Matemática => Teoría de grafos => Mensaje iniciado por: Julio_fmat en 03 Noviembre, 2019, 21:58



Título: Grafo disconexo
Publicado por: Julio_fmat en 03 Noviembre, 2019, 21:58
Demuestre o encuentre un contraejemplo para la siguiente afirmacion: El complemento de un grafo disconexo es un grafo conexo.



Título: Re: Grafo disconexo
Publicado por: Luis Fuentes en 04 Noviembre, 2019, 06:06
Hola

Demuestre o encuentre un contraejemplo para la siguiente afirmacion: El complemento de un grafo disconexo es un grafo conexo.

Es cierto. Sean [texx]G_1[/texx] y [texx]G_2[/texx] dos componentes conexas del grafo y [texx]v_1\in G_1[/texx] y [texx]v_2\in G_2[/texx].

Cualquier vértice de [texx]G_2[/texx] no está unido a [texx]v_1[/texx] en el grafo original por tanto si está unido en el complementario.

Cualquier vértice de [texx]G_1[/texx] no está unido a [texx]v_2[/texx] en el original por tanto si está unido en el complementario; y este a su vez a [texx]v_1[/texx] luego también cualquier vértice de [texx]G_1[/texx] está unido a [texx]G_1[/texx] por un camino en el complementario.

Finalmente cualquier otro vértice en cualquier otra componente conexa del grafo original no está unido a [texx]v_1[/texx] en éste y entonces si en el complementario.

Saludos.