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:
Componentes de un Grafo
Tipos de Grafos
Grafo
regular
Aquel
con el mismo grado en todos los vértices.
Grafo
bipartito
Es
aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no
haya adyacencias entre vértices pertenecientes al mismo conjunto.
Grafo
completo
Aquel
con una arista entre cada par de vértices.
Grafo
nulo
Se
dice que un grafo es nulo cuando los vértices que lo componen no están
conectados, esto es, que son vértices aislados.
