Representación de

Grafos

Pablo Rojas V.

Matriz de adyacencia

• Un grafo se puede representar mediante una matriz A

tal que A[i,j]=1 si hay un arco que conecta vi con vj, y 0

si no.

• La matriz de adyacencia de un grafo no dirigido es

simétrica.

• Una matriz de adyacencia permite determinar si dos

vértices están conectados o no en tiempo constante,

pero requieren O(n2) bits de memoria.

• Esto puede ser demasiado para muchos grafos que

aparecen en aplicaciones reales, en donde |E|<<n2.

• Otro problema es que se requiere tiempo O(n)

para encontrar la lista de vecinos de un vértice dado.

Matriz de adyacencia

6

3 4

2 5

1

1 1 0 0 1 0

1 0 1 0 1 0

0 1 0 1 0 0

0 0 1 0 1 1

1 1 0 1 0 0

0 0 0 1 0 0

Listas de adyacencia

Esta representación consiste en almacenar, para cada

nodo, la lista de los nodos adyacentes a él.

Para el segundo ejemplo anterior, v1: v2 v2: v2, v3 v3: v1,

v4 v4: v3

Esto utiliza espacio O(|E|) y permite acceso eficiente a

los vecinos, pero no hay acceso al azar a los arcos.

3

2 4

1

2

2

1

5

5

4

G 5

1

4

3

4

5

4

2

5 2 3

2 4

1

Caminos, ciclos y árboles

• Un camino es una secuencia de arcos en que el

extremo final de cada arco coincide

con el extremo inicial del siguiente en la secuencia.

V2 Un

camino

(en

rojo)

V1 V3

V5 V4

Caminos, ciclos y árboles

• Un camino es simple si no se repiten vértices, excepto

posiblemente el primero y el último.

Un ciclo es un camino simple y cerrado.

V2 Un ciclo (en rojo)

V1 V3

V5 V4

Un grafo es conexo si desde cualquier vértice existe un camino hasta

cualquier otro vértice del grafo.

Se dice que un grafo no dirigido es un árbol si es conexo y acíclico.

Fin