La Teoría de Gráficas (o Teoría de Grafos, para otros países) es un campo de las matemáticas increíble por su utilidad para modelar procesos y sistemas del mundo real.

No es ninguna sorpresa que este campo de estudio tenga una íntima relación con las Ciencias de la Computación, pues su estudio no solo abarca lo meramente teórico, sino que los algoritmos que han surgido son de suma importancia en cómputo teórico, distribuido, estructuras de datos, y muchas otras áreas importantes para los computólogos.

Esto probablemente es por la naturaleza discreta de las gráficas, y por lo adaptables que son. Son estructuras que nos permiten modelar todos aquellos sistemas que se pueden estudiar a partir de sus relaciones e interacción entre los distintos componentes.

Si bien el estudio de las gráficas es vasto, en este post me he propuesto el objetivo de explicar de manera superficial lo que son las gráficas, y a introducir algo de notación que probablemente será suficiente para que cualquier persona pueda comenzar su estudio sin un trasfondo matemático extenso.

Evidentemente la comprensión de los temas más avanzados será el resultado de un camino largo, que no podría resumir lo suficiente en este blog; porque no soy un experto en el tema, y porque tampoco pretendo alcanzar eso en este blog. Pero haré lo mejor posible para ayudar a aquellos que desean embarcarse en esta área tan interesante, y buscan comenzar desde lo básico.


¿Qué son las gráficas?

Comenzamos por lo esencial. En realidad hay variedad de formas de describir lo que son las gráficas, pero lo elemental siempre es el hecho de que las gráficas están compuestas por dos elementos:

  • Vértices (o nodos).

  • Aristas.

En las matemáticas es muy común el no describir las cosas por lo que son, sino por cómo se comportan. Ese es el caso de los vértices: realmente los vértices no tienen características concretas, sino que pueden tomar las propiedades de cualquier cosa. Podemos decir que nuestros vértices son personas en una red social, o que los vértices son números. Realmente, la identidad de los vértices no es relevante para el estudio de la estructura que forman, las gráficas.

Además, tenemos las aristas, que también son abstractas, pero lo esencial de estas es que relacionan vértices entre ellos.

Tenemos la ventaja de que las gráficas son fáciles de representar visualmente (al menos para los casos más sencillos). Generalmente su representación visual es similar a la siguiente:

Ejemplo de una gráfica.

Ejemplo de una gráfica.

Ejemplo de una gráfica.

Ejemplo de una gráfica.

Tenemos vértices representados por puntos, o círculos, y las aristas como líneas que unen a los vértices. En otros tipos de gráficas, como lo son las gráficas dirigidas, en vez de líneas utilizamos flechas.

Continuemos con la definición formal. Una definición que personalmente encuentro agradable para trabajar y no muy complicada de entender es la siguiente:

Una gráfica $G$ es una pareja $\left(V\left(G\right),E\left(G\right)\right)$ en donde $V(G)$ es un conjunto $A \neq \varnothing$ de elementos llamados vértices, y $E(G)$ es un subconjunto de $A \times A$ que llamamos aristas. Decimos que si dos vértices $u,v \in V(G)$ están relacionados, se cumple que la arista $(u, v) \in V(G)$.

Puede ser un poco denso a primero vista, pero vamos a diseccionar la definción anterior.

Lo primero a considerar es que tenemos un conjunto sobre el cuál trabajamos, en este caso se llama $A$. El conjunto no es nada especial, simplemente es un conjunto de elementos. Además, el conjunto no es vacío (no tiene caso trabajar con una gráfica vacía, ¿o sí?).

Ese conjunto $A$ va a ser el conjunto de nuestros vértices. Es un poco tedioso tener que especificar el nombre del conjunto, porque en general ni siquiera sabemos cuáles son los elementos de ese conjunto, entonces, mejor usaremos la siguiente notación: $V(G)$ es el conjunto de vértices de nuestra gráfica $G$.

