Scribd
Cargar
36 vistas2 páginas

Tarea 1 Grafos

El documento presenta la demostración de que un grafo simple no trivial es conexo si y solo si, para cualquier partición de sus vértices en dos subconjuntos no vacíos, existe al menos una arista que conecta un vértice de un subconjunto con un vértice del otro. También se incluye una demostración relacionada con la equivalencia de grafos y un ejercicio que pide un ejemplo de un grafo simple no conexo con ciertas características. Se mencionan ejercicios específicos que requieren pruebas y ejemplos en el contexto de la teoría de grafos.

Cargado por

Camilo Diaz
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
36 vistas2 páginas

Tarea 1 Grafos

El documento presenta la demostración de que un grafo simple no trivial es conexo si y solo si, para cualquier partición de sus vértices en dos subconjuntos no vacíos, existe al menos una arista que conecta un vértice de un subconjunto con un vértice del otro. También se incluye una demostración relacionada con la equivalencia de grafos y un ejercicio que pide un ejemplo de un grafo simple no conexo con ciertas características. Se mencionan ejercicios específicos que requieren pruebas y ejemplos en el contexto de la teoría de grafos.

Cargado por

Camilo Diaz
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Tarea 1

Juan Camilo Ramı́rez Dı́az


17 de mayo de 2025

Ejercicio 5.8. Pruebe que un grafo simple no trivial G es conexo si y solo si, para toda
partición del conjunto de vértices V en dos subconjuntos no vacı́os V1 y V2 , existe al menos
una arista que conecta un vértice de V1 con un vértice de V2 .

Demostración.

[⇒] Supongamos que G es conexo.

Supongamos por contradicción que existe una partición del conjunto de vértices V en dos
subconjuntos no vacı́os V1 y V2 (pues G es no trivial), tal que no hay aristas entre vértices
de V1 y vértices de V2 . Sean v1 ∈ V1 y v2 ∈ V2 . entonces por la condición anterior, dado que
no hay aristas entre V1 y V2 , se sigue que tampoco existirá ninguna trayectoria v1 − v2 , lo
cual contradice el hecho de que G es conexo.

[⇐] Supongamos que para toda partición del conjunto de vértices V en dos subconjuntos
no vacı́os V1 y V2 , existe al menos una arista que conecta un vértice de V1 con un vértice de V2 .

Supongamos por contradicción que G no es conexo. Entonces existen al menos dos com-
ponentes conexas G1 y G2 de G. Defina:

V1 := V (G1 ), V2 := V (G2 )

Entonces V1 y V2 son una partición de V , la cual cumple que ninguna arista conectará a
un vértice de V1 con uno de V2 (pues de lo contrario serı́a G1 = G2 ), en contradicción con
nuestra hipótesis.

Ejercicio 9.5. Pruebe que L(Km,n ) ≃ Km □Kn .

Demostración.

Ejercicio 12.8. De un ejemplo de un grafo simple no conexo con ω componentes, n vértices,


y (n−ω)(n−ω+1)
2
aristas.

1
3

4 2 6 7

G2 G3
5 1

G1

También podría gustarte