• Author / Uploaded
• Pepe Rojas

Citation preview

Cálculo científico y técnico con HP49g/49g+/48gII/50g Módulo 3: Aplicaciones Tema 3.4 Grafos Francisco Palacios Escuela Politécnica Superior de Ingeniería de Manresa Universidad Politécnica de Catalunya Dep. Matemática Aplicada III Abril 2008, versión 1.3

1

Introducción

Un grafo dirigido es un conjunto de nodos P1 , P2 , . . . , Pn , conectados por flechas. Las flechas indican cuando es posible pasar de un nodo a otro. El orden del grafo es el número de nodos. Así, por ejemplo, el siguiente diagrama representa un grafo de orden 4.

A la vista del diagrama, está claro que es posible pasar de P1 a P2 , en cambio, no es posible pasar del nodo P1 al nodo P3 . Desde P4 , podemos pasar al nodo P3 o permanecer en el nodo P4 .

1.1

Representación matricial

Existe una representación matricial de los grafos que nos permite estudiar las posibles transiciones entre los nodos. La matriz de transición de un grafo de orden n es una matriz cuadrada de orden n, donde: • Las columnas están asociadas a los nodos de salida. 1

• Las filas están asociadas a los nodos de llegada. • Si el grafo permite la transición Pj → Pi , ponemos el elemento mij = 1. • Si el grafo no permite la transición Pj → Pi , ponemos mij = 0. La notación anterior puede ser un poco incómoda porque realizamos un intercambio del orden de los subíndices. Esto puede evitarse si observamos que mij = 1 cuando es posible alcanzar Pi desde Pj . Así, el elemento m34 = 1 indica que es posible alcanzar el nodo P3 desde P4 . Para el grafo

obtenemos siguiente matriz de transición ⎛ ⎜ ⎜ ⎝

M =⎜

0 1 0 0

0 0 0 1

0 1 0 0

0 0 1 1

⎞ ⎟ ⎟ ⎟ ⎠

La primera columna contiene un único uno m21 = 1, que indica que desde P1 solo podemos pasar al nodo P2 . La columna 4 tiene dos unos m34 = 1, m44 = 1, que indican que desde el P4 podemos pasar a P3 o permanecer en P4 . Actividad 1.1 Determina la matriz de transición del siguiente grafo

2

1.2

Transición en dos etapas

Una vez definido un grafo, podemos plantearnos qué transiciones son posibles en exactamente dos etapas. Esto es, situados en el nodo j, ¿a qué nodos podemos acceder en exactamente dos etapas? Queda así definido un nuevo grafo, que denominamos grafo de transición en dos etapas. A partir del grafo

obtenemos el siguiente grafo de transición en dos etapas.

En el grafo de transición en dos etapas vemos que podemos pasar desde P1 a P4 , realizando el camino P1 → P2 → P4 . Desde P3 podemos pasar a P4 realizando el camino P3 → P2 → P4 . La propiedad notable es que podemos obtener la matriz de transición del grafo en dos etapas elevando al cuadrado la matriz de transición en una etapa. Si representamos por M (2) la matriz de transición en 2 etapas, resulta M (2) = M 2 . En nuestro ejemplo, obtenemos ⎛ ⎜ ⎜ ⎝

M2 = ⎜

0 1 0 0

0 0 0 1

0 1 0 0

0 0 1 1

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟×⎜ ⎠ ⎝

0 1 0 0

0 0 0 1

0 1 0 0

0 0 1 1

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟=⎜ ⎠ ⎝

0 0 0 1

0 0 1 1

0 0 0 1

0 1 1 1

⎞ ⎟ ⎟ ⎟ ⎠

Es inmediato observar que la matriz M 2 es la matriz de transición del grafo en dos etapas. 3

1.3

Transición en k etapas.