Ahora que tenemos vértices, necesitamos comenzar a relacionarlos entre sí. Una manera sencilla de hacerlo es creando parejas $(u,v)$ donde $u$ y $v$ son vértices. Y eso es lo que representa $A \times A$: todos los posibles pares de vértices. Ahora, no siempre queremos que todos los vértices se relacionen entre sí; probablemente solo queremos que algunos vértices se relacionen, o probablemente queremos que ninguno tenga relación con otro. Es por eso que decimos que tomamos un subconjunto de $A \times A$. Ese subconjunto lo nombramos $E(G)$ (por la palabra ‘arista’ en inglés, ‘edge’).


Grados

Ahora veamos algunas propiedades de estas, y la notación que usamos para expresarlas.

Una propiedad muy importante y utilizada es el grado de un vértice. Definimos al grado de un vértice como el número de aristas que inciden en él. La notación que utilizamos, para un vértice $v$, es $deg(v)$. También es común ver $d(v)$ por ser más corto y conveniente. En realidad, el concepto de grado es bastante sencillo, y es fácil de entender a partir de su representación visual. Por ejemplo, podemos fácilmente ver que el vértice $a$ tiene grado $3$, mientras que el vértice $b$ tiene grado $5$.

El vértice $a$ tiene grado $3$ y el vértice $b$ tiene grado $5$.

El vértice $a$ tiene grado $3$ y el vértice $b$ tiene grado $5$.

El vértice $a$ tiene grado $3$ y el vértice $b$ tiene grado $5$.

El vértice $a$ tiene grado $3$ y el vértice $b$ tiene grado $5$.

Además, muchas veces nos interesa conocer cuál es el menor grado en una gráfica. La notación para el grado mínimo de una gráfica es $\delta(G)$. En el siguiente ejemplo podemos ver que el grado mínimo es $1$, y corresponde al vértice $a$.

$\delta(G)=1$.

$\delta(G)=1$.

$\delta(G)=1$.

$\delta(G)=1$.

Así como tenemos el grado mínimo, también podemos necesitar una manera de expresar el grado máximo de una gráfica, sin saber exactamente el número. Por lo tanto, lo escribimos como $\Delta(G)$. En la siguiente gráfica, podemos ver que el grado máximo es $4$.

$\Delta(G)=4$.

$\Delta(G)=4$.

$\Delta(G)=4$.

$\Delta(G)=4$.


Caminos

Definimos un camino en una gráfica como una sucesión de vértices:

$$ P = (v_{1}, v_{2}, v_{3}, \dots, v_{i}) $$

Además, se cumple que para todos dos vértices que se siguen en el camino, estos deben estar unidos por una arista.

Un ejemplo de camino en una gráfica es el siguiente:

$uv$-camino en color rojo.

$uv$-camino en color rojo.

$uv$-camino en color rojo.

$uv$-camino en color rojo.

A partir de esta definición surgen distintos tipos de caminos con distintas propiedades.

Paseo

Un paseo es un camino que cumple con la propiedad de no repetir aristas.

$uv$-paseo en color rojo.

$uv$-paseo en color rojo.

$uv$-paseo en color rojo.

$uv$-paseo en color rojo.

Un paseo no tiene restricciones con respecto a repetir vértices. Además podemos hablar de paseos cerrados. Un paseo cerrado es aquel que comienza y termina en un mismo vértice.

Trayectoria

Una trayectoria es un camino que no repite vértices. Al no poder repetir vértices, se cumple que no repite aristas. Por lo tanto, una trayectoria también es un paseo (aunque el inverso no necesariamente se cumple).

$uv$-trayectoria en color rojo.

$uv$-trayectoria en color rojo.

$uv$-trayectoria en color rojo.

$uv$-trayectoria en color rojo.

Ciclo

Un ciclo es un camino cerrado, es decir, comienza y termina en un mismo vértice. Además, no repite vértices. Por lo anterior, podemos afirmar que un ciclo es un camino, paseo y trayectoria (de nuevo, los inversos no necesariamente se cumplen).

Ciclo en color rojo.

Ciclo en color rojo.

Ciclo en color rojo.

Ciclo en color rojo.


Conexidad

El tema de conexidad es algo que bien podría abarcar su propio post (y tengo la intención de hacerlo), o incluso más. No obstante, por ahora me limitaré a definir lo que es una gráfica conexa y disconexa.

