Grafos Eulerianos
Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. Un grafo se denomina grafo euleriano si tiene un circuito euleriano.
Ejercicio: Determinar si el grafo siguiente tiene un camino euleriano.
Propiedades de los grafo eulerianos:
- Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
- Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
- Si un grafo no dirigido G es euleriano entonces su grafo-línea L(G) se dice que es también euleriano.
- Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
- Un grafo no dirigido se dice que es susceptible de ser recorrido si es conexo y dos vértices en el grafo tienen grado impar.
El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:
Teorema: Dado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, G tiene un ciclo euleriano.
Ejercicio: Sea \(G=(V,E)\), donde \(V\)={1,2,3,4,5,6}, \(E\)={{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,6}, {4,5}, {5,6}}, a) tiene un camino euleriano, ¿cuál es?; b) tiene un ciclo euleriano, ¿cuál es?.
Ejercicio: Sea \(G=(V,E)\), donde \(V\)={1,2,3,4,5}, \(E\)={{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{4,5}}, a) tiene un camino euleriano, ¿cuál es?; b) tiene un ciclo euleriano, ¿cuál es?.
Grafos Hamiltonianos
Un camino hamiltoniano es un camino de un grafo que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.
Ejempos de grafos Hamiltonianos:
- Todos los grafos ciclos son hamiltonianos.
- Todos los sólidos platónicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos
- Un árbol tiene un camino hamiltoniano si y sólo si tiene a lo sumo dos hojas.
Ejercicio: ¿Tiene un camino hamiltoniano?
Hay que tener en cuenta que cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se elimina cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.
Ejercicio: Determinar si el siguiente grafo es hamiltoniano
Ejercicio: Sea \(G=(V,E)\), donde \(V\)={1,2,3,4,5,6}, \(E\)={{1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {3,4}, {3,6}, {4,5}, {5,6}}, a) tiene un camino hamiltoniano, ¿cuál es?; b) tiene un ciclo hamiltoniano, ¿cuál es?.
Un resultado que puede ayudarnos a distinguirlos es el siguiente:
Propiedad: Un grafo con \(n\) vértices \((n > 3)\) es hamiltoniano si cada vértice tiene grado mayor o igual a \(n/2\).
Grafos planos
Decimos que un grafo es plano (o planar según referencias) si es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce.
Los grafos \(K_5\) y el \(K_{3,3}\) son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.
Teorema de Kuratowski: Un grafo es plano si y solo si no contiene un subgrafo isomorfo a una subdivisión elemental de \(K_5\) (el grafo completo de 5 vértices) o \(K_{3,3}\) (el grafo bipartito completo de 6 vértices).
Ejercicio: Sea \(G=(V,E)\), donde \(V\)={1,2,3,4,5,6}, \(E\)={{1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {3,4}, {3,6}, {4,5}, {5,6}}, ¿es plano?.
Ejercicio: Determinar si es plano el grafo
En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de n vértices y a el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:
Teorema: Si G es un grafo plano con n ≥ 3 vértices, entonces a ≤ 3n – 6
Teorema: Si n > 3 y no existen ciclos de longitud 3, entonces a ≤ 2n – 4
Ejercicio: Determinar el mínimo número de aristas que hay que eliminar a $K_6$ para que sea plano
Regiones de un grafo plano
Un grafo plano, apropiadamente representado divide al plano en distintas regiones (llamadas caras).
Un mapa es un grafo plano en el que nos interesan las caras entre las aristas.
Un de los resultado más interesante de los grafos planos es la fórmula de Euler:
Fórmula de Euler: Si un grafo plano y conexo tiene \(v\) vértices, \(a\) aristas y \(c\) caras, entonces \[v − a + c = 2\]
Ejercicio: Sea \(K_5\) y eliminemos las aristas mínimas necesarias para conseguir que sea plano, ¿cuántas regiones tiene?
Coloración de grafos
La coloración de grafos es una forma de asignar etiquetas, llamadas colores, a elementos del grafo. En una coloración, los vértices de un grafo cumplen que ningún vértice adyacente comparte el mismo color.
La vértice coloración (o simplemente coloración) es la asignación de los vértices de un grafo con colores tal que dos vértices que comparten la misma arista tengan colores diferentes. Un grafo con bucles no puede ser coloreado; solo se consideran grafos simples.
El número cromático de un grafo es la menor cantidad de colores necesarios para colorear sus vértices sin que dos vértices adyacentes tengan el mismo color. O más formalmente, es el menor entero m tal que G es m-coloreable (o bien, tiene una coloración propia con m colores). A este número se le denota como \(\chi(G)\).
El único grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo \({\displaystyle K_{n}\,}\) de \(n\) vértices requiere \({\displaystyle \chi (K_{n})=n\,}\) colores.
Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos árboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable.
Una de las principales aplicaciones de la coloración de grafos es la asignación de registros en compiladores, introducida en 1981.
Ejercicio: ¿Cuál es \(\chi(G)\) donde \(G\) es el grafo de Petersen(*)?
(*)De <a href=»//commons.wikimedia.org/w/index.php?title=User:Leshabirukov&action=edit&redlink=1″ class=»new» title=»User:Leshabirukov (page does not exist)»>Leshabirukov</a> – Own work by uploader based on <a class=»external free» href=»https://en.wikipedia.org/wiki/File:Heawood_Graph.svg»>http://en.wikipedia.org/wiki/File:Heawood_Graph.svg</a>, CC BY-SA 3.0, Enlace
Un caso particular es la coloración de las aristas: asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color. El proceso lo podemos repetir con las caras de un grafo plano, asignando un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. En este caso se trata de un grafo plano.
Para terminar os dejo unos enlaces de interés
| Ejercicio: Sea (58, 20, 34, 86, 66, 24, 55, 36, 15) la secuencia de números que se van insertando en un ABB inicialmente vacío y \(H\) el número de hojas que tiene el árbol binario de búsqueda resultante tras insertar todos los elementos en el orden dado. ¿Cuál es el valor de \(\mathbf{mod}(H*21, 23)\) |
B.)
Primero dibujamos el grafo ABB.
Observamos que tiene 4 hojas. Por tanto, \(\mathbf{mod}(4*21, 23)=15\)