Representación y manipulación de grafos:

caminos, expansión, cortes y flujos

Grafos

Grafos

Un grafo G es un par de conjuntos G = (V,E)

V = un conjunto de n vertices u, v, w ! V

E = un conjunto de m aristas|V | = n, |E| = m

Teorıa de grafos– p. 2

VISUALIZACION DE UN GRAFO

n = |V | = 8, m = |E| = 10

Aristas Aristas

Las aristas son típicamente pares de vertices, {u, v} ! E

E " V # V

También se puede definir grafos donde el producto esentre más de dos “copias” del conjunto V , el cual caso sehabla de hıpergrafos.

Teorıa de grafos– p. 3

Definiciones

Complemento

El complemento de G = (V,E) es un grafo G = (V, E)donde

!v "= u :!

{v, u} # E $ {v, u} /# E"

.

Teorıa de grafos– p. 4

Grafos especiales

Un grafo es plano si se puede dibujar en dos dimensionesasí que ninguna arista cruza a otra arista.En un grafo no dirigido, los vértices v y w tienen unpapel igual en la arista {v, u}.Si las aristas tienen dirección, G es dirigido (tambiéndigrafo).En una arista dirigida !v, w":

v es el origen (o inicio) de la aristaw es el destino (o fin) de la arista

Teorıa de grafos– p. 5

Grafos reflexivos

Un bucle es una arista reflexiva, donde coinciden elvértice de origen y el vértice de destino: {v, v} o !v, v".Si un grafo G no cuente con ningún bucle, el grafo es noreflexivo.

Teorıa de grafos– p. 6

Otras clases de grafosMás clases de grafos

E podría ser un multiconjunto: más de una arista entre unpar de vértices.Si no se permiten aristas múltiples, el grafo es simple.Si se asignan pesos ! (v, w) a las aristas, el grafo esponderado.Si se asigna identidad a los vértices o las aristas, el grafoes etiquetado.

Teorıa de grafos– p. 7

AdyacenciaVecinos

v y w son adyacentes si una arista los une:{v, w} ! E.

Vértices adyacentes son llamados vecinos.El conjunto de vecinos de v es su vecindario, ! (v).

Teorıa de grafos– p. 9

Álgebra de grafos

Un grafo se puede representar con una matriz:

1 3 9 7 82 6 3 0 13 3 0 0 24 9 1 9 00 0 2 7 3

2

63

0 1

Av = λvuA = λu

El espectro de la matriz (o algún variante suyo) revela propiedades y comportamientos del sistema modelado:

Agrupamiento espectral Matriz de adyacencia

Matriz de adyacencia

La matriz A que corresponde a la relación E se llama lamatriz de adyacencia del grafo.Es necesario etiquetar los vértices para que seanidentificados como v1, v2, . . . , vn.

Para un grafo no dirigido A es simetricaMultigrafos: una matriz entera A! donde a!ij ! 0 es elnúmero de aristas entre vi y vj

Grafos ponderados: una matriz (real) A!! donde a!!ij es elpeso de la arista {vi, vj} o cero si no hay tal arista

Teorıa de grafos– p. 10

Matriz de adyacencia

Un grafo G = (V,E) de n vértices etiquetados 1, 2, 3, . . . , n.Usar la matriz de adyacencia es eficiente sólo cuando Ges bastantea denso.La matriz ocupa O (n2) elementos y si m es mucho menorque n2, la mayoría del espacio reservado tiene el valorcero.

aSi estuviera muy denso, serıa mejor guardar su complemento.

Grafos– p. 2

No ordenada

Ordenada por grupos

Listas de adyacencia

Listas de adyacencia

Se necesita un arreglo a[], cada elemento de cuál es unalista de largo dinamico.La lista de a[i] contiene las etiquetas de cada uno de losvecinos del vértice i.El tamaño de la estructura de listas de adyacencia esO (n + m) ! O (m) = O (n2) (aunque en muchos casos esmucho menor).Esto es muy parecido al implementar un grafo como una estructura enlazada, conpunteros a todos los vecinos de cada vértice.

Grafos– p. 3

GradoGrado

El grado deg (v) es el número de aristas incidentes a v.Grafos dirigidos:

grado de salida !"deg (v) = el número de aristas que

tienen su origen en v

grado de entrada#!deg (v) = el número de aristas que

tienen su destino en v

El grado total de un vértice de un grafo dirigido es

deg (v) =#!deg (v) +

!"deg (v) .

Teorıa de grafos– p. 11

EJEMPLO: GRADOS

4

33

4

2

1

2

3

Propiedades especiales

Más sobre grados

En un grafo simple no dirigido, el grado deg (vi) del vérticevi es la suma de la ijesima fila deA.

!

v!V

deg (v) = 2m

En un grafo simple no reflexivo: deg (v) = |! (v)|

Si todos los grados son k, el grafo es k-regularUn grafo n ! 1-regular se llama un grafo completoKn

