| Autor |
Mensaje |
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Hola,
estoy preparando el final de discreta y estoy trabado con una parte de la demostración de un teorema de árboles que no llego a entender.
Alguien sería tan amable de explicarme o pasarme la demostración que se vio en la clase teoría del punto c):
Teorema: Sea T=(V,A), son equivalentes:
a) T es árbol
b) T es conexo y no tiene ciclos
c) T es conexo y tiene n-1 aristas
d) T no tiene ciclos y tiene n-1 aristas
Gracias.
Saludos.
|
|
|
|
|
|
   |
    |
|
Amadeo
Nivel 9
Registrado: 20 Oct 2008
Mensajes: 1436
Carrera: No especificada
|
|
a) ==> b)
Como T es árbol, entonces existe un único camino simple entre todo par de nodos. Como justamente existe ese camino entre todo par de nodos, T es conexo, ya que si no lo fuera, existiría un nodo v tal que no hay ningún camino simple de algún otro nodo hacia v, lo cual es absurdo porque T es árbol. Además, no puede haber ciclos, ya que si fuera así, habrían por lo menos 2 caminos de v a u, para algún nodo v y u, lo cuál contradice que existe un único camino simple entre todo par de nodos.
|
|
|
|
|
|
| |
 |
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
Al final lo encontré bien explicado en el libro de Johnsonbaugh.
Dejo una captura de la explicación.
|
|
|
|
|
|
| |
|
|
gonzaloi
Nivel 7
Edad: 34
Registrado: 06 May 2008
Mensajes: 398
Carrera: No especificada
|
|
| Amadeo escribió:
|
a) ==> b)
Como T es árbol, entonces existe un único camino simple entre todo par de nodos. Como justamente existe ese camino entre todo par de nodos, T es conexo, ya que si no lo fuera, existiría un nodo v tal que no hay ningún camino simple de algún otro nodo hacia v, lo cual es absurdo porque T es árbol. Además, no puede haber ciclos, ya que si fuera así, habrían por lo menos 2 caminos de v a u, para algún nodo v y u, lo cuál contradice que existe un único camino simple entre todo par de nodos.
|
Hola Amadeo, mi duda era con el punto c), igual te agradezco por ayudar 
Saludos.
|
|
|
|
|
|
| |
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
|
|
[ Tiempo: 0.4290s ][ Pedidos: 20 (0.3544s) ] |
