Grafos

INDICE.

Introducción……………………………………………………………………………………………………………….. p.p. 3
Definición…………………………………………………………………………………………………………………… p.p. 4
Clasificación de los grafos…………………………………………………………………………………………… p.p. 4

Representación en la computadora de los grafos……………………………………………………….. p.p. 6
Representación Matricial………………………………………………………………………………….. p.p. 6
RepresentaciónEnlazada………………………………………………………………………………….. p.p. 8
Ejemplo……………………………………………………………………………………………………………. p.p. 9

Algoritmo de Dijkstra…………………………………………………………………………………………………… p.p. 11
Pseudocódigo del Algoritmo……………………………………………………………………………..p.p. 11
Funcionamiento del Algoritmo…………………………………………………………………………. p.p. 12
Ejemplo……………………………………………………………………………………………………………. p.p. 15

Algoritmo deEuler………………………………………………………………………………………………………. p.p. 16
El problema y el Método………………………………………………………………………………….. p.p. 16
Teoría………………………………………………………………………………………………………………. p.p. 16
Solución Analítica………………………………………………………………………………….. p.p. 17
Solución Numérica………………………………………………………………………………… p.p. 17Programa……………………………………………………………………………………………… p.p. 17
Ejemplo……………………………………………………………………………………………………………. p.p. 18

Algoritmo de camino más corto……………………………………………………………………………………. p.p. 19
Algoritmo………………………………………………………………………………………………………….. p.p. 19
Pseudocódigo…………………………………………………………………………………………………… p.p. 19
Comportamiento con ciclos negativos……………………………………………………………….. p.p. 20
Ejemplo……………………………………………………………………………………………………………… p.p. 20Análisis…………………………………………………………………………………………………………….. p.p. 23

Grafos conexos……………………………………………………………………………………………………………… p.p. 24
Cuestionario………………………………………………………………………………………………………………….. p.p. 25
Conclusiones…………………………………………………………………………………………………………………. p.p. 26
Bibliografía……………………………………………………………………………………………………………………. p.p. 27

INTRODUCCIÓN.

En el presente trabajo abordaremos el tema de los grafoslos cuales son indispensables en la programación ya que son una herramienta muy útil y eficiente al momento de realizar búsquedas o simplemente para quedar de manera estructurada la informmmacccion

Los grafos al ser tipos de datos abstractos (TDA) son utilizados en múltiples disciplinas y sobre todo para la organización de computadoras y representación de un camino a seguir, en este casoespecificaremos sus características y algunas ventajas y desventajas de usar los distintos tipos de grafos dentro de la planeación de soluciones a distintos problemas propuestos

Definición

Un grafo es un TDA que representa un conjunto finito N de nodos, llamado vértices, relacionados entre sí por un conjunto R de arcos.

A
A

C
C

B
B

E
E
D
D

Ejemplo de un grafo

En elejemplo anterior podemos ver un grafo de 5 vértices y 6 arcos.

* Vértices del Grafo

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

* Arcos del Grafo

R= {(A, A), (A, B), (A, D), (A, C), (D, C), (C, E)}

Hay algunos puntos que tenemos que tener en cuenta de lo grafos:

* Si el conjunto N es vacío, el grafo será vacío.
* Cada arco de un grafo establece una única relación entre nodos.
* No existerestricción en la relación que establece un arco, o sea, un nodo puede estar relacionado consigo mismo o con otro nodo.
* Cada arco se representa a través de un par, donde, cada elemento determina uno de los nodos.

Dado que no hay restricciones en cuanto a los arcos de un grafo, las estructuras como listas, arboles pueden ser consideradas como un grafo.

Ejemplo

Una lista linealpuede ser vista como un grafo donde cada nodo está relacionado con exactamente un nodo distinto de él.

Clasificación de los grafos

Podemos clasificar a los grafos en:

* Orientado o dirigido
* No orientado o no dirigido

Grafo no orientado

Un grafo es no orientado o no dirigido si el hecho de que el arco (N j, N k)...