Teoria De Grafos Y Redes 5d6dh

T EOR´I A

DE GRAFOS Y REDES

E LISA S CHAEFFER Programa de Posgrado en Ingenier´ıa de Sistemas (P ISIS ) [email protected]

´ I NVESTIGACI ON

DE

O PERACIONES

´ D EFINICIONES B ASICAS Grafo G = (V, E) ´ (o sea, nodos), u, v, w ∈ V V = un conjunto de n vertices E = un conjunto de aristas m (o sea, arcos) conectando pares de ´ vertices, (u, v) ∈ E ´ |V | = n, |E| = m Notacion:

´ DE UN GRAFO V ISUALIZACI ON

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

C ASOS ESPECIALES ´ G es dirigido si las aristas tienen direccion, ´ un bucle es una arista reflexiva donde coinciden el vertice inicio y el fin ´ de una E puede ser un multiconjunto, pudiendo haber mas ´ arista entre cada par de vertices (multigrafo) si no se permiten aristas multiples, ´ el grafo es simple si se asignan pesos (o costos o longitudes) a las aristas, el grafo es ponderado ´ si se asigna identidad a los vertices y/o las aristas, es decir que sean distinguibles, el grafo es etiquetado

A DYACENCIA dos aristas de un grafo son llamadas adyacentes si tienen un ´ en comun ´ vertice ´ dos vertices son llamados adyacentes si una arista los une ´ vertices adyacentes son llamados vecinos el conjunto de vecinos de v se llama el vecindario de v y se denota con Γ(v) ´ ´ ´ una arista es incidente a un vertice si esta lo une a otro vertice ´ el grado de un vertice v es el numero ´ de aristas incidentes a v ´ si todos los vertices tienen grado k, el grafo es regular

E JEMPLO : GRADOS 1

4 3 3

2

3

2 4

G RAFO BIPARTITO ´ = un grafo G = (V, E) cuyos vertices se pueden separar en dos conjuntos disjuntos U y W , U ∩ W = ∅, U ∪ W = V ´ de un conjunto con as´ı que las aristas solamente unen vertices ´ vertices de otro: (u, w) ∈ E ⇒ (u ∈ U ∧ w ∈ W ) ∨ (u ∈ W ∧ w ∈ U ) ´ presentes todas las aristas En un grafo bipartito completo estan entre U y W — se denota tal grafo por Ka,b donde a = |U | y b = |W |. Nota que para Ka,b , siempre m = a · b.

E JEMPLO : GRAFO BIPARTITO B

A

a c

a

b C c

b d

E

d D F e

e

A B C D E F

´ Los vertices azules son U y los verdes V . Los dos dibujos representan exactamente el mismo grafo — lo unico ´ que cambia ´ son las ubicaciones de las vertices.

D ENSIDAD un grafo simple es completo si existen aristas uniendo todos ´ los pares posibles de vertices ´ se denota un grafo completo de n vertices por Kn ´ el numero ´ maximo de aristas de un grafo simple es n n(n − 1) mmax = = 2 2 la densidad de G es δ =

m n 2

un grafo denso tiene δ ≈ 1 y un grafo escaso δ ≪ 1

C AMINOS ´ de aristas adyacentes que empieza en v y una sucesion termina en w se llama un camino de v a w el largo de un camino es el numero ´ de aristas que contiene la distancia de v y w es el largo m´ınimo de todos los caminos de v a w ´ la distancia de un vertice a si mismo es cero ´ un ciclo es un camino donde se regresa al vertice inicial un camino simple solamente recorre la misma arista una vez, ´ nunca dos veces o mas ´ ´ el diametro de G es la distancia maxima en todo el grafo

C ONECTIVIDAD ´ G es conexo si cada par de vertices esta´ conectado por un camino si no existe ningun ´ camino de v a w en G, el grafo esta´ no conexo ´ G es fuertemente conexo si cada par de vertices esta´ conectado por al menos dos caminos disjuntos un grafo desconectado se puede dividir en componentes conexos

´ RBOLES A ´ un arbol es un grafo conexo que no contiene ciclos ´ cubriente es un subgrafo de G = (V, E) que es un un arbol ´ ´ arbol y contiene todos los vertices de G ´ G es un bosque si cada componente conexo de G es un arbol

E JEMPLOS B

A

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

´ A LGORITMOS DE B USQUEDA ´ ´ Un algoritmo de busqueda ´ es un metodo sistematico para ´ recorrer un grafo de entrada G = (V, E) con el proposito de descubrir o computar alguna propiedad estructural del G. Los dos algoritmos fundamentales son busqueda ´ en anchura (BFS) busqueda ´ en profundidad (DFS)

´ B USQUEDA EN ANCHURA (BFS) ´ Dado G y un vertice inicial v ∈ V , el procedimiento general es el siguiente: 1. crea una lista vac´ıa L 2. asigna u := v 3. marca u visitado ˜ ´ 4. anade cada vertice no marcado en Γ(v) al fin de L 5. si L esta´ vac´ıa, termina ´ 6. asigna u := el primer vertice en L ´ 7. quita el primer vertice de L 8. continua de paso (3)

E JEMPLO : BFS

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

´ B USQUEDA EN PROFUNDIDAD (DFS) ´ Dado G y un vertice inicial v ∈ V , el procedimiento general es el siguiente: 1. crea una lista vac´ıa L 2. asigna u := v 3. marca u visitado ˜ ´ 4. anade cada vertice no marcado en Γ(v) al comienzo de L 5. si L esta´ vac´ıa, termina ´ 6. asigna u := el primer vertice en L ´ 7. quita el primer vertice de L 8. continua de paso (3) ´ recursiva facil) ´ (permite implementacion

E JEMPLO : DFS

DFS puede progresar en varias maneras; el orden de visitas ´ ´ vecino se va. Algunas aristas depende de como se elige a cual ´ encontradas apuntan a vertices ya visitados.

U SOS T´I PICOS DE BFS Y DFS ´ de caminos construccion ´ de distancias computacion ´ de ciclos deteccion componentes conexos

´ ... A CONTINUACI ON Acoplamientos de grafos y flujos en redes.