Teorıa de grafos– p. 12

DensidadDensidad

El número máximo posible de aristas en un grafo simple es

mmax =

!

n

2

"

=n(n ! 1)

2.

Para Kn, tenemos m = mmax.Densidad:

! (G) =m

mmax

=m#

n2

$ .

Un grafo denso tiene ! (G) " 1 y un grafo escaso tiene! (G) # 1.

Teorıa de grafos– p. 14

Grafos bipartitosGrafos bipartitos

Un grafo bipartito es un grafo G = (V,E) cuyos vérticesse pueden separar en dos conjuntos

U ! W = ", U # W = V

así que

{u,w} $ E % (u $ U & w $ W ) ' (u $ W & w $ U).

Grafo bipartito completo: están presentes todas lasaristas permitidas, K|U |,|W |.

Teorıa de grafos– p. 13

EJEMPLO: GRAFO BIPARTITO

b

a

E

c

Fe

D

e

c

b

a AA B

d

D

C

d

F

E

C

B

Los vertices azules son U y los verdes V . Los dos dibujosrepresentan exactamente el mismo grafo — lo unico que cambiason las ubicaciones de las vertices.

Caminos y distanciasCaminos y distancias

Una sucesión de aristas adyacentes que empieza en vy termina en w es un camino de v a w.El largo de un camino es el número de aristas quecontiene.La distancia dist (v, w) entre v y w es el largo mínimode todos los caminos de v a w.La distancia de un vértice a si mismo es cero.El diametro diam (G) de G es la distancia máxima

diam (G) = maxv!V

w!V

dist (v, w) .

Teorıa de grafos– p. 15

Ciclos Ciclos

Un camino simple solamente recorre la misma arista unavez máximo.Un ciclo es un camino que regresa a su vértice inicial. Ungrafo que no cuente con ningún ciclo es acíclico.Entonces, un ciclo simple empieza y regresa del mismovértice, pero no visita a ningún otro vértice dos veces.Sin embargo, la elección del punto de inicio de un ciclo esarbitrario.

Teorıa de grafos– p. 16

ConectividadConectividad

G es conexo si cada par de vértices está conectado porun camino.Si por algunos v y w no existe ningún camino, grafo es noconexo.G es fuertemente conexo si cada par de vértices estáconectado por al menos dos caminos disjuntos.Un grafo no conexo se puede dividir en dos o máscomponentes conexos que son formados por talesconjuntos de vértices de distancia definida.

Teorıa de grafos– p. 17

Subgrafos Subgrafos

G(S) = (S, F ) es un subgrafo de G = (V,E) si S ! V yF ! E tal que

{v, w} " F #!

(v " S) $ (w " S)"

.

Si el subgrafo contiene todas las aristas posibles, es unsubgrafo inducido por el conjunto S.Un subgrafo que completo se dice una camarilla (inglés:clique).

Teorıa de grafos– p. 18

Árboles = grafos especialesÁrboles

Un arbol es un grafo conexo acíclico.Un arbol cubriente de G = (V,E) es un subgrafo que esun árbol y contiene todos los vértices de G.Si el grafo es ponderado, el árbol cubrientemınimo escualquier árbol donde la suma de los pesos de sus aristases mínima.Un grafo G no conexo es un bosque si cada componenteconexo de G es un árbol.

Teorıa de grafos– p. 19

Ejemplos EJEMPLOS

A

B

En azul: un arbol cubriente. En verde: un 7-ciclo. Los vertices rojosestan en el camino mas corto de A a B con largo 3. El diametrodel grafo es cuatro.

Tarea en clase

¿Qué tienen en común estos tres grafos?

Teorıa de grafos– p. 20

Isomorfia

Búsqueda y recorridosBúsqueda y recorrido

Recorrido = el proceso de aplicación de un métodosistemático para visitar cada vertice

Busqueda = un método sistemático para recorrer un grafode entrada G = (V,E) con el propósito de encontrarun vertice del G que tenga una cierta propiedad

Estos algoritmos comúnmente utilizan colas o pilas.

Grafos– p. 4

Búsqueda en profundidad de v(Depth-first search)

Búsqueda en profundidad (DFS)

Dado G y un vértice inicial v ! V1. Crea una cola vacía L

2. Asigna u := v

3. Marca u visitado

4. Añade los vecinos no marcados de v al comienzo de L

5. Quita del comienzo de L todos los vértices marcados

6. Si L está vacía, termina

7. Asigna u := el primer vértice en L

8. Quita el primer vértice de L

9. Continua de paso (3)Grafos– p. 6

Versión recursiva del DFS

Preorden y postorden

dfs(v,G,L) {L := L ! {v}preorden: imprimirvpara todo w " ! (v) \ L :

dfs(w,G,L).postorden: imprimirv

}

Grafos– p. 9

Ejemplo del DFSEJEMPLO: DFS

