Grafos
Definición de Grafo.
Los grafos son, como veremos, un lenguaje, una notación, que permite representar relaciones binarias —es decir, entre pares de objetos— en un conjunto.
De una manera informal, podríamos decir que un grafo es una colección de vértices y de aristas que unen estos vértices. Los vértices los dibujaremos como puntos del plano, y las aristas serán líneas que unen estos puntos. Vayamos con las definiciones formales:
Definición: Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ϵ¸ V, a≠b.
Definición: Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.
De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.
En la teoría de los grafos, solo queda lo esencial del dibujo de un grafo. La forma de los nodos no es relevante, sólo importan sus enlaces. La posición de los nodos se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles.
¿De que consta un grafo?
Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones.
Hay que recordar siempre que la definición de un grafo no depende de su representación.
Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo.
Lazo o Bucle
Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo nodo.
Un grafo se dice simple si no tiene lazos y existe como mucho un enlace entre cada par de nodos.
Camino
Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J, L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.
Camino Simple
Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol. Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.
Camino Cerrado o Ciclo
Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
Un ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 son los lazos (o bucles). En el ejemplo, C1 = (v2, v1, v5, v4, v3, v1, v2) es un ciclo de longitud 6.
Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el nodo del comienzo solo aparece una vez más y como nodo final, y los demás solo aparecen una vez. En el grafo C2 = (v1, v2, v3, v1) es un ciclo simple.
Un grafo se dice no cíclico si no contiene ningún ciclo simple.
Grafo Conexo
En teoría de grafos, un grafo G se dice conexo, si para cualquier par de vértices a y b en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de a a b.
-Un grafo es k-conexo si contiene k caminos independientes entre cualesquiera dos vértices.
--Un punto de articulación es un nodo tal que si lo quitamos nos quedamos con un grafo disconexo (no conexo).
--Un puente es una enlace tal que si lo quitamos nos quedamos con un grafo disconexo.
--Un conjunto de corte es un conjunto de nodos que al ser eliminado desconecta el grafo.
Árbol
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 nn-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. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.
Gráfica Completa
La gráfica completa sobre n vértices, denotada por Kn, es la gráfica simple con n vértices en la que hay una arista entre cada par de vértices.
Gráfica Etiquetada
Se dice que una gráfica esta etiquetada si sus aristas tienen asignado un valor. Si cada arista a tiene un valor numérico no negativo u(a), llamado peso o longitud de a, se dice que G tiene peso. En esta caso, cada camino P de G tendrá asociado un peso o longitud que será la suma de los pesos de las aristas que forman el camino P.
Multigrafo
Un multigrafo 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 multigrafo 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.
Un multidigrafo es un grafo dirigido que está facultado para tener aristas múltiples, es decir, aristas con los mismos nodos iniciales y finales. Formalmente, un multidigrafo G es un par ordenado G:=(V,A) donde:
V es un conjunto de vértices o nodos
A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.
Un multidigrafo mixto G:=(V, E, A) puede definirse de la misma manera que un grafo mixto, es decir, con la capacidad de poseer al mismo tiempo aristas dirigidas (A) y no dirigidas (E).
Matriz de Adyacencia
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
Construcción de la matriz a partir de un grafo
--Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
--Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.
Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.
Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).
Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.
Ejemplo de grafo no dirigido
Ejemplo de grafo no dirigido, para el que se calcula la matriz de adyacencia.
La matriz de adyacencia para el grafo no dirigido de la Figura 1 viene dada por:
Ejemplo de grafo dirigido
Ejemplo de grafo dirigido, para el que se calcula la matriz de adyacencia.
La matriz de adyacencia para el grafo dirigido de la Figura 2 viene dada por:
