Este documento presenta diferentes propiedades que caracterizan clases de grafos. Explica que los grafos bipartitos se caracterizan por no tener ciclos de largo impar, y que los grafos Eulerianos se caracterizan por tener a lo más una componente no trivial y todos sus vértices deben tener grado par. También introduce técnicas como considerar estructuras extremas para demostrar propiedades de grafos.
0 calificaciones0% encontró este documento útil (0 votos)
44 vistas8 páginas
Este documento presenta diferentes propiedades que caracterizan clases de grafos. Explica que los grafos bipartitos se caracterizan por no tener ciclos de largo impar, y que los grafos Eulerianos se caracterizan por tener a lo más una componente no trivial y todos sus vértices deben tener grado par. También introduce técnicas como considerar estructuras extremas para demostrar propiedades de grafos.
Este documento presenta diferentes propiedades que caracterizan clases de grafos. Explica que los grafos bipartitos se caracterizan por no tener ciclos de largo impar, y que los grafos Eulerianos se caracterizan por tener a lo más una componente no trivial y todos sus vértices deben tener grado par. También introduce técnicas como considerar estructuras extremas para demostrar propiedades de grafos.
Este documento presenta diferentes propiedades que caracterizan clases de grafos. Explica que los grafos bipartitos se caracterizan por no tener ciclos de largo impar, y que los grafos Eulerianos se caracterizan por tener a lo más una componente no trivial y todos sus vértices deben tener grado par. También introduce técnicas como considerar estructuras extremas para demostrar propiedades de grafos.
Descargue como PDF, TXT o lea en línea desde Scribd
Descargar como pdf o txt
Está en la página 1/ 8
MLM 2070 - Teorı́a de Grafos
Luis A. Dissett
Clase 4
1 Caracterización de grafos por propiedades Un tema recurrente será el de caracterizar clases de grafos usando propiedades de diversos tipos. Dada una clase G de grafos, queremos hallar una propiedad P que caracterice los elementos de G, o sea, tal que
G ∈ G ⇐⇒ G satisface P.
Ejemplo: grafos bipartitos y ciclos
Caracterizaremos los grafos bipartitos a partir de los ciclos que
contienen.
2 Grafos bipartitos Lema. Toda caminata cerrada de largo impar contiene un ciclo de largo impar.
Demostración. Por inducción en el largo de la caminata.
Definición. Una bipartición de G es una especificación de dos
conjuntos independientes de vértices, cuya unión es V (G). Un grafo bipartito con bipartición X, Y (también llamado un bigrafo X − Y ) es uno donde los conjuntos independientes son X e Y.
Teorema (König, 1936). Un grafo es bipartito si y sólo si no
tiene ciclos de largo impar
3 Grafos Eulerianos Definición. Un grafo es Euleriano si tiene un circuito que contiene todas las aristas. Un circuito Euleriano o recorrido Euleriano en un grafo es un circuito o recorrido que contiene todas las aristas.
Definición. Un grafo es par si todos sus vértices tienen grado par.
Un vértice es par (o impar ) cuando su grado es par (o impar).
Definición. Un camino maximal en un grafo G es un camino P en
G que no está contenido en ningún camino más largo.
Lema. Si todo vértice en un grafo G tiene grado ≥ 2, entonces G
contiene un ciclo. Nota: aquı́ estamos usando fuertemente la hipótesis de que G es finito.
4 Caracterización de grafos Eulerianos Teorema. Un grafo es Euleriano si y sólo si tiene a lo más una componente no trivial y todos sus vértices tienen grado par. La demostración de este teorema tiene el siguiente
Corolario (de la demostración). Todo grafo par se descompone
en ciclos.
5 CONTSS “Condiciones obviamente necesarias también son suficientes.” Tanto en la caracterización de grafos bipartitos como de grafos Eulerianos, la necesidad de la condición es clara. Lo interesante era probar que esas condiciones bastan.
6 Extremalidad Una técnica útil al demostrar propiedades de grafos es considerar estructuras “extremas” en un cierto sentido (maximales o minimales con respecto a una propiedad). El hecho de que sean extremas fuerza el que aparezca información adicional. Ejemplo. En la demostración de que todo grafo en que los grados son ≥ 2 tiene un ciclo, el camino maximal tiene la propiedad de que todos los vecinos de uno de sus extremos pertenecen ya al camino.
7 Ejemplos Teorema. Si G es un grafo simple en que cada vértice tiene grado ≥ k, entonces G contiene un camino de largo ≥ k. Si k ≥ 2, entonces G también contiene un ciclo de largo ≥ k + 1.
Teorema. Todo grafo que contiene una arista que no es un lazo
tiene por lo menos dos vértices que no son de corte.
