Autor Tema: Grafos

0 Usuarios y 1 Visitante están viendo este tema.

06 Abril, 2021, 07:17 pm
Leído 334 veces

carambola

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 59
  • País: es
  • Karma: +0/-0
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!!

08 Abril, 2021, 11:18 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,038
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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.