Grafos

Grafos

GRAFOS
1. DEFINICIONES
1.1. Adyacencias
1.2. Caminos
1.3. Conectividad
1.4. Algunos grafos particulares
2. IMPLEMENTACIONES.
2.1. Matrices de adyacencia
2.2. Listas y multilistas de adyacencia
2.3. El problema de la celebridad
3. ALGORITMOS SOBRE GRAFOS
3.1. Recorrido en profundidad
3.1.1. Conectividad
3.1.2. Numerar vértices
3.1.3. Árbol asociado al recorrido enprofundidad
3.1.4. Test de ciclicidad
3.1.5. Puntos de articulación
3.1.6. Componentes fuertemente conexas
3.2. Recorrido en anchura
3.2.1. Algunas aplicaciones particulares
3.3. Ordenación topológica
LAS FUENTES



Grafos

GRAFOS

1. DEFINICIONES
El lector o lectora ya conocen el tipo de datos grafo porque ha sido introducido en
otras asignaturas que preceden a ésta. Esta sección se va adedicar a recordar la
terminología que se emplea con ellos. En general, un grafo se utiliza para
representar relaciones arbitrarias entre objetos del mismo tipo. Los objetos reciben
el nombre de nodos o vértices y las relaciones entre ellos se denominan aristas. El
grafo G, formado por el conjunto de vértices V y por el conjunto de aristas E, se
denota por el par G=.
Habitualmentedistinguimos entre grafos dirigidos y no dirigidos, dependiendo de si
las aristas están orientadas o no lo están, y entre grafos etiquetados o no
etiquetados en función de si las aristas tienen o no información asociada.
Gráficamente (los círculos representan los vértices y las líneas que los unen
representan las aristas):
1

7

a

2

2

3
4

5

Grafo no dirigido y no etiquetado

bc

1

5
2

d

Grafo dirigido y etiquetado

El tipo grafo que vamos a usar no permite aristas ‘lazo’ (una arista en que el mismo
vértice es origen y destino), ni tampoco ‘multiaristas’ (dados dos vértices existe
entre ellos más de una arista en el mismo sentido). Las operaciones que vamos a
manejar van a ser las habituales de los conjuntos (crear, insertar elemento, eliminarelemento) sabiendo que tenemos elementos de dos tipos: vértices y aristas, y


Grafos

operaciones específicas como grado, sucesores, adyacentes, etc. No seremos
excesivamente rigurosos y haremos todas las salvedades que nos convengan para
no tener que entrar en grandes detalles de implementación.
1.1. Adyacencias
Sea G= un grafo NO DIRIGIDO. Sea v un vértice de G, v∈V. Se define:
- adyacentesde v,
(v) = { v' V | (v,v' E }
∈
)∈
- grado de v,
( v) = |
(v) |. Si un vértice está aislado, su grado es cero.
Sea G= un grafo DIRIGIDO. Sea v un vértice de G, v∈V. Se define:
- sucesores de v,
(v) = { v' V | (v,v' E }
∈
)∈
- predecesores de v,
(v) = { v' V | (v' )∈E }
∈
,v
- adyacentes de v,
( v) =
(v)∪
(v)
- grado de v,
( v) = | |
- grado de entrada de v ,
- grado desalida de v,

(v)| - |
(v)| |
( v) = |
(v)|
( v) = |
(v)|

1.2. Caminos
Un CAMINO de longitud n≥0 en un grafo G= es una sucesión {v0,v1, ...,vn } tal
que :
- todos los elementos de la sucesión son vértices, es decir, ∀i: 0≤i≤n : vi∈V, y
- existe arista entre todo par de vértices consecutivos en la sucesión, o sea,
∀i: 0≤i0. Equivale a que, como mínimo, hay dos vértices en la secuencia
y,por tanto, su longitud es ≥ 1.
- es ABIERTO si v0≠vn
- es CERRADO si v0=vn
- es SIMPLE si no se repiten aristas
- es ELEMENTAL si no se repiten vértices, excepto quizás los extremos. Todo camino
elemental es simple.
Un CICLO ELEMENTAL es un camino cerrado, propio y elemental, es decir, es una
secuencia de vértices, de longitud mayor que 0, en la que coinciden los extremos y
no se repitenni aristas ni vértices.


Grafos

1. 3. Conectividad
Sea G= un grafo NO DIRIGIDO. Se dice que:
- es CONEXO si existe camino entre todo par de vértices.
- es un BOSQUE si no contiene ciclos
- es un ARBOL NO DIRIGIDO si es un bosque conexo
Un SUBGRAFO H= del grafo G, es el grafo H tal que U⊆V y F⊆E y F⊆UxU.
Un ARBOL LIBRE del grafo G es un subgrafo, H=, tal que es un árbol no dirigido...