arboles y grafos


¿Qué es un grafo? 

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como unconjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, unared de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, puedenser cables o conexiones inalámbricas).


¿De que consta un grafo? 

- Aristas 
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. 
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. 
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos. 

• Aristas Adyacentes: Sedice que dos aristas son adyacentes si convergen en el mismo vértice. 

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. 

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. 

• Cruce: Son dos aristas que cruzan en un punto. 

- Vértices 
Son los puntos o nodos con los que está conformado un grafo. Llamaremosgrado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. 

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente. 

• Vértice Aislado: Es un vértice de grado cero. 

•Vértice Terminal: Es un vértice de grado 1. 

- Lazo o Bucle 
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden. 
Un bucle o lazo (loop en inglés) en un grafo o dígrafo es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles. 

- Caminos 
Un camino es una sucesión de vérticestal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. 

Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último. 

La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un caminocon longitud 5, y (5, 2, 1) es un camino simple de longitud 2... 

- Camino Cerrado 

Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado. 

- Camino Simple 

Un camino simple es aquel en que todas las aristas del camino son diferentes. 
Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos. 

- Ciclo 
UnCiclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 son los bucles. En el ejemplo, (1, 2, 3, 4, 5, 2, 1) es un ciclo de longitud 6. 

Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice del comienzo sólo aparece una vez más y como vértice final, y los demás sólo aparecen una vez. En el grafo de arriba (1, 5, 2, 1) es unciclo simple. 

Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el último. 

Ciclo Euleriano: Es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar. 

Ciclo...