De forma análoga, puede construirse el grafo de transición en exactamente k etapas, la matriz de transición verifica M (k) = M k . Esto es, podemos calcular la matriz de transición en exactamente k etapas M (k) mediante la k-ésima potencia de M. Nota. Al calcular las potencias de M puede aparecer elementos con valor (k) mayor de 1. Un elemento mij = 3 indica que es posible llegar a Pi desde Pj en exactamente k etapas y que esto se pude hacer exactamente de 3 formas distintas.. Para la matriz ⎛ ⎞ 0 0 0 0 ⎜ 1 0 1 0 ⎟ ⎜ ⎟ M =⎜ ⎟ ⎝ 0 0 0 1 ⎠ 0 1 0 1 obtenemos la potencia 4

⎛ ⎜ ⎜ ⎝

M (4) = M 4 = ⎜

0 1 1 1

0 1 1 2

0 1 1 1

0 1 2 3

⎞

⎟ ⎟ ⎟. ⎠

(4)

El elemento m42 = 2 indica que es posible ir alcanzar P4 desde P2 en exactamente 4 transiciones y que esto puede hacerse de exactamente 2 formas, si observamos el grafo inicial,

vemos que tales caminos son: (1)

(2)

(3)

(4)

(1)

(2)

(3)

(4)

P2 −→ P4 −→ P3 −→ P2 −→ P4 , P2 −→ P4 −→ P4 −→ P4 −→ P4 . Actividad 1.2 Determina los caminos correspondientes a los demás elementos de la matriz M (4) .

4

2

Resolución con la calculadora

El cálculo manual de las potencias de una matriz es una tarea realmente costosa. La calculadora permite calcular potencias enteras de matrices con la tecla [y x ]. Este recurso nos permite calcular fácilmente las matrices de transición de un grafo. Para el grafo

Obtenemos la matriz de transición

Guarda la matriz en la variable M. Para calcular M 2 , carga la matriz en el Nivel 2 y el entero1 2 en el Nivel 1

y pulsamos [yx ]. Se obtiene 1

Asegúrate que la calculadora está en modo exacto y que el exponente no tiene punto decimal. Si intentas usar el número decimal 2. como eponente puedes obtener un error.

5

De forma análoga, para calcular la matriz de transición en 4 etapas, carga M en la pila seguida del exponente entero 4

y pulsa [y x ]

Actividad 2.1 Consideramos el siguiente grafo:

Calcula las matrices de transición en 2, 3 y 4 etapas. ¿Es posible alcanzar P1 desde P4 en exactamente 3 etapas?

6

3

Transición en k etapas o menos

En el grafo de transición en k etapas o menos, el nodo Pj está conectado con el nodo Pi si es posible alcanzar desde Pi desde Pj en exactamente 1, 2, 3, . . . ó k etapas. Es evidente que la matriz de transición en k etapas o menos ¯ (k) puede obtenerse sumando las matrices de transición en exactamente M 1, 2, 3, . . . k, etapas, es decir ¯ (k) = M + M (2) + · · · + M (k) , M ¯ (k) puede calcularse y teniendo en cuenta que M (k) = M k , la matriz M sumando las potencias de M ¯ (k) = M + M 2 + · · · + M k . M Para el grafo

La matriz de transición en 3 etapas o menos es ⎛ ⎜

¯ (3) = ⎜ M ⎜ ⎝ ⎛ ⎜ ⎜ ⎝

= ⎜

0 1 0 0

0 0 0 1

0 1 0 0

0 0 1 1

0 1 1 2

0 1 2 3

0 1 1 2

0 2 3 4

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟+⎜ ⎠ ⎝ ⎞

0 0 0 1

0 0 1 1

0 0 0 1

0 1 1 1

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟+⎜ ⎠ ⎝

0 0 1 1

0 1 1 1

0 0 1 1

0 1 1 2

⎞ ⎟ ⎟ ⎟ ⎠

⎟ ⎟ ⎟ ⎠

(3)

• El elemento m ¯ 21 = 1 indica que se puede alcanzar P2 desde P1 en 3 etapas o menos de exactamente una manera. El único camino válido es P1 → P2 . (3)

• El elemento m ¯ 24 = 2 indica que se puede alcanzar P2 desde P4 en 3 etapas o menos de exactamente 2 maneras. Los caminos válidos son: P4 → P3 → P2 ,

P4 → P4 → P3 → P2 . 7

