6.1 Elementos y Características de los Grafos

 

 

Componentes de un Grafo

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.

 

 

Es 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).

Ejemplo de un grafo:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

En este ejemplo podemos observar que la arista “b” en el grafo se encuentra asociada a los vértices “2” y “3”. Por lo tanto, se dice que el “b” es incidente en “2” y “3” y viceversa, que “2” y “3” son incidentes en “b”. En conclusión “2” y “3” son vértices adyacentes en “b”. Esto es: “b” = (2, 3), que significa que existe una arista entre “2” y “3” llamada “b”.

También podemos observar:

V = {1, 2, 3, 4, 5} Vértices

E = {a, b, c, d, e, f, g, h, i } Aristas (Edges en inglés)

G = { (1, 2), (3, 2), (5, 3), (4, 5), (1, 4), (2, 4), (2, 5), (1, 3), (5, 1)} Grafo

Lazo: Es una arista incidente en un sólo vértice. Ejemplo: a6 = (V5, V5).

 

 

 

 

 

 

 

 

 

 

 

Aristas paralelas. Cuando dos o más aristas están asociadas con el mismo par de vértices. Ejemplo: las aristas a2 y a3 de la Figura 2 están asociadas al mismo par de vértices. Es decir: a2 = (V1, V3) y a3 = (V1, V3).

Vértice aislado. El vértice que no es incidente en alguna arista. Ejemplo:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Grado o valencia de un vértice “v”. Es el número de aristas incidentes en “v”. Ejemplo:

Grado o Valencia de la Figura 2

 

 

 

 

 

 

 

 

Subgrafos. Parte de un grafo.

 

 

 

 

 

 

Ejemplo, algunos subgrafos de este grafo serían los siguientes: