Análisis combinatorios: Gráfica conexa ¡Como resolver el siguiente ejercicio;
- Sea G una gráfica conexa tal que |E(G)|=|V(G)|-1 y sean v1 y v2 dos vértices de G. ¿Existen trayectorias entre v1 y v2?, en caso de que existan, ¿cuántas existen?.
Anteriormente le envíe otros ejercicios, le comento que ya pude resolverlos.
1 Respuesta
Respuesta de Valero Angel Serrano Mercadal
1
·
·
¡Hola Carolinaboni!
Es una gráfica conexa, luego existen trayectorias entre cualesquiera dos puntos.
La teoría dice que toda gráfica conexa tiene un arbolo generador, luego está lo tiene. También dice que un árbol tiene |V(G)|-1 aristas, y como está gráfica tiene esas aristas el árbol generador debe ser G, a G no le sobra ninguna arista fuera del árbol. Luego G es un árbol y la teoría dice que un árbol es aquella gráfica tal que existe una y solo una trayectoria entre cualquier par de vértices. Por tanto la respuesta es que hay una trayectoria única entre cualquier par de puntos.
Y eso es todo, saludos.
:
:
