ILlamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V, y un conjunto, A, de pares no ordenados de elementos del mismo. V es el conjunto de los vértices o nodos del grafo. A sera el conjunto de las aristas o arcos del grafo. Utilizaremos la notación G = (V,A) para designar al grafo cuyos conjuntos de vértices y aristas son, Respectivamente, V y A. El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).







































De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. Por otro lado, y debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo.



Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia, aquí sólo se realizará una introducción a la misma, describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

Grafos Dirigidos.

Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).



Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido. Por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. No obstante, podemos dar unas definiciones generales para ambos tipos.

A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados.



DEFINICIONES Y TERMINOLOGÍA FUNDAMENTAL.



Un grafo G es un conjunto en el que hay definida una relación binaria, es decir G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y   es una relación binaria a cuyos elementos denominaremos arcos o aristas.

Dados   ,puede ocurrir que:



1.     , en cuyo caso diremos que x e y están unidos mediante un arco, y



2.     , en cuyo caso diremos que no lo están.



Si las aristas tienen asociada una dirección (las aristas (x, y) y (y, x) no son equivalentes) diremos que el grafo es dirigido, en otro caso ((x, y)=(y, x)) diremos que el grafo es no dirigido.























​Definición 1 Un grafo simple G (V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos Distintos de V . A esos pares se les llama aristas o lados.



Ejercicio 1 Muestre que si G es simple, entonces " ≤



En algunos casos lo grafos simples no bastan para modelar ciertas situaciones en las cuales se requiere de la existencia de múltiples aristas entre par de Vértices. En este caso no es suficiente definir las aristas como par de vértices;

La definición de multígrafo es un poco más complicada.



Definición 2 Un multígrafo G (V,E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f (e1) = f(e2).

Los multígrafos definidos no admiten bucles o lazos (aristas que conectan Un vértice consigo mismo). Usamos en este caso, pseudografos que son más generales que los multígrafos.



Definición 3 Un pseudografo G (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V }. Se dice que una arista e es un bucle o lazo si f (e) = {u, u} = {u} para algún

u ∈ V .



La diferencia entre grafo y dígrafo es que el último tiene los lados dirigidos y se entiende como un grafo dirigido.

Definición 4 Un grafo dirigido o dígrafo G = (V, E) consta de un conjunto

V de vértices, un conjunto E de aristas, que son pares ordenados de elementos de V.

Definimos los multígrafos dirigidos de la siguiente manera

Definición 5 Un multígrafo dirigido G (V,E) consta de un conjunto V de Vértices, un conjunto E de aristas y una función f de E en {(u, v)|u, v ∈ V }.



Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f (e1) = 1.1. Adyacencia de Vértices, Incidencia de Aristas y Grado de los Vértices Dos vértices u, v de un grafo G = (V, E) se dicen adyacentes si {u, v} ∈ E, asimismo dos aristas son adyacentes si tienen un mismo vértice como extremo; análogamente si e = {u, v} decimos que el lado e es incidente a los vértices u y v. El grado de un vértice es el número de lados incidentes a él. El grado de un vértice u se denota gr(u). Denotamos con ± (G) y ¢ (G) el mínimo y el máximo grado de los vértices de G respectivamente.



COMPONENTES DE 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: 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 nodos con 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.



Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

x e y se llaman los extremos del camino
El número de aristas del camino se llama la longitud del camino.
Si los vértices no se repiten el camino se dice propio o simple.
Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
Llamaremos ciclo a un circuito simple
Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo



Clasificación de grafos



Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. 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 y representan 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 la siguiente 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 dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

A continuación pueden verse los dibujos de K3, K4, K5 y K6

Un grafo bipartito regular: se denota Km, n donde m, n es el grado de cada conjunto disjunto de vértices.



A continuación ponemos los dibujos de K1, 2, K3, 3, y K2, 5

























Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

​

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.



























Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.









​





















Grafos Eulerianos.



Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.

Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.

 

Grafos Conexos.

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".



























Árboles.



Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también a cíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).

Bosques de árboles.

Los bosques de árboles son un caso similar a los árboles, son a cíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.



​























Recorrido de un grafo.



Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.

Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.



















​