Grafos
Grafos
Grafos
Se puede dar un paseo pasando por todos los puentes una, y slo una, vez? Grafo: se puede dibujar sin levantar en lpiz del papel y sin repetir lneas? Desarrollo enorme en los ltimos 50 aos. Por qu?
Aplicaciones!!
4. Arquitecturas paralelas: dados k procesadores, los queremos interconectar de una manera adecuada.
Bibliografa:
K. Rosen: Matemtica Discreta y sus aplicaciones, Ed. McGrawHill, 2004.
3
Primeras deniciones
1. Un grafo es un par G = (V, E), donde V son los vrtices (o nodos) y E son las aristas (pares de vrtices). La arista entre los vrtices vi y vj la denotaremos {vi , vj }. Obs: ver un grafo de esta manera abstracta resulta muy til en la prctica. Se pueden dibujar de maneras distintas ...
4 5 3
10
15 8 7
5 1
8 0
9 4
11
0 14
15
12
10 14
11 12
13
13
14
10 8 9 4 6 13 1
12
13
15
10
11
12 0 2 14
15
11
2. Si en E no hay aristas repetidas, ni aristas de la forma {vi , vi } (lazos) diremos que el grafo es simple (en otro caso, diremos que G es un multigrafo). Si no se dice lo contrario, asumiremos que los grafos que aparecen son simples. 3. Se dice que G es un grafo dirigido (digrafo) si las aristas de G estn orientadas (de un vrtice origen a un vrtice destino). En este caso, las aristas {vi , vj } y {vj , vi } son distintas. Son necesarios en ciertas aplicaciones: programacin de tareas, diagramas de ujo.
c b b
Grafo simple
Multigrafo
Grafo dirigido
K3
K4
K5
Ciclo de n vrtices, Cn. V = {v1, v2, . . . , vn} E = {(v1, v2), (v2, v3), . . . , (vn1vn), (vn, v1)}
C3
C4
C5
011
010
Un primer resultado:
Una consecuencia directa: en cualquier grafo, hay un nmero par de vrtices de grado impar.
A Mn
aij =
1 0
G
0 1 A=1 0 0
2 3 5 4
1 0 1 1 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 0
Lista de adyacencias
2 3 5 4
v1 v2 v3 v4 v5
{v2, v3} {v1, v3, v4} {v1, v2} {v2, v5} {v4}
Ventaja: tamao proporcional a |V | + |E|. Inconveniente: a primera vista, manejo menos evidente
Ambas estructuras son fcilmente adaptables al caso de grafos dirigidos y multigrafos.
10
2 G
Formalmente:
b H
G y H son isomorfos si existe una biyeccin f : VG VH tal que {vi , vj } EG {f (vi ), f (vj )} EH Notacin: G H .
Es fcil pensar en muchas condiciones necesarias: 1. Igual nmero de vrtices y aristas 2. La secuencia de grados es la ordenacin creciente de los grados de los vrtices (v1 ), (v2 ), . . . , (vn ). Dos grafos isomorfos deben tener la misma sucesin de grados.
No es suciente ...
11
subgrafo
grafo G
Gu
12
u v
u v
recorrido
camino
camino simple
ciclo
13
Un grafo G es conexo si para cualquier par de vrtices existe un recorrido que los conecta. (Si el grafo es dirigido, hay que tener en cuenta la orientacin de las aristas) La distancia d(u, v) entre dos vrtices u y v es la longitud del recorrido ms corto que los conecta.
Obs: d es una distancia Obs: El recorrido ms corto entre dos vrtices u y v es siempre un
camino (es decir, no repite vrtices).
bipartido
es bipartido?
14
G es bipartido
P2
(X, Y ) es biparticin. Si no lo fuera, v, w en X (o en Y ), conectados. P1 el camino mnimo de u a v , P2 cam. min. de u a w. longitud de P1 P2 ?? Ojo: P1 P2 no tiene por qu ser un ciclo. Sea x el ltimo vrtice comn a P1 y P2 . Repetir argumento con los caminos de x a v, arista v,w, camino w,x.
gido) con vrtices V = {v1 , . . . , vn} y matriz de adyacencia A. El nmero de recorridos de longitud k entre los vrtices vi y vj es el coeciente (i, j) de la matriz Ak .
15
Conectividad
conexo
ms conexo a
Se dice que un grafo G es k-conexo si al eliminar menos de k vrtices (y las aristas adyacentes) el grafo sigue siendo conexo (o queda reducido al vaco). Obs: en redes, se dice que una red es tolerante a fallos si, para todo par de vrtices u, v existen, al menos, dos caminos alternativos entre u y v . (Esto es claramente equivalente a que cualquier par de vrtices u, v est contenido en un ciclo.) Veamos que esto es equivalente a que el grafo sea 2-conexo (es decir, que siga siendo conexo si falla un solo vrtice). Se dice que dos caminos entre u y v son disjuntos si no tienen vrtices ni aristas en comn (excepto, claro, u y v ). (A veces se habla de internamente disjuntos).
16
menos, 3 vrtices. G es 2-conexo si y slo si dados dos vrtices distintos u, v V existen al menos dos caminos disjuntos que los conectan.
Dem: (1) Si G no es 2-conexo, existe w t.q. G w no conexo. x, y no conectados en G w. Los caminos de x a y en G pasan por w. No hay dos caminos disjuntos de x e y . (2) Sabemos G 2-conexo. caminos disjuntos de x a y ?
R P R x Q w e x Q z y P R z
R y e w Q
Obs: Dos vrtices u y v estn unidos por dos caminos disjuntos si y slo si estn contenidos en un ciclo. Por tanto, el teorema de Whitney se puede formular tambin de esta forma: menos, 3 vrtices. G es 2-conexo si y slo si dos vrtices distintos cualesquiera estn contenidos en un ciclo.
17
2-conexo
2-conexo
18