Grafos

 DLSI (Univ. Alicante)

TEMA 5
El tipo grafo

PROGRAMACIÓN Y ESTRUCTURAS DE
DATOS

 DLSI (Univ. Alicante)

Tema 5. Tipo grafo

Tipo grafo
1. Concepto de grafo y terminología
2. Especificación algebraica
3. Representación de grafos
4. Grafos dirigidos
4.1. Recorrido en profundidad o DFS
4.2. Recorrido en anchura o BFS
4.3. Grafos acíclicos dirigidos o GAD
4.4. Componentesfuertemente conexos

5. Grafos no dirigidos
5.1. Algoritmos de recorrido

2

 DLSI (Univ. Alicante)

Tema 5. Tipo grafo

1. Concepto de grafo y terminología (I)
Estructura de los grafos
cada nodo puede tener más de un sucesor y
más de un predecesor

Clasificación
MULTIGRAFO, no tiene ninguna restricción
(arcos reflexivos y múltiples ocurrencias del
mismo arco)

1

2

3DIGRAFO, no hay múltiples ocurrencias del
mismo arco

1

2

3

GRAFO NO DIRIGIDO, hay relaciones
irreflexivas y simétricas entre nodos (todos sus
arcos no orientados aristas)

1

2

3

 DLSI (Univ. Alicante)

3

Tema 5. Tipo grafo

1. Concepto de grafo y terminología (II)
Definición de grafo
Un grafo G consiste en dos conjuntos V y A donde: G=(V, A)
1) V es un conjuntofinito no vacío de vértices o nodos.
2) A es un conjunto de aristas o arcos, tales que cada arista ai de A está
identificada por un único par (vj, vk) de nodos de V, denotada por
ai = (vj, vk)

Un Arco Orientado o ARCO es aquél en que el orden de los vértices es
importante:
Arco No Orientado o ARISTA: orden de los vértices no importa.
Relaciones simétricas: (vj,vk)
El número máximo dearistas o arcos que pueden existir en un grafo de n
vértices sin contar las aristas que unen un vértice consigo mismo (vi, vi)
son:
Grafo no dirigido:
n (n-1) / 2
Grafo dirigido:
n (n-1)
4

 DLSI (Univ. Alicante)

Tema 5. Tipo grafo

1. Concepto de grafo y terminología (III)
Los vértices v1 y v2 son adyacentes si (v1,v2) es una arista en A(G), la cual
diremos que es incidente sobreambos vértices.
En el caso de grafos dirigidos será incidente a v1 y v2. Además diremos
que v1 es adyacente hacia v2, y v2 es adyacente desde v1.
Adyacencia de un vértice: es el conjunto de nodos del grafo tales que existe un
arco que los relacione:
Ay (x) = {vi ∈ V / ∃ (x, vi) ∈ A}
Para los digrafos podemos hablar de:
- Adyacencia de entrada, es el conjunto de nodos para los que hay unaarista en el
grafo que relaciona a ambos, con destino el vértice x:
AyE (x) = {vi ∈ V / ∃ ∈ A}
-Adyacencia de salida es:
AyS (x) = {vi ∈ V / ∃ ∈ A}
Grado de entrada o ingrado (gradoE): cardinal del conjunto Adyacencia de
Entrada.
Grado de salida (gradoS): cardinal del conjunto Adyacencia de Salida.
Grado de un Vértice: grado( v ) = CARD( Ay( v ) ) = gradoE + gradoS

 DLSI (Univ.Alicante)

5

Tema 5. Tipo grafo

1. Concepto de grafo y terminología (IV)
Un camino desde vp hasta vq en el grafo G es una secuencia de vértices
vp, v1,v2, ..., vn, vq tal que (vp, v1) (v1,v2), (v2, v3), ..., (vn, vq) son
aristas de A(G)
Se llama longitud de un camino al número de aristas del mismo.
Se llama camino simple a aquél en el que todos los vértices excepto el
primero y el último,son distintos
Un ciclo es un camino simple en el que el vértice primero y último
coinciden.

1

Camino 3,2,4,3
es un ciclo de longitud 3

2

3

4

Camino 3,2,4,1,4,3,
no es un ciclo
6

 DLSI (Univ. Alicante)

Tema 5. Tipo grafo

1. Concepto de grafo y terminología (V)
Un grafo no dirigido se dice que es conexo: si ∀ vi, vj ∈ V(G) existe un
camino de vi a vj en G
1

12

3

4

2

3

4

NO CONEXO

CONEXO

Un subgrafo de un grafo G=(V, A), es un grafo G’=(V’, A’) tal que V’ ⊂ V y
A’ ⊂ A
1

2

2

3

4

3

4

SUBGRAFO

Un árbol extendido de un grafo G=(V, A) es un subgrafo T= (V’, A’) de G
tal que T es un árbol y V’=V

 DLSI (Univ. Alicante)

7

Tema 5. Tipo grafo

2. Especificación algebraica (I)
MODULO GENERICO...