DFS puede progresar en varias maneras; el orden de visitasdepende de como se elige a cual vecino se va. Algunas aristasencontradas apuntan a vertices ya visitados.

Búsqueda en anchura (BFS)

1. crea una cola vacía L

2. asigna u := v

3. marca u visitado4. añade cada vértice no marcado en ! (v) al fin de L

5. si L está vacía, termina6. asigna u := el primer vértice en L

7. continua de paso (3)

Grafos– p. 48

Búsqueda por ancho de v(Breadth-first search)

Ejemplo del BFSEJEMPLO: BFS

Empezando del vertice rojo, la busqueda primero visita todos losvertices amarillos, despues los verdes, y por ultimo el azul.Algunas aristas encontradas apuntan a vertices ya visitados.

Flujos en redes

EJEMPLO: FLUJO DE AGUACERO DE POR CLOACAS

Se necesita determinar cual es el flujo maximo de agua por unsistema de cloacas. Para cada canal, se conoce la capacidad enmetros cubicos por segundo:

4

2 6

2

57

4

3

2

63

73

2 6

53 4

8

1

62

1416

2

8

2 2

Modelado a través de grafosEJEMPLO: GRAFO DE LAS CLOACAS

7+2 = 9

4+8 = 12

2+6 = 8

8+3 = 117+2 = 9

3+5 = 8

M

M

M

5

6

62

2

2

4

6

6

1

42

4

1

2

1

3

3

M es un constante mucho mas grande que ninguna capacidad(por ejemplo M = 200 sirve bien).

Modelado a través de grafosEJEMPLO: FLUJO MAXIMO

5/M

3/12

0/8

6/118/9

5/9

3/8

6/M

0/M

4/4

2/2

1/2

0/1

1/4

5/5

6/6

0/6

3/4

2/20/6

2/2 0/61/1

0/3

3/3

0/1

0/2

Se puede identificar partes criticas con congestion y partes inutilespara seleccionar donde mejorar la construccion.

Modelo generalEJEMPLO: UNA RED DE FLUJO

1

2

3

3

2

32

1

3

2

22

3

4

1

15 4

2

3

3

1

2

46

31

4

3

SumideroFuente

1

2

Los vertices grises son el fuente y el sumidero. Se muestra lacapacidad de cada arista.

Aplicaciones de flujosEJEMPLO: MODELO DE FLUJOS

Un vertice por familia, un vertice por carro. Los flujos representanlas cantidades de personas.

74

44

511

4

46

5

C

G

H

J C

C

C

SS

M

Capacidad = 2 ¡Flujos deben tener valores enteros!

Aplicaciones de flujos

EJEMPLO: COSTOS, CAPACIDADES, DEMANDAS

Las 12 rutas ri (grises) existentes con sus costos por unidad ci

asociados, las capacidades de las fabricas y las demandas de losvendedores:

1

1

1

2

1

3

2

1

3

1

1

1

200

250

50

100

200

350

150

Transporte vs. transbordoEJEMPLO: TRANSPORTE VS. TRANSBORDO

Transporte Transbordo

En un problema de transporte, la entrega es directa. En problemasde transbordo, las rutas con mas complejas.

CortesEJEMPLO: CORTES

Cuatro cortes y sus capacidades:

1

3

3

2

32

1

3

2

22

3

4

1

15 4

2

3

3

1

2

46

31

4

3

514

2

1915

1

2

Ciclo hamiltonianoRUTEO: PROBLEMA DEL VIAJANTE

Encontrar un ciclo que visita cada vertice exactamente una vez.

b

a n

m

l

i

f

h

j

k

g

e

d

c

Variaciones: aristas ponderadas, un camino en vez de un ciclo,premios en los vertices, etcetera.

Ciclo eulerianoRUTEO: PROBLEMA DEL CARTERO CHINO

Encontrar un ciclo que visita cada arista por lo menos una vez.

24

25 5

6

11

14

1712 16

15

2123

9

1041

19

23

13

22

8

720

18

Variaciones: aristas ponderadas, pesos no simetricos, premios enla aristas, rutas mas profitables.

AcoplamientoEJEMPLO: ACOPLAMIENTO

Las aristas gruesas negras forman el acoplamiento y los verticesazules estan acoplados.

Cubiertas

EJEMPLO: CUBIERTAS

Los vertices verdes cubren todas las aristas y las aristas amarillascubren todos los vertices.

ColoreoPROBLEMAS COMBINATORIOS: COLOREO

El problema de asignar colores a los vertices ası que ningunaarista conecta vertices del mismo color y que el numero de coloresutilizados es mınimo.

Tenemos un 4-coloreo — ¿existe un 3-coloreo?

CLIQUE & IDSETPROBLEMAS COMBINATORIOS: CLIQUE

El problema de identificar el clique maximo, es decir, subgrafocompleto de orden maximo.

El complemento de un clique es un conjunto independiente, osea, un subgrafo sin aristas.