Analisis De Algoritmos

analisi

2012
Practica:5
Analisis de Algoritmos
Emmanuel Osain Jimenez Pliego
universidad veracruzana

Indice:
1Introducción: ……………………………………………………. ……. 2Ejercicios:……………………………………………………………….… 3
1) Obtener lamatriz adyacente y de incidencia degrafos……... 3
2) Obtener el resultado y escribir como queda la operación algebraica de los siguientes grafos:………………………..……….. 4
3) Calcular las posibles rutas y elegir cual es lamejor:…………. 4
4) Menciona al menos 3 ejemplos endonde se puedan aplicar los grafos en solución de problemas………………... …………… …….. 5

Investigación:………….…………………………………………………. 6Diferencia entre grafos dirigidos y no dirigidos:….…………….… 6







Introduccion:
En esta practica pondremos en ejecución el uso de los grafos los cuales a diferencia de los arboles incluyenciclos.

Aquí también veremos el recorrido de grafos y veremos qe tienen bucles, asi como tener ahora en cuenta en donde se puede implementar el uso de grafos y el recorrido de estos.

Ejercicios:1) Obtener la matriz adyacente y de incidencia de los siguientes grafos:

| AB | AC | AD | BC | BF | CD | CF | DF |
A | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
B | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |C | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
D | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
F | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| A | B | C | D | F |
A | 0 | 1 | 1 | 1 | 0 |
B | 1 | 0 | 1 | 0 | 1 |
C | 1 |1 | 0 | 1 | 1 |
D | 1 | 0 | 1 | 0 | 1 |
F | 0 | 1 | 1 | 1 | 0 |
A
D
C
B
F
a)

B
D
C
A
F
E

| AB | AD | BC | CD | CF | DE | EF |
A | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
B | 1 | 0 | 1 |0 | 0 | 0 | 0 |
C | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
D | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
E | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
F | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| A | B | C | D | E | F |
A | 0 | 1 | 0 |1 | 0 | 0 |
B | 1 | 0 | 1 | 0 | 0 | 0 |
C | 0 | 1 | 0 | 1 | 0 | 1 |
D | 1 | 0 | 1 | 0 | 1 | 0 |
E | 0 | 0 | 0 | 1 | 0 | 1 |
F | 0 | 0 | 1 |...