Teoría de Grafos.-Clase 2 Conexión y árboles. Aplicación 1: Problemas de ordenación....

Teoría de Grafos.-Clase 2

Conexión y árboles

Aplicación 1: Problemas de ordenación.(Estructura de una compañía)

Director

Coordinador 1

Trabajador 5

Coordinador 2

Trabajador 3Trabajador 2Trabajador 1 Trabajador 4

Aplicación 2.Problemas de búsqueda(Recorrer todas las habitaciones de un laberinto)

Aplicación 3: problemas de conectividad mínima.(Reconstrucción de carreteras tras un terremoto)

Aplicación 3b: problemas de conectividad mínima.(Reconstrucción de carreteras tras un terremoto con varios costes)

Definiciones:

Definición: Una cadena (walk) de un vértice u a un vértice y es una sucesión alternante de vértices y aristas, los cuales pueden estar repetidos.

u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y

En general escribiremos u, v, w, x, u, v, y

Definiciones:

Definición: Una camino (path) de un vértice u a un vértice y es una cadena de u a y sin vértices repetidos.

u, e4, x, e6, w, e3, v, e5, y

u, x, w, v, y

Definiciones:

Definición: Una ciclo (cycle) es un camino que empieza y acaba en el mismo vértice.

u, e1, v, e5, y, e7, w, e2, u

u, v, y, w, u

Definiciones:

Definición: Una recorrido (trail) es una cadena sin aristas repetidas (se pueden repetir vértices). Observar que es una condición mas débil que un camino.

x, e6, w, e3, v, e1, u, e2, w, e7, y

x, w, v, u, w, y

Definiciones:

Definición: Una circuito (circuito) es un recorrido con el mismo origen y final.Observar que un circuito es condición mas débil que un ciclo.

x, e6, w, e3, v, e5, y, e7, w, e2, u, e4, x

x, w, v, y, w, u, x

Teorema: Toda cadena u-v contiene un camino u-v

Sea u=u0, u1, u2, … , un=v una cadena de longitud n. Suponemos que u es diferente de v.

Si todos los vértice son diferentes entonces es un camino

Si hay dos vértices iguales digamos ui y uj son iguales con i diferente a j, entonces

u=u0, u1, u2, …, ui, ui+1, … uj-1, uj, uj+1, … , un=v

Eliminando los vértices desde ui hasta uj-1 tendríamos una cadena dondeestos dos vértices no están repetidos. Repitiendo el proceso hasta que no hayavértices repetidos nos daría un camino de u a v.

u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y

u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, yw

Definición: Un vértice u se dice que esta conectado al vértice v si existe una cadena (camino) de u a v. Un grafo se dice conexo o conectado si u esta conectado a v para todas posibles parejas de vértices u y v. Un grafo que no es conexo se dice disconexo.

Un subgrafo H de un grafo G se dice una componente de G si H es un subgrafo maximal conexo de G.

Grafo conexo Grafo disconexo con 4 componentes

Definición: Un vértice v en un grafo G se denomina vértice de corte si K(G-v) ≥ K(G)

K(G-v3)=2V3 es un vértice de corte

K(G-v2)=1V2 NO es un vértice de corte

K(G-v5)=2V5 es un vértice de corte

Grafo conexo GK(G)=1

Definición: Una arista e de un grafo G se denomina puente si K(G-e) ≥ K(G)

Grafo conexo GK(G)=1

v5v4 es puenteK(G –v5v4)=2

v1v2 NO es puenteK(G –v1v2)=1

Teorema: Una arista e de un grafo conexo G es un puente de G si y solo si e no esta en un ciclo de G.

Sea G un grafo conexo, si e es un puente entonces no esta en un ciclo

Como G es conexo existe un camino de a1 a a2 en G. -Si el camino no contiene a uv también estarán conectados en G-e-Si el camino contiene a e=uv solo hay que cambiar e=uv por u, x, …, w, v. Por tanto G-e es conexo lo cual es una contradicción ya que G-e debería ser disconexo puesto que e=uv es un puente.

Si e no esta en un ciclo de G entonces es un puente.

Si e=uv no esta en un ciclo entonces G-e no contiene un camino de u a v ya que Si lo contuviese uniendo el vértice uv seria un ciclo. Entonces u y v no están conectados y por tanto el grafo no es conexo.

Lo probamos por reducción al absurdo. Imaginemos que “e” estuviese en un ciclo.Sea el ciclo u, v, w, … , x, u e imaginemos sin perdida de generalidad que e = uv.Entonces existe un camino en G-e que une uv que seria u, x, …, w, v.

