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.
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?.
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
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: 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?.
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.
El número cromático de una 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)\).
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 G=(V,E), donde V={1,2,3,4,5}, y E={{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}}. ¿Cuál es el valor del menor principal de orden 3 de la matriz laplaciana de G? |