Teoria De Grafos

TEORIA DE GRAFOS

Los grafos han sido utilizados hace miles de años atrás, actualmente se utilizan en varias ciencias como la química, computación, economía, investigación de operaciones, etc.Existen una gran variedad así como tipos y propiedades de los grafos, se pueden utilizar para la resolución de un problema, por ejemplo calcular la distancia más corta de un punto a otro teniendo encuenta varios caminos.
En un grafo existen puntos que son llamados vértices o nodos, así como también el conjunto de pares de vértices se les llama arista, lados o ramas.
Los grafos tienen muchascaracterísticas, a continuación hare mención de algunas: las aristas tienen un sentido, ya sea que sean dirigidos o no dirigidos, por ejemplo en algunas ocasiones va a ser necesario representar el mapa deuna ciudad y habrá calles que no tienen doble sentido por lo que se especificara su único sentido, si no se le especificara esto se le conocería como bidireccionales; un grafo simple es aquel que notiene ni lazos ni segmentos múltiples, un lazo es aquel que inicia en un vértice y termina en ese mismo vértice, pasando solo por un arista, mientras que un segmento múltiple son diferentes segmentosque están uniendo a un mismo par de nodos; y un grafo complejo es en el que si existen lasos y segmentos múltiples; un grafo plano es aquel que se puede dibujar sin que haya cruces en sus aristas, de locontrario sería un grafo no plano. Un grafo es no conexo si no se puede establecer un camino para unir dos vértices.
Un nodo aislado es aquel en donde no hay un segmento que lo una con los demás. Ungrafo rotulado es cuando llegan a tener un valor ya establecido de lo contrario es un grafo no rotulado; un grafo completo es aquel en el que hay segmento unidos con nodos, si llegase a existe unnodo aislado, ya no es completo.
Un camino en los grafos es una secuencia de aristas que (v1, v2, v3…vn) el vértice final es donde inicia el otro arista. Existen varios tipos de caminos uno es el...