Grafos

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Concepto

Un grafo es un par ordenado \displaystyle G = ( N , A ) donde \displaystyle N es un conjunto de nodos (vértices) y \displaystyle A es un conjunto de aristas o arcos que relacionan o enlazan a estos nodos.

GrafoDeEjemplo.png

Nodos

Nodos Adyacentes

Una arista x \in A está asociada a un par de nodos \displaystyle (u,v) con u,v \in N. Si existe una arista que conecta \displaystyle u con \displaystyle v, se dice que \displaystyle u y \displaystyle v son nodos adyacentes.

Aristas

Arista incidente

Una arista x \in A, que conecta los nodos \displaystyle u y \displaystyle v, se denomina incidente a los nodos \displaystyle u y \displaystyle v.

Aristas paralelas

Dos aristas son paralelas si vértice final e inicial son el mismo.

AristasParalelas.png


Grafos dirigidos, no dirigidos y mixtos

Grafos dirigidos

En un grafo dirigido, todas las aristas tienen una dirección definida.

Caminos

Un camino es una secuencia de nodos  V_1 , V_2 , \dots V_n , tal que

 V_1 \rightarrow V_2\ ;\ V_2 \rightarrow V_3\ ;\ V_3 \rightarrow V_4\ ;\ \dots\ ;\ V_{n-1} \rightarrow V_n .

El camino que va de \displaystyle V_1 a \displaystyle V_n pasa por los nodos  V_1 , V_2 , \dots V_n .

Longitud del camino

Es la cantidad de artistas (o la cantidad de nodos menos 1) de un camino.

Camino Simple y No Simple

Camino Simple

Camino en el cual todos los nodos, excepto el primero y el último, aparecen sólo una vez.

Camino No Simple

Existe al menos un nodo que se repite dos o más veces en el camino.

Por ejemplo, en el siguiente grafo, el nodo 3 aparece repetido dos veces durante el camino que va desde 1 hasta 4.

GrafoCaminoNoSimple.png


Representación de un grafo dirigido

Sea el siguiente grafo:

GrafoDeEjemplo2.png

Éste se puede representar en un programa como una matriz de incidencia o como una lista de adyacencia.

Matriz de Incidencia

MatrizDeAdyacencia.png

Donde 0 es un valor negativo y 1 es verdadero. Es decir, que hay una arista que va desde el nodo 1 hasta el nodo 2, pero no existe una arista que se dirija de 2 hasta el nodo 1, ni una que vaya de 3 hasta el nodo 3.

Lista de Adyacencia

Otra forma de programar un grafo, es mediante una lista de adyacencia. Se tiene una lista enlazada con todos los nodos que aparecen en el grafo. Sin embargo, cada nodo, además de almacenar el valor o dato de éste, contiene un puntero hacia otra lista enlazada. A su vez, cada dato de esta lista es un puntero hacia el nodo hasta donde se dirige en el camino.

ListaDeAdyacencia.png

Por ejemplo, en el grafo, el nodo 1 tiene una arista que se dirige hasta 2 y otra hacia el nodo 4. Por lo tanto, en la lista de adyacencia, el nodo 1 contiene un puntero hacia una lista enlazada formada por dos punteros; el primero apunta hacia el nodo 2 y el segundo hacia el nodo 4.


Algoritmos en grafos dirigidos

Por hacer...

Grafos no dirigidos

En los grafos no dirigidos, a diferencia de los dirigidos, cada par de vértices que son adyacentes son bidireccionales.

Conceptos importantes

Ciclo: camino simple de longitud mayor o igual a 3, donde el primer y último vértice son los mismos. Componente conexo: Es un grafo, que no es subgrafo de ningún otro subgrafo, y que cumple la propiedad que existe un camino para cualquier par de nodos dentro del grafo Árbol libre: Grafo conexo acíclico (sin ciclos).

Métodos de representacion

Matriz de adyacencia

Es igual que en las matrices de los grafos dirigidos, pero se debe tener en cuenta que decir que el nodo a está conectado con b, es lo mismo que decir que b está conectado al nodo a. Esto quiere decir que parte de la matriz es información repetida (el triagulo inferior o superior).

Lista de adyacencia