Decimos que una gráfica es conexa si existe un camino entre cualesquiera dos vértices de esta gráfica. De manera opuesta, si existe algún vértice que no está conectado por un camino con otro vértice, decimos que la gráfica es disconexa.

Grafica conexa a la izquierda, no conexa a la derecha.

Grafica conexa a la izquierda, no conexa a la derecha.

Grafica conexa a la izquierda, no conexa a la derecha.

Grafica conexa a la izquierda, no conexa a la derecha.

Además, podemos hablar de los componentes de la gráfica. Decimos que un componente conexo en una gráfica es una subgráfica con todos los vértices conexos entre sí. En una gráfica conexa, decimos que tenemos un solo componente. En gráficas disconexas, tenemos al menos 2.

Componentes en rojo.

Componentes en rojo.

Componentes en rojo.

Componentes en rojo.


Isomorfismos

Digamos que tenemos dos gráficas $G$ y $H$. Probablemente lucen distintas al visualizarlas, por ejemplo:

¡Ambas gráficas son isomorfas!

¡Ambas gráficas son isomorfas!

¡Ambas gráficas son isomorfas!

¡Ambas gráficas son isomorfas!

No obstante, nos damos cuenta de que podemos desplazar los vértices y resulta que ambas gráficas lucen iguales. Entonces, podemos decir que $G \cong H$ ($G$ es isomorfa a $H$).

Lo anterior se refiere a la representación visual. Pero en su representación abstracta, ¿qué es un isomorfismo?. Un isomorfismo es una función biyectiva (es decir, uno a uno) entre los vértices de $G$ y los vértices de $H$. Esa función cumple con que relaciona los vértices de una manera que preserva las adyacencias de los vértices.

Es decir, si los vértices $u_{1}, u_{2} \in V(G)$ están relacionados por una arista, los vértices $v_{1}, v_{2} \in V(H)$ también estarán relacionados por una arista.

Mapeamos los vértices con la función en rojo.

Mapeamos los vértices con la función en rojo.

Mapeamos los vértices con la función en rojo.

Mapeamos los vértices con la función en rojo.


Gráficas Bipartitas

En muchos casos queremos clasificar nuestros vértices en categorías, o agruparlos dada una condición.

A pesar de que es posible agruparlos de muchas maneras, un método que utilizamos muy comúnmente para agrupar vértices es con gráficas bipartitas.

Una gráfica bipartita.

Una gráfica bipartita.

Una gráfica bipartita.

Una gráfica bipartita.

Las gráficas bipartitas son aquellas en las que podemos dividir los vértices en dos grupos. Cada uno de los dos grupos debe tener al menos un vértice, y se debe cumplir que los vértices en el grupo $A$ solo se relacionan con vértices en el grupo $B$, y viceversa.

Utilizando notación, decimos que una gráfica $G$ es bipartita cuando:

  • $V(G) = A \uplus B$

  • $A \neq \varnothing$ y $B \neq \varnothing$

  • $\forall a \in A \forall b \in V(G), ab \in E(G) \rightarrow b \in B$

  • $\forall b \in B \forall a \in V(G), ab \in E(G) \rightarrow a \in A$


Ya vimos qué son las gráficas, y la notación que usamos para expresar los vértices y las aristas. Igual, podemos distinguir el grado de un vértice, y tenemos una forma de expresar los grados mínimo y máximo de una gráfica. Vimos lo que son los caminos que podemos encontrar dentro de una gráfica, y cómo podemos clasificarlos. Ya sabemos lo que es una gráfica conexa y una gráfica no conexa. También vimos algunos tipos de gráficas como lo son las gráficas bipartitas, y los isomorfismos.

Si bien puede ser un poco abrumador para alguien entender estos conceptos a la primera, con un poco de análisis y reflexión podemos comprenderlos. Realmente son ideas simples, sin un alto grado de complejidad. Pero son suficientemente elementales como para dar lugar a miles de libros, artículos, investigaciones y cursos sobre el tema.

Esta introducción fue bastante resumida, pues todavía hay mucho de qué hablar. Sin embargo, creo que siendo capaz de entender estos conceptos, uno está preparado para avanzar en el tema y poder indagar a mayor profundidad. Como todo en matemáticas, una vez que hemos sentado las bases, podemos comenzar a construir sobre ello.