• Author / Uploaded
• JULIAN DAVID RINCON CASTRO

Citation preview

Taller Representación de Grafos No Dirigidos y Ponderados.

Equipo 7 Julián David Rincón Castro – 20172020125 Jordy Esteban Pineda Velandia – 20172020119 Javier Andrés Aponte Quevedo – 20172020036 Jhonnatan Leonardo Daza Ibarra – 20162020011

Docente: Julio Cesar Flórez Báez.

Ciencias de la Computación II.

Universidad Distrital Francisco José de Caldas. Facultad de Ingeniería Ingeniería de Sistemas Bogotá D. C. 2020

Introducción. Muchas veces en la aplicación de la teoría de grafos en la vida real, estos no pueden ser representados por grafos no dirigidos, ya que cada arista debe seguir un sentido, como sucede en la teoría de redes. Para esto se ve necesario estudiar también la representación matricial de grafos dirigidos, que facilitan la implementación computacional para este tipo de aplicaciones.

Objetivos. General. Reconocer y aprender a realizar, las diferentes representaciones matriciales de grafos dirigidos ponderados y grafos dirigidos no ponderados. Específicos. • Reconocer la matriz de incidencia de un grafo dirigido ponderado y no ponderado. • Reconocer la matriz de adyacencia de vértices y aristas de un grafo dirigido ponderado y no ponderado. • Reconocer la matriz de circuitos de un grafo dirigido ponderado y no ponderado.

Marco Teórico. Grafo. Un grafo G es una pareja de conjuntos (S, A), donde S es el conjunto de vértices y A es el conjunto de aristas. Vértice. Son los elementos que forman el grafo. Cada uno lleva una valencia característica asociada según la situación, el conjunto de vértices se suele representar por V o S. Arista. Son las líneas que unen los vértices de un grafo. El conjunto de aristas en un grafo se suele representar por E o A. Grafo dirigido. Un grafo dirigido es aquel que tiene todas sus aristas dirigidas, es decir, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w, v), que es diferente de (v, w). En el grafo se representa por una flecha que inicia en el vértice w y termina en el vértice v. Grafo ponderado. Un grafo ponderado o con costos, es un grafo donde cada arista tiene asociado un valor o etiqueta, para representar el costo, peso, o longitud de la arista. Matriz de incidencia. En una matriz de tamaño n x m, donde n es el numero de vértices, y m el numero de aristas. En grafos dirigidos, se agrega un 1 en la matriz si la arista incide de salida al vértice, y -1 si incide de llegada al vértice. Matriz de adyacencia. Es una matriz cuadrada usada para representar relaciones binarias, en el caso de un grafo, una matriz de adyacencia puede ser usada para representar la cercanía entre vértices o aristas.

Desarrollo del Taller.

Dado el siguiente grafo hallar:

b-4

2 a-2

5

d- 8 c-6 4

1

e - 10

f - 12 3

𝐺 = (𝑆, 𝐴) 𝑆 = {1,2,3,4,5} 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓}

Dirigido no ponderado: Matriz de incidencia: A

B

C

D

E

F

1

1

0

0

0

0

-1

2

-1

1

0

1

0

0

3

0

0

0

0

1

1

4

0

0

-1

-1

-1

0

5

0

-1

1

0

0

0

Matriz de adyacencia vértices: 1

2

3

4

5

1

0

1

-1

0

0

2

-1

0

0

1

1

3

1

0

0

1

0

4

0

-1

-1

0

-1

5

0

-1

0

1

0

Matriz de adyacencia aristas: A

B

C

D

E

F

A

0

1

0

1

0

1

B

1

0

1

-1

0

0

C

0

1

0

-1

-1

0

D

1

-1

-1

0

-1

0

E

0

0

-1

-1

0

-1

F

1

0

0

0

-1

0

Circuitos:

𝑐1 = {𝑎, 𝑏, 𝑐, 𝑒, 𝑓} 𝑐2 = {𝑎, 𝑑, 𝑒, 𝑓} 𝑐3 = {𝑏, 𝑐, 𝑑} Grafos de los circuitos:

•

𝑐1 = {𝑎, 𝑏, 𝑐, 𝑒, 𝑓}

2

b-4

5

a-2 c-6 4

1

e - 10

f - 12 3

•

𝑐3 = {𝑎, 𝑑, 𝑒, 𝑓}

2 a-2

d- 8 4

1

e - 10

f - 12 3

•

𝑐3 = {𝑏, 𝑐, 𝑑}

b-4

2

d- 8

5 c-6

4

Matriz de los circuitos:

A

B

C

D

E

F

1

1

1

1

0

-1

1

2

1

0

0

1

-1

1

3

0

1

1

-1

0

0

A

B

C

D

E

F

1

2

0

0

0

0

-12

2

-2

4

0

8

0

0

3

0

0

0

0

10

12

4

0

0

-6

-8

-10

0

5

0

-4

6

0

0

0

Dirigido ponderado: Matriz de incidencia:

Matriz de adyacencia vértices: 1

2

3

4

5

1

0

2

-12

0

0

2

-2

0

0

8

4

3

12

0

0

10

0

4

0

-8

-10

0

-6

5

0

-4

0

6

0

A

B

C

D

E

F

A

0

6

0

10

0

14

B

6

0

10

-12

0

0

C

0

10

0

-14

-16

0

D

10

-12

-14

0

-18

0

E

0

0

-16

-18

0

-22

F

14

0

0

0

-22

0

Matriz de adyacencia aristas:

Circuitos

𝑐1 = {𝑎, 𝑏, 𝑐, 𝑒, 𝑓} 𝑐2 = {𝑎, 𝑑, 𝑒, 𝑓} 𝑐3 = {𝑏, 𝑐, 𝑑}

Grafos de los circuitos:

•

𝑐1 = {𝑎, 𝑏, 𝑐, 𝑒, 𝑓}

b-4

2

5

a-2 c-6 4

1

e - 10

f - 12 3

•

𝑐3 = {𝑎, 𝑑, 𝑒, 𝑓}

2 a-2

d- 8 4

1

e - 10

f - 12 3

•

𝑐3 = {𝑏, 𝑐, 𝑑}

b-4

2

5

d- 8

c-6 4

Matriz de los circuitos: A

B

C

D

E

F

1

2

4

6

0

-10

12

2

2

0

0

8

-10

12

3

0

4

6

-8

0

0

Conclusiones. En la representación matricial de grafos dirigidos, siempre es importante reconocer la dirección de una arista, ya que esto no permitirá determinar si en la matriz corresponde a un valor positivo o negativo. En el caso de los circuitos se debe establecer un marco de referencia para recorrerlos, para esta actividad se establece como marco de referencia el sentido de las manecillas del reloj, por lo que si al momento de recorrer una arista en un circuito esta va en sentido del reloj se representara por 1, y si la arista va en sentido contrario a las manecillas del reloj, su representación será por -1. Algo que se puede notar en la matriz de incidencia, ya sea de un grafo ponderado o no, al sumar los valores de cada columna de la matriz, estos dan 0. Por lo que, si se desea comprobar si la matriz de adyacencia esta bien construida, se pueden sumar los valores de cada columna y comprobar que cada suma de cero. Para el caso de las matrices de adyacencia de aristas una técnica para comprobar si están correctas en que estas deben ser simétricas.