Teoria de grafos

                               TEORIA DE GRAFOS

La teoría de grafos tiene su origen en el problema de los siete puentes de
Königsberg resuelto por Leonhard Euler.
Más tarde, otros problemas influyeron en el desarrollo de la teoría de grafos
como el estudio de las redes eléctricas, la enumeración de isómeros de
hidrocarburos,...
Hoy en día es rara la disciplina científica o humanística que no utiliza la teoría
de grafos. Como ejemplos 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 variable en el cálculo diferencial...
Dibujar un grafo para resolver un problema es un reflejo muy común, que no
precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y
consta de vértices y de aristas que reúnen algunos de ellos.

En la teoría de los grafos, sólo se queda lo esencial del dibujo: la forma de las
aristas no son relevantes, sólo importan sus extremidades (o cabos); la
posición de los vértices tampoco, y se puede variar para obtener un grafo más
claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman
isomorfismos de grafos. Generalmente, se considera que colocar los vértices
en forma de polígono regular da grafos muy legibles.

Formalmente: Un grafo es una pareja G = (V, A), donde V es un conjunto de
puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas
aristas. Para simplificar, la arista {a,b} se denota ab.
En la figura, V = {a, b, c, d, e, f}, y A = {ab, ac, ae, bc, bd, df, ef}.
Una red de autovías que conectan ciudades, una red eléctrica, un alcantarillado
se pueden modelizar con grafos.

http://enciclopedia.us.es/index.php/Teor%C3%ADa_de_grafos