UNIDAD IV. GRAFOS

GRAFOS

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 representa gráficamente como un conjunto 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, 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 o conexiones inalámbricas).

Un grafo consta de vértices y aristas. Los vértices son objetos que contienen información y las aristas son conexione entre vértices. Para representarlos se suele utilizar puntos para los  vértices y líneas para las aristas (las conexiones). Hay que recordar siempre que la definición de un grafo no depende de su representación.

Tipos de grafos

Grafos simples

Un grafo es simple si sólo 1 arista que une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina Multigráfica o Grafo múltiple.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Ejemplo de grafo conexo y no conexo

 

 

 

Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente K, siendo K_n el grafo completo de n vértices.

Un K_n, es decir, grafo completo de n vértices tiene exactamente aristas.

La representación gráfica de los K_n como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos

Un grafo G es bipartito si puede expresarse como {G= V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• V₁ y V₂ son disjuntos y no vacíos.
• Cada arista de A une un vértice de V₁ con uno de V₂.
• No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes.

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 es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles.

CAMINO

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

Camino simple

 Un camino simple es aquel en que todas las aristas del camino son diferentes.

Camino cerrado

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

Un camino es cerrado si sus extremos coinciden.

Caminos ajenos

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

Longitud de un camino

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.

CICLO

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Un Ciclo es un camino que empieza y acaba en el mismo vértice.

ARBOL

Un árbol es un grafo conexo simple acíclico. Algunas veces, un vértice del árbol es distinguido llamándolo raíz. Los árboles se usan frecuentemente como estructuras de datos en ciencias de la computación.

Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay n^n-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Árbol binario

Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3. De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos.

GRAFO COMPLETO

Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n − 1) / 2 aristas, y se nota K_n. Es un grafo regular con todos sus vértices de grado n − 1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

GRAFO ETIQUETADO

Un grafo etiquetado es la asignación de etiquetas, tradicionalmente representada mediante enteros, a las aristas o vértices, o ambos, de un grafo.

Formalmente, dado un grafo G, un vértice etiquetado es una función que hace corresponde vértices de G a un conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de etiquetas. En este caso, G es llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado ésta puede ser llamada como grafo ponderado.

El término grafo etiquetado generalmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas. Tal grafo puede ser equivalentemente etiquetado mediante enteros consecutivos {1,..., n}, donde n es el número de vértices en el grafo. Para muchas aplicaciones, a las aristas y los vértices le corresponden etiquetas que tienen un significado en el dominio asociado.

Tipos de etiquetados

Etiquetado elegante

Un grafo es denominado como elegante cuando sus vértices son etiquetados desde 0 a ||E||, el tamaño del grafo, y este etiquetado induce un etiquetado de aristas desde 1 a ||E||.

Etiquetado armonioso

Un grafo armonioso es un grafo con k aristas que permiten una inyección de los vértices de G al grupo de enteros modulo k que induce una biyección entre las aristas de G y los enteros positivos hasta ||E||.

Coloración de grafos

La coloración de grafos es un caso especial de grafos etiquetados, tales que los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas.

MULTÍGRAFO

Un multígrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multígrafo G es un par ordenado G:=(V, E) donde:

• V es un conjunto de vértices o nodos
• E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

Algunos autores permiten que los multígrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo.

FORMAS DE REPRESENTACIÓN DE GRAFOS

Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas de adyacencia (no acotadas).

Matriz de adyacencia

Se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

EJEMPLO

Lista de adyacencia

Se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.

EJEMPLO