Conceptos Fundamentales de la Teoría de Grafos: Definiciones y Teoremas Clave

Fundamentos de Grafos y Dígrafos

Grafo Dirigido o Dígrafo

Un Grafo Dirigido (o Dígrafo, también llamado grafo orientado, simple y finito) es un par $G = (W, F)$ formado por dos conjuntos finitos:

• $W \neq \emptyset$: El conjunto de sus vértices o nodos.
• $F \subseteq W \times W$: El conjunto de sus arcos o flechas.

Cada flecha $e \in F$ es un par ordenado de dos vértices $e = (v, w) \in W \times W$, que llamaremos, respectivamente, inicio y fin de la flecha.

Grafo No Orientado

Un Grafo No Orientado (simple y finito) es un par $G = (W, F)$ formado por dos conjuntos finitos:

• $W \neq \emptyset$: El conjunto de sus vértices.
• $F \subseteq \{\{v, w\} / v, w \in W \text{ y } v \neq w\}$: El conjunto de sus lados o aristas.

Grafos Isomorfos

Dos grafos $G_1 = (W_1, F_1)$ y $G_2 = (W_2, F_2)$ (o dígrafos, respectivamente) diremos que son isomorfos si existe una aplicación $f: W_1 \to W_2$ biyectiva tal que, $\{v, w\} \in F_1$ (resp. $(v, w) \in F_1$) si y solo si $\{f(v), f(w)\} \in F_2$ (resp. $(f(v), f(w)) \in F_2$).

Subgrafo

Dado un grafo (resp. grafo dirigido) $G = (W, F)$, diremos que otro grafo (resp. grafo dirigido) $G_1 = (W_1, F_1)$ es un subgrafo de $G$ si $W_1 \neq \emptyset$, $W_1 \subseteq W$ y $F_1 \subseteq F$, donde cada lado (resp. flecha) de $F_1$ es incidente con vértices de $W_1$.

Nota sobre Subgrafo Maximal

Si un subgrafo es tal que $W_1 = W$, se dirá que es un subgrafo maximal.

Conectividad y Distancia en Grafos

Camino

Sea $G = (W, F)$ un grafo no orientado. Un camino $c$ es una sucesión finita de vértices $c = \{v_1, v_2, \dots, v_{n+1}\}$, con $v_i \in W$ para cada $i = 1, 2, \dots, n+1$; tales que dos vértices consecutivos son adyacentes. Esto es, verificando $\{v_i, v_{i+1}\} = e_i \in F$ para cada $i = 1, 2, \dots, n$.

Teorema del Número de Caminos

Sea $G = (W, F)$ un grafo (resp. un grafo dirigido) con matriz de adyacencia $A$ para $W = \{v_1, v_2, \dots, v_n\}$. Entonces, el número de caminos (resp. caminos orientados) de longitud $l$ que conectan los vértices $v_i$ y $v_j$ coincide con la coordenada $(i, j)$-ésima de $A^l$.

Corolario de la Distancia

La distancia de un vértice a otro es el número $l$ al que se ha elevado la matriz de adyacencia $A^l$, y el número de geodésicas es la coordenada $a_{i, j}$ de dicha matriz.

Distancia

Sea $G$ un grafo (resp. dirigido). Llamaremos distancia entre dos vértices $d(u, v)$ a la longitud de cualquiera de los caminos (resp. caminos orientados) más cortos que conectan $u$ con $v$. A estos caminos (los de menor longitud) los llamaremos geodésicas.

Circuitos, Coloración y Propiedades Estructurales

Grafo de Euler

Sea $G = (W, F)$ un grafo (resp. grafo dirigido) sin vértices aislados. Un camino simple (resp. un camino orientado simple) que pase por todos los lados (resp. flechas) del grafo se dice que es de Euler.

Un camino (resp. orientado) de Euler cerrado se dirá que es un ciclo o circuito de Euler. Un grafo que posea al menos un ciclo de Euler se llamará grafo de Euler.

Condiciones de Euler

• Grafos No Orientados: El grado de cada vértice es par.
• Grafos Orientados: El grado de entrada de cada vértice coincide con el de salida.

Grafo de Hamilton

Sea $G = (W, F)$ un grafo con más de tres vértices (resp. grafo dirigido). Un camino elemental (resp. un camino orientado elemental) que pase por todos los vértices del grafo se dice que es de Hamilton.

Un camino (resp. orientado) de Hamilton cerrado se dirá que es un ciclo o circuito de Hamilton. Un grafo que posea al menos un ciclo de Hamilton se llamará grafo de Hamilton.

Coloración

Colorear un grafo $G$ consiste en asignar colores a cada vértice de forma que a dos vértices adyacentes no se les asigne un mismo color. Si el número de colores usado en una coloración de $G$ es $n$, entonces diremos que tenemos una $n$-coloración de $G$.

Al menor $n$ para el cual conseguimos una $n$-coloración se le llama número cromático de $G$. En tal caso, se dice que $G$ es $n$-cromático. Una coloración óptima será una $n$-coloración donde $n$ es el número cromático del grafo.

Estructuras Especiales: Bipartitos, Planos y Árboles

Grafo Bipartito

Un grafo $G = (W, F)$ (no dirigido) se dirá bipartito si existen dos subconjuntos no vacíos de vértices $W_1, W_2 \subseteq W$ tales que:

1. $W_1 \cap W_2 = \emptyset$
2. $W = W_1 \cup W_2$
3. El subgrafo inducido por $W_1$, $\langle W_1 \rangle = G_1 = (W_1, \emptyset)$, no tiene aristas.
4. El subgrafo inducido por $W_2$, $\langle W_2 \rangle = G_2 = (W_2, \emptyset)$, no tiene aristas.

Esto significa que todos los lados son incidentes con un vértice de $W_1$ y otro de $W_2$.

Relación con la Coloración

Si un grafo es 2-coloreable, es bipartito.

Notación $K_{n, m}$

Cuando se utiliza la notación $K_{4, 2}$, los números 4 y 2 representan el número de vértices de cada subconjunto (partición) del grafo bipartito completo.

Grafo Plano

Un grafo se dirá plano si podemos representarlo gráficamente en el plano de forma que no se corten sus lados.

Árbol y Bosque

Un árbol es un grafo conexo y sin ciclos elementales (circuitos).

Un bosque es un grafo sin ciclos elementales; es decir, es un grafo donde cada componente conexa es un árbol.

Teorema Fundamental de Árboles

Dado $G$ un $(p, q)$-grafo conexo (donde $p$ es el número de vértices y $q$ el número de aristas), entonces: $G$ es un árbol si y solo si $p = q + 1$.