estructura de datos









INTRODUCCION


Este trabajo se elaboro para conocer los diferentes conceptos y conocer algunos de los diferentes grafos para aplicarlos a la programación y hacer proyectos mas elaborados.
Se verán ciertas aplicaciones de los grafos para el desarrollo de las nuevas aplicaciones que lo necesitan.
.


















OBJETIVOS

Conocer algunascaracterísticas de los grafos como están formados y como se aplican a la estructura de datos.
Aplicar los conceptos vistos para utilizarlos en programas más elaborados y de mayor calidad.


















QUE ES UN GRAFO
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjuntode nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, ungrafo, G, se define como un par ordenado, G = (V, E), donde V es unconjunto finito y E es un conjunto que consta de dos elementos de V.

Un grafo está formado por un conjunto de nodos y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.
El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,
C), (C, D), (C, F), (E, G), (A, A)}

Si los pares de nodos en los arcos dirigidos, el grafo se denominagrafo directo, dirigido o dígrafo.
TERMINOLOGÍA
1. Al número de nodos del grafo se le llama orden del grafo.
2. Un grafo nulo es un grafo de orden 0 (cero).
3. Dos nodos son adyacentes si hay un arco que los une.
4. En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A
5. Camino es una secuencia de uno o mas arcos que conectan dos nodos.
6. Un grafose denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario.
7. Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes.
8. El camino de un nodo así mismo se llama ciclo.

1. Un grafo sin ciclos es un árbol.
2. El entregado de un nodo indica el número de arcos que llegan a se nodo.
3. Elfuera de grado de un nodo indica el número de arcos que salen de él.
4. Un grafo de N vértices o nodos es un árbol si cumple las siguientes condiciones
a) Tiene N-1 arcos
b) Existe una trayectoria entre cada par de nodos.
c) Esta mínimamente conectado.
GRAFOS Y MULTIGRAFOS
Un grafo G consiste en dos cosas:
(1) Un conjunto V de elementos llamadosnodos (o puntos o vértices)
(2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único (Desordenado) par [u,v] de nodos de V, denotado por e-[v,u]. A veces denotamos un grafo escribiendo G=(V,E)
Un grafo G se dice que es conexo si existe un camino entre cualesquiera dos de sus nodos. Mostraremos en el problema 8.18 que si existe un camino P desde un nodo u a unnodo v, entonces eliminando las aristas innecesarias, se puede obtener un camino simple Q de u a v, de acuerdo con esto podemos establecer la siguiente proposición.
Se dice que un grafo G es completo si cada nodo u de G es adyacente a todos los demás nodos de G claramente, un grafo así es conexo, un grafo completo de n nodos tendrá n(n-1)2 aristas.
Un grafo conexo T sin ciclos se llama grafoárbol o árbol libre o simplemente árbol. Esto significa en particular, que existe un único camino simple P entre cada dos nodos u y e de
T (problema 8.18) mas aún, si T es un árbol de finito de m nodos, entonces T tendrá m -1 aristas (problema 8.20).
Un grafo G se dice que esta etiquetado si sus aristas tiene datos asignados. En particular, se dice que G tiene peso si cada arista e de G...