arboles en la teoría de grafos y un programa en c

Árbol en la teoría de grafos
En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices que están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles.Un árbol a veces recibe el nombre de árbol libre.
Los árboles satisfacen las siguientes características:
⦁ Un árbol es un grafo conexo y acíclico (sin ciclos).
⦁ Un bosque es un grafo acíclico, osea, una unión disjunta de árboles.
⦁ Una hoja en un grafo es un vértice de grado 1.
⦁ Un árbol generador de un grafo G es un subgrafo generador de G que es un árbol.
Los puentes de Königsburg y ciclosde Euler
Leonard Euler, uno de los grandes matemáticos de la historia, vivía en Königsburg, y los colegas de él se divertían discutiendo un problema: cómo hacer una caminata por la ciudad cruzando cadauno de sus siete puentes una y sólo una vez, y volver al punto de partida.
Un plano de la ciudad mostraba algo como se ve en la figura
Los puentes de Königsburg.
...y su grafo equivalenteNaturalmente hemos simplificado bastante el plano de Königsburg del siglo 18 porque sólo importan los puentes, las islas, y las dos bandas del río. Pero Euler quería simplificar aún más.
El decía que era unproblema del grafo en la figura, y que no importaba si los nodos eran islas o bandas o qué. Y se puso a pensar en la generalidad de esos curiosos objetos, que ahora llamamos grafos, de los cuales habíaproducido un ejemplo, y en el problema de encontrar un camino que pasaba por cada arista y volvía al nodo de partida.
Un camino no nulo cuyo recorrido empieza y termina en el mismo nodo y que norepite ninguna arista se llama ciclo.
Un ciclo que contiene todas las aristas del grafo se llama ahora ciclo de Euler porque Euler resolvió ese primer problema con que fundó la teoría de grafos.
Y resultóque no existía un ciclo de Euler para los puentes de Königsburg. La razón era que el grafo tiene nodos de grado impar. El grado de un nodo es el número de aristas no rulos conectados al nodo. La...