Grafos

Teoría de Grafos
Curso 2006-2007

Introducción
Grafos: modelos matemáticos de situaciones reales Ejemplos:
Mapa de carreteras, plano de metro, callejero, red de PCs, plano de un circuito eléctrico, árboles genealógicos, etc.

Aplicaciones:
Compiladores y traductores, Redes, Planificación, etc.

Origen: 1736 (Los Puentes de Könisberg. Euler)

1

Índice
• • • • • • Conceptos básicosy representación Accesibilidad y conexión Grafos y relaciones Caminos Eulerianos y Hamiltonianos Árboles Planaridad y coloreado

Conceptos básicos
• Un Grafo G es una terna (V,A,p) formada por dos conjuntos V (de vértices) y A (de arcos) y una aplicación p: A → P2(V) (de incidencia)
– p(a) = {u, v}. (u, v son los extremos del arco a) – p(a) = {u} (a es un bucle)

• Un Digrafo D = (V,A,p)dónde p: A → V×V
– p(a) = (u, v) (u es el extremo inicial u origen de a v es el extremo final o destino de a) – p(a) = (u, u) (a es un bucle)

2

Representaciones de un grafo
Representación gráfica
v1 a5 v5 a4 a8 v4 a3 v3 a5 a6 a7 a2 a6 a1 v2 v1 v2 a8 v3 a3 v4 a7 a4 v5

a1

a2

Conceptos básicos
Un Grafo/digrafo G=(V,A,p) es Simple si p es inyectiva Un vértice que no es extremo deningún arco es un vértice aislado. Grafo nulo: todos los vértices son aislados

3

Conceptos básicos
Si D un digrafo y cada arco se considera no dirigido se obtiene un Grafo asociado a D, G(D) Si G es un grafo y por cada arco a con p(a)={u,v} (u ≠ v) se consideran a1 y a2 con p(a1) = (u,v) y p(a2) = (v,u) se obtiene un Digrafo asociado a G, D(G).
(Si p(a) = {u}, se sustituye por p(a) = (u,u))Grafos finitos

Conceptos básicos
G’ = (V’, A’, p’) es subgrafo de G = (V,A,p) si:
G’ es un grafo V’⊆V, A’ ⊆A y p’= p|A’

Subgrafo determinado por:
A’⊆A, G(A’) = (V’, A’, p|A’) V’ extremos de los arcos de A’ V’⊆V, G(V’) = (V’, A’, p|A’) A’ arcos que unen nodos de V’ Subgrafo estrellado determinado por v∈V, G(v)= (Vv, Av, p|Av) Av

arcos emergentes de v (tales que un extremo es v) y Vvextremos de los arcos de Av (además de v)

G1∪G2. G1∩G2

4

Representaciones de un grafo
Matriz de Adyacencia
G= (V, A, p) con V = {v1,..., vn} Ma(G) = (aij) : i,j = 1..n
aij = número de arcos de extremos {vi, vj}/ (vi, vj)

a4 v1 a1 a2 a5 v2 a3 v3 v5 v4 a6

⎛0 ⎜ ⎜2 M (G ) = ⎜ 0 ⎜ ⎜0 ⎜0 ⎝

2 0 1 0 0

0 1 0 0 0

0 0 0 1 2

0⎞ ⎟ 0⎟ 0⎟ ⎟ 2⎟ 0⎟ ⎠

Accesibilidad y conexión
Uncamino en G es una sucesión
v0 a1 v1 a2 v2....an vn (n≥0) tal que los extremos (inicial y final) del arco ai son vi-1 y vi, con i = 1 .. n • n es la longitud del camino • v0 y vn son los extremos (inicial y final) • v1, ..., vn-1 son los vértices interiores • Representaciones alternativas:
– a1 a2 ....an
– v0 v1 v2.... vn sólo si G es simple

5

Accesibilidad y conexión II
Un camino v0 a1 v1a2 v2....an vn es
– cerrado si v0 = vn – simple si sus arcos son distintos dos a dos – elemental si sus vértices son distintos dos a dos salvo, a lo sumo, los extremos – ciclo si es cerrado, elemental, simple y de longitud positiva (>0)

Accesibilidad (D digrafo)
Sean u y v vértices de D.
– v es accesible desde u sii existe un camino en D desde u hasta v – v es k-accesible desde u sii existeun camino en D de longitud k de u a v

Matriz de accesibilidad de orden k de D, Mk, es una
matriz booleana:
( mijk ) = 1 ⇔ v j es k − accesible desde vi

D*: Mady(D*) = M1 (= M), grafo simple asociado a D

6

Accesibilidad II
Mk = M ⊗ Mk-1 (k > 1)
k (⊗: producto booleano de matrices)

vi

vj

vi

vr

k-1

vj

Mk = Mk (k ≥ 1)

(potencia booleana)

Matriz deaccesibilidad de D, M(D)
mij = 1 ⇔ v j es accesible desde vi

Accesibilidad III
M(D) = I ⊕ ∑r≥1 Mr
Veamos que es suficiente con calcular un nº finito de potencias

D= (V, A, p), n= |V|; vi ≠ vj ∈V : vj es m-accesible desde vi para algún m≥1 ⇔ vj es k-accesible desde vi para algún 1≤k ≤ n-1
[hay un camino de u a v ⇔ hay un camino elemental de u a v]

vi

w

vj

7

Accesibilidad IV...