Veamos que dos vértices cualesquiera a1 y a2 de G-e están conectados, lo cual es absurdo ya que ya que G-e debería ser disconexo porque e=uv es un puente.

Definición: Un árbol es un grafo conexo sin ciclos.

Árbol p=2 Árbol p=3Árbol p=1 Árboles p=4

Árboles p=6

Sean p1 y p2 respectivamente el orden de T1 y T2 y q1 ,q2 sus tamaños.Evidentemente, k=p1+p2 y q=q1+q2+1.Como p1 y p2 son menores que k-1 por hipótesis se cumple que q1=p1-1 y q2=p2-1Entoncesq=q1+q2+1=(p1-1)+(p2-1)+1=p1+p2-1=k-1

Teorema: Un árbol de orden p tiene tamaño p-1.

Si p=1, hemos visto que q=0.Si p=2, también hemos visto que q=1.

Suponemos que hasta orden k-1 se cumple.Lo demostramos para p=k.

Sea T un árbol de orden k. Tenemos que probar que tiene tamaño q= k-1. Como todos las aristas son puentes si quitamos una, quedarían dos componentes T1 y T2.

Ejercicio: Sean T1 =(V1,A1) y T2=(V2,A2) dos árboles tales que |A1|=17, |V2|=2|V1| . Determinar |V1|, |V2| y |A2|.

V1 es 18 ya que el tamaño de un árbol de orden p es p-1.

V2=36 ya que 2*18=36 y A2 = 35

Consecuencia. Sea G un grafo de orden p- Entonces las siguientes afirmaciones son equivalentes:(1) G es un árbol. (Conexo y sin ciclos)(2) G tiene tamaño p-1 y no tiene ciclos.(3) G es conexo y tiene tamaño p-1.

(2)->(3) Tenemos que ver que es conexo. Si no fuese conexo, tendría k árboles (ya que no tiene ciclos). Cada árbol tendría p1, p2, … , pk vértices con p1+p2+ ...+ pk=p. Aplicando el teorema anterior tendría tamañop1-1+p2-1+ ...+ pk-1=p-k. Como sabemos que tiene tamaño p-1 se tiene que k=1. Es decir una única componente y por tanto conexa.

(1)->(3) Por el teorema anterior sabemos que tiene tamaño p-1.

(3)->(1) Como ejercicio. Basta observar cual es el menor numero de aristasNecesarias para hacer un ciclo.( Para una demostración rigurosa consultar Gross)

Teorema: Todo árbol con p≥2 contiene al menos dos vértices extremos (grado 1).

∑ di ≥ 1 + 2 (p-1)= 2p -1 (1)(un vértice tiene grado 1 y los otros como mínimo tienen grado 2)

Uniendo el teorema 1 de la clase 1 y que como T es un árbol tiene p-1 aristas

∑ di=2q=2(p-1)=2p-2. (2)

Uniendo (1) y (2) tenemos 2p-2 ≥ 2p -1 que es absurdo

Vamos a probarlo por reducción al absurdo. Supondremos que no es cierto y llegaremos a una contradicción.

Sea T un árbol de orden p y tamaño q con secuencia de grados d1 ≤ d2 ≤ … ≤ dp Como T es conexo al menos cada vértice tiene grado 1 es decir di ≥ 1.

Supongamos que no contiene al menos dos vértices de grado 1. Es decir contendría o 0 o 1. Cero no puede ser ya que es conexo. Entonces tendríaque tener solo un vértice de grado 1. Entonces se d1 =1 y di ≥2 para los demás vértices. Entonces

Teorema: Si u y v son dos vértices distintos de un árbol T, entonces TContiene exactamente un camino (path) u-v.

Sabemos que existe al menos 1 ya que es conexo.Igual que antes vamos a demostrarlo por reducción al absurdo.Supongamos que existen dos caminos P y Q que unen u y v.Entonces tiene que existir un vértice ui donde el siguiente vértice en los dos caminos es diferente. De igual forma existe un vértice u n-j a partir del cual ambos tienen los mismos vértices.

un-1 vun-ju2

ui+1 u n-j-1

Si esto pasase, existiría un ciclo y es absurdo ya que los árboles no tienen ciclos.

Algoritmo Depth-First Search

Es un algoritmo que garantiza que de forma sistemática recorremos todos los vértices del grafo. Esta basado en el concepto de pila

L M N O P

H JI K

Apilar

