TP Grafos - Parte 2

Trabajo práctico: Grafos – Parte 2 

1) Confeccionar las matrices de adyacencia e incidencia totalizando los grados de los vértices de los  siguientes grafos:

a)                                 b)                         c)                 d)

 [pic 1]  [pic 2][pic 3][pic 4]2) Dado el siguiente grafo encontrar:

a) Todos los caminos simples de A a F [pic 5]

b) Todos los ciclos que incluyen al Vértice A como inicio y fin

c) Todos los ciclos del grafo

d) Un camino de longitud 6 entre A y B

e) Un camino de longuitud 3 entre A y C

3) Dada la siguiente Matriz de adyacencia: [pic 6]

Determinar y justificar cada punto:  

a) ¿El grafo es conexo?

b) ¿El grafo es euleriano?

c) ¿Es multigrafo?

4) Determinar cuáles de los siguientes grafos son Eulerianos. En caso de serlos determinar el ciclo  euleriano para dibujarlo sin levantar el lápiz.

a)                                 b)                                 c)[pic 7]

5) Determiná para los siguientes grafos, si son eulerianos, indicar un circuito y un camino euleriano y un  camino hamiltoniano

a)                                 b)                         c)                        d)[pic 8]

1. 
   a)

Matriz de adyacencia:

   A B C D

A  0 1 1 1

B  1 0 1 1

C  1 1 0 1

D  1 1 1 0

Matriz de incidencia:

   e1 e2 e3 e4

A   1  1  1  0

B   1  1  0  1

C   1  0  1  1

D   0  1  1  1

Totalización de los grados de los vértices:

Vértice A: grado 3

Vértice B: grado 3

Vértice C: grado 3

Vértice D: grado 3

b)

Matriz de adyacencia:

   A B C D E

A  0 1 0 1 1

B  1 0 1 0 1

C  0 1 0 1 1

D  1 0 1 0 1

E  1 1 1 1 0

Matriz de incidencia:

   e1 e2 e3 e4 e5

A   1  1  0  1  1

B   1  0  1  0  1

C   0  1  1  1  0

D   0  0  0  1  1

E   0  0  1  0  1

Totalización de los grados de los vértices:

Vértice A: grado 3

Vértice B: grado 3

Vértice C: grado 3

Vértice D: grado 3

Vértice E: grado 4

c)

Matriz de adyacencia:

   A B C D

A  0 1 1 0

B  1 0 0 1

C  1 0 0 1

D  0 1 1 0

Matriz de incidencia:

   e1 e2 e3 e4

A   1  1  0  0

B   1  0  1  0

C   0  0  1  1

D   0  1  0  1

Totalización de los grados de los vértices:

Vértice A: grado 2

Vértice B: grado 2

Vértice C: grado 2

Vértice D: grado 2

d)

Matriz de adyacencia:

A B C D E

A 0 1 1 1 0

B 1 0 1 0 1

C 1 1 0 1 0

D 1 0 1 0 1

E 0 1 0 1 0

Matriz de incidencia:

      a  b  c  d  e

    ----------------

  1 |  1  1  0  0  0

  2 |  1  0  1  1  0

  3 |  0  1  1  0  1

  4 |  0  0  0  1  1

Totalización de grados de vértices:

Vértice A: grado 3

Vértice B: grado 3

Vértice C: grado 3

Vértice D: grado 3

Vértice E: grado 2

a) Todos los caminos simples de A a F son:

```

A -> B -> D -> F

A -> C -> D -> F

```

...