Download GRAFOS

GRAFOS
HUGO ARAYA CARRASCO
1
GRAFOS
• Un grafo G es un par (V,E) donde V es un conjunto
(llamado conjunto de vértices o nodos) y E un
subconjunto de VxV (conjunto de aristas).
• Gráficamente representaremos los vértices por puntos y
las aristas por líneas que los unen.
• Un vértice puede tener 0 o más aristas, pero toda arista
debe unir exactamente 2 vértices.
• Llamaremos orden de un grafo a su número de vértices,
|V|.
• Si |V| es finito se dice que el grafo es finito.
• Toda arista une dos vértices distintos
2
ARISTAS y VERTICES
• Si la arista carece de dirección se denota
indistintamente {a,b} o {b,a}, siendo a y b los vértices
que une.
• Si {a,b} es una arista, a los vértices a y b se les llama
sus extremos.
• Dos vértices v, w se dice que son adyacentes si {v,w}V
(o sea, si existe una arista entre ellos)
• Llamaremos grado de un vértice al número de aristas de
las que es extremo. Se dice que un vértice es ‘par’ o
‘impar’ según lo sea su grado.
3
CAMINOS
• Sean x, y  V, se dice que hay un camino en G de x a y
si existe una sucesión finita no vacía de aristas {x,v1},
{v1,v2},..., {vn,y}. En este caso.
–
–
–
–
x e y se llaman los extremos del camino
El número de aristas del camino se llama la longitud del camino
Si los vértices no se repiten el camino se dice propio o simple.
Si hay un camino no simple entre 2 vértices, también habrá un
camino simple entre ellos
– Cuando los dos extremos de un camino son iguales, el camino
se llama circuito o camino cerrado o ciclo (sin aristas repetidas).
– Llamaremos ciclo a un circuito simple (no existen vertices
repetidos excepto el primero y el ultimo)
– Un vértice a se dice accesible desde el vértice b si existe un
camino entre ellos. Todo vértice es accesible respecto a si
mismo
4
EJEMPLOS DE GRAFOS
• Grafo regular: Aquel con el
mismo grado en todos los
vértices. Si ese grado es k lo
llamaremos k-regular.
5
EJEMPLOS DE GRAFOS
• Grafo bipartito: Es aquel con cuyos vértices pueden formarse
dos conjuntos disjuntos de modo que no haya adyacencias entre
vértices pertenecientes al mismo conjunto
6
EJEMPLO DE GRAFOS
• Grafo completo: Aquel con una arista entre cada par de vértices. Un
grafo completo con n vértices se denota Kn.
7
EJEMPLOS DE GRAFOS
• Todo grafo completo es regular porque cada vértice tiene grado
|V|-1 al estar conectado con todos los otros vértices.
• Un grafo regular no tiene por qué ser completo
• Un grafo bipartido regular se denota Km,n donde m, n es el grado
de cada conjunto disjunto de vértices.
• A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
8
MATRIZ DE ADYACENCIA
• La suma de los grados de los vértices es igual al doble
del número de aristas
• Sea G un grafo de orden n. Llamaremos matriz de
adyacencia de G a la matriz nxn que llamaremos A = (aij)
donde aij = 1 si {i,j}A y aij = 0 en otro caso.
• La matriz de adyacencia siempre es simétrica porque aij
= aji
v1
v2
v3
v4
v5
v1
0
1
1
0
0
v2
1
0
1
1
0
v3
1
1
0
1
1
v4
0
1
1
0
0
v5
0
0
1
0
0
9
GRAFOS
• Sea G un grafo de n vértices con n > 1 y sea A su matriz
de adyacencia. Se cumple que el valor del coeficiente ai,j
de la matriz Ak es igual al número de caminos de
longitud k con extremos vi y vj
• Si existe un camino de longitud m (m  n) entre 2
vértices cualquiera, entonces existe un camino de
longitud  n-1 entre esos dos vértices.
• Un grafo G se dice conexo si cada par de vértices está
unido al menos por un camino.
• Una arista de un grafo G se dice de separación si G es
conexo pero al suprimir la arista se divide en dos
componentes conexos
10
GRAFOS
• Un método para comprobar si un grafo es conexo es el siguiente:
– Se halla la matriz de adyacencia y se eleva a la (n-1)-ésima
potencia
– Se calcula la suma de las potencias de A hasta An-1
– Si todos sus elementos son  0, el grafo es conexo.
• Dados dos grafos G = (V, E) y G´ = (V´, E´), se denomina
isomorfismo entre G y G´ a cualquier aplicación biyectiva f:G 
G’ tal que si a, b  V, entonces {a,b}E  {f(a),f(b)}E´.
11
Grafos Eulerianos y Hamiltonianos
•
•
•
Llamaremos camino euleriano a un camino que contiene a todas las
aristas del grafo, apareciendo cada una exactamente una vez.
Un ciclo euleriano es un camino euleriano que comienza y acaba en el
mismo vértice.
Un grafo que admite un ciclo euleriano diremos que es un grafo
euleriano.
12
Grafos Eulerrianos y Hamiltonianos
• Si un grafo está formado por dos subgrafos
eulerianos unidos al menos por un vértice y sin
aristas en común, entonces es euleriano.
• Un grafo conexo G=(V,A) es euleriano  todo
vértice tiene grado par.
• Un grafo conexo tiene un camino abierto
euleriano  tiene exactamente dos vértices de
grado impar.
13
Puentes de Konigsberg
• El problema consiste en partir de cualquier lugar ,
caminar sobre cada puente exactamente una vez y
luego regresar a la posición inicial.
14
Algoritmo de Fleury
• Si G es un grafo euleriano siempre es
posible seguir la siguiente construcción de
un circuito euleriano. Se empieza por un
vértice arbitrario y se recorren las aristas
arbitrariamente sometida a dos
condiciones:
– Se borran las aristas a medida que son
atravesadas
– Solo se recorre una arista de separación si no
queda otra alternativa
15
Caminos Hamiltonianos
• Un camino hamiltoniano es un camino que recorre todos
los vértices de un grafo sin pasar dos veces por el
mismo vértice.
• Si el camino es cerrado se dice un ciclo hamiltoniano
• Un grafo G se dice hamiltoniano si tiene un ciclo
hamiltoniano.
• A diferencia de los grafos eulerianos, no hay una
caracterización de cuando un grafo tiene un ciclo o un
camino hamiltoniano.
• Si un grafo es conexo con |V|3 y para cada par de
vértices la suma de sus grados es mayor o igual que el
número de vértices entonces es hamiltoniano.
16
Problema del Vendedor Viajero
En un grafo G con pesos se pretende
encontrar un ciclo que pase por todos los
vértices de forma que la suma de los
pesos de las aristas escogidas para
formar el ciclo sea lo menor posible.
17
Ruta mas corta
Un grafo con pesos es un grafo en el cual
se asignan valores a las aristas y que la
longitud de un camino en un grafo con
pesos es la suma de los pesos de las
aristas en el camino. Con frecuencia se
desea determinar la ruta mas corta entre
dos vértices dados. Dijkstra escribió el
algoritmo que resuelve este problema.
18
Algoritmo de Dijkstra
•
•
•
•
•
•
•
•
•
•
Suponemos que los pesos son números positivos.
Se desea determinar el camino mas corto de a hasta z.
El grafo es conexo.
Sea L(v) la etiqueta del vértice v.
En algún momento algunos vértices tienen etiquetas
temporales y otros permanentes.
Sea T el conjunto de tienen etiquetas temporales.
En principio todos los vértices tienen etiquetas
temporales.
En cada iteración el algoritmo modifica el estado de una
etiqueta de temporal a permanente.
El algoritmo concluye cuando z recibe una etiqueta
permanente, L(z) proporciona la longitud mínima de a
hasta z.
El peso de la arista (i,j) es w(i,j)
19
Algoritmo de Dijkstra
Procedure dijkstra(w, a, z, L)
L(a)=0
For todos los vértices x != a do
L(x) = infinito
T = conjunto de todos los vértices
// T es el conjunto de vértices cuya distancia mas corta a
“a” no ha sido determinada
While z pertenece T do
elegir v en T con L(v) mínimo
T = T-{v}
for cada x en T adyacente a v do
L(x) = min{L(x),L(v) + w(v,x)}
end
end
20
ARBOLES
• Un grafo se dice un árbol si es conexo y no
tiene ciclos.
• Los primeros dos grafos son árboles:
21
ARBOLES
• Por tanto, un grafo es un árbol  entre cada par de
vértices existe un camino y sólo uno.
• Un grafo se dice un bosque si sus componentes
conexas son árboles.
• Teorema.- Sea G(V,E) un grafo. Son equivalentes
a) G es un árbol
b) Cada par de vértices distintos de V esta conectado
por un único camino.
c) G es conexo y toda arista de G es de separación
d) G no tiene ciclos y |V| = |E| + 1
e) G es conexo y |V| = |E| + 1
f) G no tiene ciclos pero al añadirle una arista a G se
crea un único circuito
22
ARBOL GENERADOR
• Definición.- Sea G un grafo, un árbol generador de G es
un subgrafo conexo de G que tiene los mismos vértices
que G y no tiene circuitos.
23
ARBOL GENERADOR
• Supongamos que a cada arista se le asocia un número
positivo (su peso). Un árbol generador se dice de peso
mínimo si la suma de los pesos de las aristas que lo
componen es lo menor posible
• Para calcular el árbol de peso mínimo existen 2
algoritmos:
– Kruskal: Se van escogiendo las aristas de menor
peso hasta conseguir un árbol de peso mínimo
– Prim: Consiste en ir borrando las aristas de mayor
peso posible y que no sean aristas de separación.
• Puede haber más de un árbol generador de peso
mínimo, pero todos deben tener el mismo peso.
24
ALGORITMO DE PRIM
La idea básica consiste en añadir, en cada paso, una arista
de peso mínimo a un árbol previamente construido. Más
explícitamente:
Paso 1. Se elige un vértice u de G y se considera el árbol
S={u}
Paso 2. Se considera la arista e de mínimo peso que une un
vértice de S y un vértice que no es de S, y se hace S=S+e
Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina.
En caso contrario se vuelve al paso 2
25
ALGORITMO DE PRIM
26
ALGORITMO DE PRIM
27
ALGORITMO DE KRUSKAL
• La idea básica consiste en elegir sucesivamente las aristas
de mínimo peso sin formar ciclos.
• Paso 1. Se elige la arista de mínimo peso e y se considera
S={e}.
• Paso 2. Sea e’ la arista de mínimo peso tal que e’ÏS y S+e'
es un grafo acíclico. Se hace S=S+e'.
• Paso 3. Si S tiene n-1 aristas, el algoritmo termina. En
caso contrario se vuelve al paso 2.
28
ALGORITMO DE KRUSKAL
29
ALGORITMO DE KRUSKAL
30