grafos y clasificasion

INSTITUTO TECNOLOGICO SUPERIOR DE MACUSPANA




ALUMNO:
CESAR AGUSTO RODRIGUEZ NIETO

CATEDRATICO:
ING: DANIEL ÁLVAREZ GARCÍA

MATERIA:
Programación en tiempo real

NOMBRE DEL REPORTE:
Investigación unidad 1

CARRERA:
ING MECATRONICA

FECHA:
25/febrero /2013


GRAFOS
Este software pretende ser de utilidad para la docencia y el aprendizaje de lateoría de grafos (graphtheory), y otras disciplinas relacionadas como la ingeniería de organización industrial, la logística y el transporte, investigación operativa, el diseño de redes, etc. Grafos se puede usar perfectamente para el modelado y resolución de problemas reales de cierto tamaño y complejidad.
Un grafo representa un modelo de una realidad empresarial en forma de red. Este modelo podrá ser analizado desdedistintos puntos de vista gracias a los algoritmos y funciones incorporados en el software Grafos. Independientemente de sus conocimientos actuales sobre la materia, la información recogida en estas páginas y el libro serán un buen punto de partida para el aprendizaje en mayor profundidad de la teoría de grafos y su aplicación en la realidad empresarial e industrial.

La filosofía de Grafos es lasiguiente: “dibujar, modelar, resolver y analizar”. Con esto se pretende que el usuario tenga libertad absoluta para tratar y abordar los problemas de grafos. Usted podrá dibujar libremente el grafo sin preocuparse del análisis o algoritmo que utilizará posteriormente. Grafos le avisará en caso de no factibilidad o de cualquier otro requerimiento para un análisis en particular.
Los estudiantesque usen Grafos experimentarán un proceso de aprendizaje basado en su libertad y en etapas de prueba-error. Esa libertad en la utilización del programa y su filosofía de aprendizaje, fue la idea inicial y la inquietud que originó este proyecto. Otros programas existentes guían al usuario paso a paso, descartando de entrada su libertad de elección y construcción.
En concreto dicho autor realizó unartículo basándose en los puentes que existen en la ciudad de Kaliningrado. A partir de ellos, y mediante lo que es la teoría de los grafos, desarrolló una exposición acerca de los grafos y los vértices que se sustenta en el hecho de que es imposible regresar al vértice que ejerce como punto de partida sin antes no pasar por alguna de las aristas en dos ocasiones.
Los grafos pueden serclasificarse de diversas maneras según sus características. Los grafos simples, en este sentido, son aquellos que surgen cuando una única arista logra unir dos vértices. Los grafos complejos, en cambio, presentan más de una arista en unión con los vértices.
Por otra parte, un grafo es conexo si dispone de dos vértices conectados a través de un camino. ¿Qué quiere decir esto? Que, para el par de vértices(p, r), tiene que existir algún camino que permita llegar desde p hasta r.
En cambio, un grafo es fuertemente conexo si el par de vértices tiene conexión a través de, como mínimo, dos caminos diferentes.
Un grafo simple, además, puede ser completo si las aristas están en condiciones de unir todos los pares de vértices, mientras que un grafo es bipartito si sus vértices surgen por la unión de unpar de conjuntos de vértices y si se cumple una serie de condiciones.



CAMINOS Y CICLOS
SIMPLE.- Cuando un camino entre dos vértices solo pasa una vez por cualquiera de los vértices el camino se denomina simple. Esto se aplica a un ciclo.
LONGITUD DE UN CAMINO.- Se define como la suma de las longitudes de las aristas del camino.
DEFINICIÓN: Sea G = (V,A), un grafo no dirigido. Para x, y ЄV,se dice que hay un camino en G de x a y , si existe una sucesión no vacia finita de aristas distintas de A. Cuando x= y, el camino se denomina ciclo. El numero de aristas de un camino (ciclo) se denomina longitud del camino (ciclo).
EL CAMINO MAS CORTO.- Un problemas de gran interes es determinar el camino mas corto de un vértice hasta otro vértice. Existen varios procedimientos bien conocidos...