Caminos Y Ciclos

Matriz de adyacencia

Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. La matriz de adyacencia para G es una matriz booleana de dimensión nxn, donde cada elemento [i, j] vale 1 si y solo si, existe un arco (i, j).

Construcción de la matriz a partir de un grafo[editar]

1. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.

2. 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.

Grafo no dirigido Matriz de adyacencia

Grafo dirigido Matriz de adyacencia

Lista de adyacencia

Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. La lista de adyacencia para un vértice i es una lista, en algún orden, de todos los vértices adyacentes a i. Se puede representar G por medio de un arreglo H, donde H[i] es un apuntador a la lista de adyacencia del vértice i.

VÉRTICE ADYACENTE: El vértice y es adyacente al vértice x, si y solo si, (x, y) es una arista del grafo. En este caso, el arco (x, y) es incidente sobre el vértice y. y es el vértice “punta” y x es el vértice “cola” , del arco(x, y).

Incidencia De Aristas

Matriz de Incidencia - Definición

Una matriz de incidencia representa las relaciones binarias entre dos elementos, en nuestro caso entre un vértice y una arista del grafo.

Para construir la matriz de incidencia a partir de un grafo debemos realizar una matriz de n x a donde n es el nº de nodos o vértices y a es el nº de aristas.

En esta matriz las columnas representan las aristas y las filas los vértices.

Para cada A[i] [j] ,nótese que A es la matriz de Incidencia, puede valer:

0 si vértice i no es incidente con arista j

1 si vértice i es incidente con arista j

Fotografía de un ejemplo de grafo dirigido y su respectiva matriz de incidencia

Podemos que el nº de unos en una fila nos indica el nº de aristas que inciden en un vértice.

Grados de los Vértices

En Teoría de grafos, el grado o valencia de un vértice es el número de aristas incidentes al vértice. El grado de un vértice x es denotado

...