Grafos

Grafos.
El origen de la palabra grafo proviene de la lengua griego y su significado etimológico es "trazar".
Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos pueden ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación o también un organigrama, los grafos matemáticos que representan las relaciones binarias, unared de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad
Un grafo es básicamente un objeto geométrico aunque sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.
Debido a su generalidad y a la diversidad de formas, resulta complejo tratar con todas las ideasrelacionadas con un grafo.
Los grafos son estructuras de datos no lineales que tienen una naturaleza dinámica. Su estudio podría dividirse en dos grandes bloques:
· Grafos Dirigidos: Los arcos en el grafo tienen una dirección asociada. El primer elemento del arco es el origen y el segundo es considerado el destino
· Grafos no Dirigidos: Son aquellos en los cuales las aristas no están orientadas (Noson flechas).
Un grafo es una estructura de datos que almacena datos de dos tipos:
· Vértices o nudos, con un valor almacenado.
· Aristas o arcos: cada una conecta a un vértice con otro, y puede tener un valor almacenado.
Una arista es un par de vértices (v,w).
Si el par está ordenado, se dice que el grafo es dirigido o que es un dígrafo.
Un grafo está formado por un conjunto de nodos ovértices 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)} para el siguiente grafo.
Su Terminología
· Al número de nodos del grafo se le llama orden del grafo.
· Un grafo nulo es un grafo de orden 0 (cero).
· Dos nodos son adyacentes si hayun arco que los une.
· En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A
· Camino es una secuencia de uno o más arcos que conectan dos nodos.
· Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario.
· Un grafo es completo cuando cada nodo está conectado con todos y cada uno de los nodosrestantes.
· El camino de un nodo así mismo se llama ciclo.
Lazo o bucle
Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo nodo. Un grafo se dice simple si no tiene lazos y existe como mucho un enlace entre cada par de nodos (no hay enlaces en paralelo).
Un lazo o bucle o también llamado “Composición iterativa” permite ejecutar múltiples veces unas instrucciones. Lacantidad de veces se puede establecer mediante:
 Una condición:
o Se comprueba al principio: las instrucciones del lazo se hacen cero o más veces.
o Se comprueba al final: las instrucciones del lazo se hacen una o más veces.
 Un número fijo de veces: se usa una variable de control.
Existen Tipos de Bucles:
Bucles Infinitos

Se observa que la flecha que se regresa hacia arriba nos estáindicando que hay que volver a evaluar la expresión. Como el bucle es infinito, no se tiene una condición para terminar y se estará haciendo siempre.
Bucles Finitos

Bucles repetitivos
Existen tres diseños de estructuras cíclicas:
 Independientes: cuando los bucles se realiza uno primero hasta que se cumple la condición y solo se entra al bucle B.
 Aninados: Al entrar a una estructura derepetición, dentro de ella se encuentra otra. Se termina de realizar y se continúa con la externa hasta que la condición se cumple.
 Cruzados: Inicia un bucle y no se termina cuando empieza otro, luego se utiliza estructuras goto (saltos) para pasar al bucle externo y se quedan entrelazados.
Ocasiona que el programa pierda el control de lo que se está ejecutando y se puede obtener resultados...