Elementos y características de los grafos

Elementos y características de los 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, etc. 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 vertices 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 leíbles.

Grafo. Un conjunto de vértices V y de aristas E, tal que cada arista se asocia a un par de vértices.

Una arista “e” en un grafo asociada a vértices “a” y “b”, se dice, que es incidente en “a” y “b” y viceversa, que “a” y “b” son incidentes en “e”. Y por lo tanto que “a” y “b” son vértices adyacentes en “e”.

Si “G” es un grafo con vértices “V” y aristas “E”, entonces G = (V, E).

...