Grafos

Grafos dirigidos y no dirigidos

En matemáticas y ciencias de la computación, un grafo o gráfica es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo 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.
Típicamente, un grafo se representagráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red 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, pueden ser cables oconexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
Un grafo G es un par ordenado G = (V,E), donde:
* V es un conjunto de vértices o nodos, y
* E es un conjunto de arcos o aristas, que relacionan estos nodos.
Normalmente V suele ser finito. Muchosresultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .

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 seles llama sus extremos.
* Aristas Adyacentes: Se dice 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 nodoscon los que está conformado un grafo. Llamaremos grado 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.
Dígrafo (grafo dirigido).
A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.

  
Una de las aplicaciones mas importantes es de hallar el camino mas corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, parael recorrido de árboles, sirve para la representación de algoritmos, etc. Un ejemplo de esto es la tarea de freír un huevo.
Grafo no dirigido

En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que yrepresentan dos arcos diferentes.

Ejemplos
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
G2 = (V2, A2)
V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}
G3 = (V3, A3)
V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de lasiguiente manera:

Algunos de los principales tipos de grafos son los que se muestran a continuación:

* Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
* Grafo bipartito: Es aquel con cuyos vértices pueden formarse...