UNIDAD 1 GRAFOS

UNIDAD 1 GRAFOS
1.1 INTRUCCION A GRAFOS
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos opuntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de las matemáticas discretas y de las matemáticas aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas comocombinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campode la informática, las ciencias de la computación y telecomunicaciones.





1.2 CAMINOS Y CICLOS
Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).
Por ejemplo, en un museo grande(al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de Camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puederecorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sinembargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

1.3 CICLOS HAMILTONIANO
Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además querecorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).
Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de Caminohamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempopolinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

1.4 ALGORITMOS DE RUTA MAS CORTA
El algoritmo del vecino máspróximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no el ideal.
Abajo está la aplicación del algoritmo del vecino más próximo al problema del viajante.
Estos son los pasos del algoritmo:
1. elección de un vértice arbitrario respecto al...