Rincón Matemático

Matemática => Matemática Discreta y Algoritmos => Teoría de grafos => Mensaje iniciado por: carambola en 06 Abril, 2021, 07:17 pm

Título: Grafos
Publicado por: carambola en 06 Abril, 2021, 07:17 pm
Demostrar la siguiente proposición:

Sea \( G = (V, E) \) un grafo conexo y $$E',\widehat{E}\subset E$$ tal que el grafo \( (V, E) \) no tiene ciclos y $$|E'|<|\widehat{E}|$$. Probar que existe $$e\in \widehat{E}$$ que conecta vértices de diferentes componentes conexas del grafo \( (V, E') \).


Gracias!!
Título: Re: Grafos
Publicado por: Luis Fuentes en 08 Abril, 2021, 11:18 am
Hola

Sea \( G = (V, E) \) un grafo conexo y $$E',\widehat{E}\subset E$$ tal que el grafo \( (V, E) \) no tiene ciclos y $$|E'|<|\widehat{E}|$$. Probar que existe $$e\in \widehat{E}$$ que conecta vértices de diferentes componentes conexas del grafo \( (V, E') \).

Si \( G \) es conexo y sin ciclos es un árbol. Entonces cada componente conexa de \( (V,E') \) es un árbol. Si \( |E'|=a \), entonces la componente conexa más grande a lo sumo tiene \( a+1 \) vértices y \( a \) aristas. Si \( |\widehat{E}|=b>a \) entonces las aristas de \( E' \) no puden en estar en una sola componente conexa  de \( (V,E') \), ya que hemos visto que a lo sumo tienen \( a \) aristas.

Saludos.