Actividad 3.1 Para el grafo,

calcula la matriz de transición en 4 etapas o menos.

4

Soluciones a las actividades

Actividad 1.1

⎛ ⎜ ⎜ ⎝

M =⎜

0 0 1 0

1 1 0 1

⎞

0 1 0 0

0 0 1 0

0 1 1 1

0 1 2 3

⎟ ⎟ ⎟ ⎠

Actividad 1.2 La matriz de transición en 4 etapas es ⎛ ⎜ ⎜ ⎝

M (4) = ⎜

0 1 1 1

0 1 1 2

⎞

⎟ ⎟ ⎟. ⎠

La fila 1 es nula. Esto indica que el nodo P1 no puede alcanzarse en 4 pasos. De hecho el nodo P1 solo puede alcanzarse como nodo inicial. La segunda fila está formada por unos. Por lo tanto, el nodo P2 puede ser alcanzado partiendo desde cualquier nodo en 4 transiciones y eso puede hacerse exactamente de una manera. Los caminos son los siguientes 1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

P1 → P2 → P4 → P2 → P2 , P2 → P4 → P4 → P3 → P2 , P3 → P2 → P4 → P3 → P2 , P4 → P4 → P4 → P3 → P2 . Según la fila 3, podemos alcanzar en cuatro etapas el nodo P3 desde P1 , P2 , P3 , de una forma. Los caminos son 1

2

3

4

P1 → P2 → P4 → P4 → P3 , 8

1

2

3

4

1

2

3

4

P2 → P4 → P4 → P4 → P3 , P3 → P2 → P4 → P4 → P3 . Partiendo desde P4 , se puede alcanzar P3 en cuatro etapas de 2 formas, los caminos son 1 2 3 4 P4 → P4 → P4 → P4 → P3 , 1

2

3

4

P4 → P3 → P2 → P4 → P3 . Finalmente, la fila 4 indica que es posible alcanzar el nodo P4 desde cualquier nodo en 4 etapas. Desde P1 y P3 puede hacerse de una sola forma 1

2

3

4

1

2

3

4

P1 → P2 → P4 → P4 → P4 , P3 → P2 → P4 → P4 → P4 . Hemos visto que desde P2 , puede alcanzarse P4 de 2 formas 1

2

3

4

1

2

3

4

P2 → P4 → P4 → P4 → P4 , P2 → P4 → P3 → P2 → P4 . Desde P4 se puede alcanzar P4 de 3 maneras. 1

2

3

4

1

2

3

4

1

2

3

4

P4 → P4 → P4 → P4 → P4 , P4 → P4 → P3 → P2 → P4 , P4 → P3 → P2 → P4 → P4 . Actividad ?? La matriz de transición es ⎛ ⎜ ⎜ ⎝

M =⎜

0 0 1 0

1 1 0 1

0 1 0 0

0 0 1 0

⎞

⎟ ⎟ ⎟. ⎠

Las matrices de transición en 2, 3 y 4 etapas son: ⎛ ⎜ ⎜ ⎝

M (2) = ⎜

0 1 0 0

1 1 2 1

1 1 0 1

0 1 0 0

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟ , M (3) = ⎜ ⎠ ⎝

1 1 0 1

1 3 2 1

1 1 2 1

1 1 0 1

(3)

⎞

⎛

⎟ ⎜ ⎟ ⎜ ⎟ , M (4) = ⎜ ⎠ ⎝

1 1 2 1

3 5 2 3

1 3 2 1

1 1 2 1

⎞

⎟ ⎟ ⎟. ⎠

Si observamos M (3) , obtenemos m14 = 1, por lo tanto, existe un camino de tres etapas que permite alcanzar el nodo P1 desde P4 . El camino es 1

2

3

P4 → P3 → P2 → P1 . 9

Actividad 3.1 ¯ (4) = M + M (2) + M (3) + M (4) . M ⎛ ⎜

¯ (4) = ⎜ M ⎜ ⎝

2 6 3 2 3 10 6 3 3 6 4 3 2 6 3 2

10

⎞ ⎟ ⎟ ⎟ ⎠