Desapilar

Ejemplo: Recorrer todos los vértices del siguiente grafo mediante DFS empezando en 1.

Actual

Asignamos Etiqueta(si actual es nuevo)

Aumentamosetiqueta(si hubo asignación de etiqueta) Pila

v1 1 2 v1

Huboasignaciónetiqueta

Adyacentes

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1

v4 7 8 v1v3v41 0

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1

v4 7 8 v1v3v41 0

v3 - 8 v1v30 1 7

Actual

v1 1 2 v1

Adyacentes

v2 2 3 v1v21 1 v2

v5 3 4 v1v2v51 1 v5

v6 4 5 v1v2v5v61 0v6

v5 - 5 v1v2v50 1

v8 5 6 v1v2v5v81 0

v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1

v4 7 8 v1v3v41 0

v3 - 8 v1v30 1v7 8 9 v1v3v71 0

v3 - 9 v1v30v1 - 9 v10

Añade

Elimina

2 3 4 8 1 3 5 11

Algoritmo Depth-First Search

L M N O P

H JI K

Es un algoritmo parecido al DFS que garantiza que de forma sistemática recorremos todos los vértices del grafo. Esta basado en el concepto de cola.

(1) v1

(2) v1 v2 v3 v4 v6 v7 v8 v8v2 v3 v7v6v4

v2 v3 v4 v6 v7 v8

(1) v1

(2) v1 v2 v3 v4 v6 v7 v8 v8

v2 v3 v4 v6 v7 v8(3)

v2 v3 v7v6

v2 v3 v4 v6 v7 v8

v3 v4 v6 v7 v8 v5v5

(1) v1

(2) v1 v2 v3 v4 v6 v7 v8 v8

v2 v3 v4 v6 v7 v8(3)

v2 v3 v7v6

v2 v3 v4 v6 v7 v8

v3 v4 v6 v7 v8 v5v5

(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5

(1) v1

(2) v1 v2 v3 v4 v6 v7 v8 v8

v2 v3 v4 v6 v7 v8(3)

v2 v3 v7v6

v2 v3 v4 v6 v7 v8

v3 v4 v6 v7 v8 v5v5

(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5

v4 v6 v7 v8 v5(5) v6 v7 v8 v5

(1) v1

(2) v1 v2 v3 v4 v6 v7 v8 v8

v2 v3 v4 v6 v7 v8(3)

v2 v3 v7v6

v2 v3 v4 v6 v7 v8

v3 v4 v6 v7 v8 v5v5

(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5

v4 v6 v7 v8 v5(5) v6 v7 v8 v5

v6 v7 v8 v5 v7 v8 v5(6)

v7 v8 v5 v8 v5

v8 v5v5

v8v2 v3 v7v6

DFSDBS

Teoría de Grafos.-Clase 2 Conexión y árboles. Aplicación 1: Problemas de ordenación....

Documents

Ejercicios (Grafos)

PROGRAMACIÓN PARALELA Esquemas de programación …dis.um.es/~domingo/apuntes/Valencia/0809/Algoritmos.pdfEsquemas de Programación Paralela 14 Recorrido de árboles y grafos * Muchos

Vicerrectora Académica Dirección de Estudios ... · Teoría de grafos y Algoritmos de Optimización en grafos es o no ... Árboles generados y conjuntos de corte. ... Determinan

Tópicos I Unidad I Cola de prioridades, montículos Semana 3 Árboles, montículos y grafos

Estructura de Datos - árboles y grafos

UNIDAD 2 Grafos Árboles abarcadores mínimos Caminos más cortos

Tópicos I Unidad I Arboles de búsqueda Semana 1 Árboles, montículos y grafos

Grafos Iii

Tópicos I Unidad I Algoritmos sobre grafos elementales, Conectividad y Grafos ponderados Semana 4 Árboles, montículos y grafos

Grafos (Full)

Grafos Terminologia e Tipos Especiais de Grafosjmi/md/grafos.pdfGrafos Grafos Terminologia e Tipos Especiais de Grafos Grafos Grafos e Modelos Umgrafo G e composto pelo par (V;A)

Solución de Grafos Con El Software Grafos

Julio grafos

Intro Grafos

Grafos Estructura

Presentación1 grafos

Ejemplo grafos

Sobre subclases y variantes de los grafos perfectos' · grafos de l´ınea, grafos clique-Helly hereditarios sin claw, grafos sin diamantes y grafos arco-circulares Helly. En casi

GRAFOS definiciones

Grafos Digrafos