Ensaño de Grafos

TAREA
Ensayo de Grafos y sus Aplicaciones.


Que son los grafos y sus aplicaciones.

Introducción.
Un grafo es un objeto unitario de naturaleza abstracta que abarca a las grafías que componen una letra. La palabra tiene origen griego y significa “imagen” o “dibujo”. Representación gráfica de diversos puntos que se conocen como nodos o vértices, loscuales se encuentran unidos a través de líneas que reciben el nombre de aristas. Al analizar los grafos, los expertos logran conocer cómo se desarrollan las relaciones recíprocas entre aquellas unidades que tienen algún tipo de interacción.
Según Guevara Los grafos son diagramas hechos de puntos y arista, es decir esto nos ayudara a resolver problemas de nuestra vida diaria ¿cómo nos ayuda y dequé forma a resolver estas incógnitas?

Desarrollo

En nuestra vida cotidiana no es una novedad ver carreteras, líneas telefónicas o televisión por cable, circuitos eléctricos de nuestra casas, o simple viaje en la arena como hizo Pascal que trazo un dibujo en la arena explicando las dimensiones grandes, hacia puntos y parecía unirlos al azar por segmentos, era un plano del metro de Montreal,aunque se trataba de una adaptación idealizada de la realidad que queremos representa, este plano preserva las propiedades reales importantes de la red que supone describir, ha estos puntos y aristas se llaman grafos.
Entonces podemos definir un grafo un conjunto de nodos unidos por un conjunto de líneas o flechas, es decir los nodos son objetos de procesamiento o estructuras que contienen algúntipo de información y las líneas o flechas son conexiones o relaciones entre estos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido por relaciones entre los nodos tienen una dirección, en cualquiera de los dos casos se utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.
Las aristas también tienen algún tipo de informaciónasociada (distancia, costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado. Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino que termina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.
Se dice que un grafo es conexo si se puede llegar desdecualquier nodo hasta
cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse en componentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son conexos.
Los dos algoritmos “clásicos” de recorrido de grafos son el recorrido en profundidad y en anchura. Precisamente por ser “clásicos” han sido estudiados con anterioridad y se les conoce suorden de complejidad en tiempo y todos los beneficios de aplicarlos.
• Recorrido en profundidad
Para efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo como punto de partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y si hay un nodo adyacente a este que no haya sido“visitado”, se toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina cuando todos los nodos hayan sido visitados.
• Recorrido en anchura
En este algoritmo también se utiliza la estrategia de marcas los nodos como
visitados para detectar la culminación del recorrido, pero los nodos se recorren de una manera ligeramente distinta. De nuevo, se selecciona cualquier nodo como puntode partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y luego se visitan todos los nodos adyacentes a este, al finalizar este proceso se busca visitar nodos más lejanos visitando los nodos adyacentes a los nodos adyacentes del nodo inicial.
Este algoritmo puede crear menos ambientes recursivos...