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

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:

Figura 3

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

V1 V2 V3 V4 V5

3 3 5 1 3

Subgrafos. Parte de un grafo.

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

Grafos simples.- Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multigrafo.

Grafo completo.- Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 aristas.

La representación gráfica de los como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• V1 y V2 son disjuntos y no vacíos.

• Cada arista de A une un vértice de V1 con uno de V2.

• No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Grafos Planos.- Un grafo G es planar si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama representación plana del grafo.

Grafo conexo.- Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir,

G es conexo ⇐⇒ ∀u, v : ∃µ = [u, v]

En

...