Grafos

Solo disponible en BuenasTareas
  • Páginas : 3 (548 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de diciembre de 2011
Leer documento completo
Vista previa del texto
a. Describir el grafo en términos de un conjunto de V de nodos y de su conjunto A de aristas

Conjunto de vértices: {A,B,C,D,E}
Conjunto de aristas: {(A,D),(A,B),(B.D),(C,B),(D,C),(D,E),(E,C)}b. Encontrar el grado de entrada y grado de salida de cada vértice.

Nodo | Grado de entrada | Grado de salida |
A | 0 | 2 |
B | 2 | 1 |
C | 2 | 1 |
D | 2 | 2 |
E | 1 | 1 |

c.Encontrar los caminos simples del vértice A al vértice C.

P1=(A,D,E,C)
P2=(A,D,C)
P3=(A,B,D,C)
P4=(A,B,D,E,C)

d. Calcule la potencia a partir de la Matriz de Adyacencia. Diga cuántoscaminos de longitud 3 existen para cada vértice.

Cantidad de nodos: 5

A0 y A1 | A | B | C | D | E |
A | 0 | 1 | 0 | 1 | 0 |
B | 0 | 0 | 0 | 1 | 0 |
C | 0 | 1 | 0 | 0 | 0 |
D | 0 | 0 | 1 |0 | 1 |
E | 0 | 0 | 1 | 0 | 0 |
| A2 | A | B | C | D | E |
A | 0 | 0 | 1 | 1 | 1 |
B | 0 | 0 | 1 | 0 | 1 |
C | 0 | 0 | 0 | 1 | 0 |
D | 0 | 1 | 1 | 0 | 0 |
E | 0 | 1 | 0 | 0 | 0 |
|A3 | A | B | C | D | E |
A | 0 | 1 | 2 | 0 | 1 |
B | 0 | 1 | 1 | 0 | 0 |
C | 0 | 0 | 1 | 0 | 1 |
D | 0 | 1 | 0 | 1 | 0 |
E | 0 | 0 | 0 | 1 | 0 |
|
A4 | A | B | C | D | E |
A | 0 | 2 |1 | 1 | 0 |
B | 0 | 1 | 0 | 1 | 0 |
C | 0 | 1 | 1 | 0 | 0 |
D | 0 | 0 | 1 | 1 | 1 |
E | 0 | 0 | 1 | 0 | 1 |
| A5 | A | B | C | D | E |
A | 0 | 1 | 1 | 2 | 1 |
B | 0 | 0 | 1 | 1 | 1 |C | 0 | 1 | 0 | 1 | 0 |
D | 0 | 1 | 2 | 0 | 1 |
E | 0 | 1 | 1 | 0 | 0 |
| Sumatoria | A | B | C | D | E |
A | 0 | 5 | 5 | 5 | 3 |
B | 0 | 2 | 3 | 3 | 2 |
C | 0 | 3 | 2 | 2 | 1 |
D | 0| 3 | 5 | 2 | 3 |
E | 0 | 2 | 3 | 1 | 1 |
|

Caminos de longitud 3:

A= 4 {A, D, E, C}
{A, D, C, B}
{A, B, D, E}
{A, B, D, C}

B= 2 {B, D, C, B}
{B, D, E, C}

C= 2 {C, B, D,C}
{C, B, D, E}

D= 2 {D, C, B, D}
{D, E, C, B}

E=1 {E, C, B, D}

a. Dibuje el grafo correspondiente
D
C
E
A
B
D
C
E
A
B

b. Represente el grafo mediante lista de...
tracking img