Grafos

Un árbol es un grafo simple G que satisface alguna de las siguientes condiciones equivalentes:
* G es conexo y no tiene ciclos .
* G no tiene ciclos y, si se añade alguna arista se forma unciclo.
* G es conexo y si se le quita alguna arista deja de ser conexo.
* G es conexo y el grafo completo de 3 vértices no es un menor de G.
* Dos vértices cualquiera de G estánconectados por un único camino simple.
* G es conexo y tiene n − 1 aristas.
Propiedades
* Todo árbol es a su vez un grafo bipartito.
* Todo árbol con sólo un conjunto numerable de vértices esademás un grafo plano.
* Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.
Árbol generador
Un árbol generadorde 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 generador mínimo
El árbol generadormínimo es un árbol generador construido sobre un grafo conexo ponderado con un criterio de selección de aristas definido por su menor peso.
El algoritmo de Dijkstra
También llamado algoritmo de caminosmínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lodescribió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices;cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
Ejemplo:

Se quiere hallar el camino más corto que hay desde “a”hasta “d”.
Primero se deben considerar las adyacencias del vértice “a” colocando unas etiquetas a los lados de sus vértices adyacentes y se toma el camino con el menor valor de las aristas....