Árbol generador.

Árbol generador. Un árbol generador de un grafo conexo es un subgrafo conexo con el menor número posible de aristas y con todos los vértices del grafo original. No tiene porque ser único.

Árbol dirigido: es un árbol con un vértice distinguido como raíz y tal que cada arista apunta del vértice más cercano a la raíz al más lejano

Árbol no dirigido: es la cerradura simétrica de un árbol es decir, es un árbol con todas sus aristas bidireccionales

Árbol generador mínimo. El árbol generador mínimo es un árbol generador construido sobre un grafo conexo ponderado con un criterio de selección de aristas definido por su menor peso.

Bosque: es un grafo acıclico o sea, una unión disjunta de arboles.

Hoja: Son los vértices que no tienen hijos.

algoritmo voraz: es aquel que, para resolver un determinado problema, sigue una heurísticaconsistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

Algoritmo de Kruskal. Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).

Algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo

...