Teoria de grafos

Teoría de Grafos

En la vida cotidiana nos encontramos con numerosos problemas cuantificables, así como en las organizaciones, intervienen una serie de elementos entre los cuales se establecen relaciones: por ejemplo tenemos los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificación de proyectosmediante PERT) o estructura de producto compleja (gestión de inventarios mediante MRP). También podemos citar la psicología en dinámica de grupos, la sociología en los sociogramas, la física teórica, que usa los diagramas de Feynmann, donde se representan mediante líneas las partículas elementales, el estudio de flujos en redes en programación lineal e investigación operativa, los cambios de variableen el cálculo diferencial.
Para este tipo de problemas Los grafos son una muy buena herramienta que nos permite modelizar relaciones de este tipo de naturaleza, de forma que se puedan resolver problemas asociados a esas circunstancias, frecuente de forma menos que utilizando otras técnicas como la programación lineal.
La mencionada Teoría de Grafos (también llamada teoría de las graficas)estudia las propiedades de los grafos (también llamadas graficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (nodos) y una selección de pares de vértices, llamados aristas (edges en ingles) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Historia
La teoría de grafos tiene suorigen en el problema de los siete puentes de Königsberg resuelto gracias al trabajo de Leonhard Euler, en 1736. También se considera uno de los primeros resultados topológicos en geometría en geometría (que no depende de ninguna medida). Como ejemplo ilustrativo entre la teoría de grafos y la topología tenemos la siguiente imagen que además ilustra el problema de los siete puentes de Königsbergde Euler.

En 1845 Gustav Kirchhoff publico sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.
En 1852 Francis Guthrie planteo el problema de los cuatro colores que plantea si es posible, utilizando solo cuatro colores, colorear cualquier mapa de países de tal forma que dos países con unafrontera en común nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

Definiciones
Grafo.
Ya se menciono anteriormente que es un grafo, pero formalmenteun grafo es una pareja de conjuntos
G = (V,A), donde V es un conjunto de vértices (puntos), y A es el conjunto de Aristas, que es un conjunto de pares de la forma (u,v) tal que u,v∈V, tal que u ≠v. Para simplificar, la arista {a,b} se denota 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. Laposición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Si no se considera el orden de los vértices en cada pareja, dichos pares se denominan aristas, y decimos
que el grafo es no orientado.
Si se consideran las relaciones, el par de aristas se llama arco y el grafo es orientado. Un grafo
no orientado puede siempre convertirse en orientado, expresando ladoble relación entre los vértices.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Subgrafo.
Un Subgrafo de un grafo G es un grafo cuyo conjuntos de vértices y aristas son subconjuntos de los G. Se dice que un grafo G contiene a otro grafo H si algún Subgrafo de G es H o es...