Teoria de grafos

Introducción
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelizar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.
En numerosos problemas cuantificables, en las organizaciones, intervienen una serie deelementos entre los que se establecen unas relaciones: por ejemplo, los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificación de proyectos mediante PERT) o estructuras de producto complejas (gestión de inventarios mediante MRP).
Los grafos son una herramienta que permite modelizar relaciones de estanaturaleza, de modo que se puedan resolver problemas asociados a esas circunstancias, frecuentemente de forma menos costosa que utilizando otras técnicas como la programación lineal.
Una buena comprensión de la teoría de grafos pasa por dominar la nomenclatura y conceptos asociados a estas representaciones de relaciones entre elementos, así como sus diversas formas de representación.

Definición deGrafo
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representamediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
Definición Formal
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar,notaremos la arista (a,b) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o lared de drenaje de una ciudad.
Subgrafo
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).

Arista
Una arista o arco es una relación matemática que conecta dos vértices. Una arista dirigida es unaarista de un digrafo y tiene una dirección asociada consigo, esto es, posee un vértice inicial y un vértice final. Una arista no dirigida es una donde no se distingue un vértice inicial ni uno final
Aristas dirigidas y no dirigidas
En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. Elconjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a).
Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).
En elgrafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.
Aquí V={ a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.
Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la...