Igual que en grafos dirigidos pero con información redundante (al igual que en la matriz de adyacencia).

Algoritmos de extensión de costo mínimo

Algoritmo de Kruskal

En este algoritmo se crea un árbol de extensión (o profundidad). Este árbol conectará todos los nodos del grafo por el menor costo posible. El algoritmo dice:

* Hacer un listado de los costos de todas las aristas y cuales son las aristas que poseen dichos costos.
* Luego, comenzando desde los arcos de menor costo, se comienza a tomar los nodos que no están conectados 
  y que no forman un cíclo con los que ya se tienen tomados.
* Repitiendo el paso anterior hasta el final se tiene el árbol.

Algoritmo de Prim

Este algoritmo también posee el mismo objetivo que el algoritmo de Kruskal. Su procesdimiento es el siguiente:

* Se parte de cualquier nodo y se toma una de las conexiones disponibles que tiene dicho nodo, usando como criterio a tomar, el arista con menor costo y que
  que no genere un ciclo.
* Luego de incorporar una nueva arista (con su par de nodos) se procede el mismo paso anterior, pero tomando en cuenta los nodos que ya están conectados.
* Así, finalmente, se tendrá el árbol.

Recorrido de grafos

Búsqueda en profundidad

Es esta búsqueda, al igual que en grafos dirigidos, se realiza partiendo de un nodo "a" y tomando alguno de sus arcos disponibles de este nodo, agregando asi al nodo "b". Luego de marcar ambos nodos como visitados, se procede a tomar un nodo disponible, pero viendo las conexiones disponibles del nodo "b". En caso de no haber conexiones disponibles, se evaluá un vértice del nodo tomado anteriormente. Tener en cuenta que se genera un árbol luego de esta busqueda.

Búsqueda en amplitud

En este recorrido, se parte de un nodo "a" y se agregan todas las conexiones que posee dicho nodo (por ejemplo "b", "c" y "d"). Luego se toma uno de los vertices adyacentes, por ejemplo "b", y tomamos todos sus conexiones disponibles, luego seguimos con "c" y luego con "d", luego con los "hijos" de "b", y así susecivamente. Cabe destacar que no se deben tomar las conexiones a nodos que ya están visitados. Tomar en cuenta que se genera un árbol luego de esta búsqueda.

Grafos biconexos

En general un grafo k-conexo implica que permite la eliminación de k-1 nodos y el grafo no se ve particionado. En el caso de los grafos biconexos, significa que permite el borrado de un solo nodo y dicho grafo no se parte. Un concepto muy ligado a lo anterior es el de puntos de articulación, que son dichos vértices que al ser borrados del grafo, particionan a este, por lo tanto para que un grafo sea biconexo (al menos), no debe poseer puntos de articulación.

Algoritmo de puntos de articulación

El algoritmo nos indicará que vértices son puntos de articulación. El agoritmo es:

* Se realiza una búsqueda en profundidad, y se genera un árbol a partir de este. Deben incluirse las aristas de retroceso del árbol.
* Luego se recorre el árbol generado con la búsqueda en profundidad en preorden (orden previo). A cada nodo que se recorra, se le asigna un valor "np" que será igual a la posición en que fue listado en preorden.
* Luego se recorre el árbol en postorden (orden posterior).
* Luego se calcula un valor denominado "b". La asignación de dicho valor debe ser en el orden que se generó luego del recorrido en postorden. Este valor "b" esta dado por el mínimo entre los siguientes 3 valores:
 * El valor np del vértice actual.
 * El valor np de los nodos a los cuales se puede acceder por arista de retroceso.
 * El "b" de los hijos del nodo actual.
* Luego de anotar cada "b" a todos los nodos del árbol. se procede a aplicar el siguiente criterio para ver si un vértice es un punto de articulación. Cabe destacar que son 2 criterios, el primero solo se aplica a la raíz, y el otro es para todo el resto de los nodos del árbol. Tambien debe saberse que los vértices del árbol nunca son puntos de articulación. Los criterios son:
 * Para la raíz: Si la raíz tiene más de un hijo, entonces es un punto de articulación.
 * Otros nodos:. si el np del nodo actual es menor o igual al b de los hijos, entonces es punto de articulación.
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas