Grafos es un tema muy útil para la informática y que ayuda a entender determinados problemas y estructuras de datos.

Definiciones elementales

Definición

Un grafo es un par

G = (V, E)

donde

V

es un conjunto finito de elementos llamados vértices/nodos y

E

es un conjunto finito de elementos llamados ejes/aristas.

Si los ejes son pares no ordenados de vértices de $V$ , se dice un grafo no dirigido.
Si los ejes son pares ordenados de vértices de $V$ , se dice un grafo dirigido / digrafo.

Si un vértice no está conectado a otro por ningún eje, se llama nodo aislado.
Si un par de vértices están conectados por más de un eje, se llaman ejes paralelos / múltiples.
Si un eje conecta un nodo con él mismo, se llama un lazo.

Los grafos se suelen representar con puntos para los nodos y líneas que los unen representando los ejes.

El grafo anterior no es dirigido, tiene dos ejes paralelos entre $A$ y $B$ , además de otros dos entre $B$ y $D$ . $C$ tiene un lazo y $E$ es un nodo aislado.

Y este es un grafo dirigido o, directamente, digrafo.

Definición

Un par de vértices son adyacentes / vecinos cuando existe un eje que los conecta. Se dice que el eje incide sobre los vértices

v_1

v_2

si el eje

e = \Set{v_1, v_2}

los conecta. En ese caso,

v_1

v_2

son los extremos del eje

e

Definición

Sea $G = (V, E)$ un grafo cualquiera.

$|V|$ es el orden del grafo $G$ (número de vértices)
$|E|$ es el tamaño del grafo $G$ (número de ejes)

El grado de un vértice

Definición

El grado de un vértice

v

\delta(v)

, es el número de ejes incidentes.

Por tanto,

\delta(v) = 0 \iff v \text{ es aislado.}

Además, se puede definir la sucesión de grados de un grafo $G$ :

$$ {\big\\{ \delta(v) \big\\}}_{v \in V} $$

Lema del Apretón de Manos

Las suma de todos grados de los vértices es dos veces el número de ejes.

\sum_{v \in V} \delta(v) = 2 |E|

Corolario

El número de vértices de grado impar, es par.

Según el Lema del Apretón de Manos, podemos poner la suma de todos los grados de la siguiente forma:

\overbrace{\sum_{v_2 \in V_2} \delta(v_2)}^{\text{Siempre par}} + \overbrace{\sum_{v_1 \in V_1} \delta(v_1)}^{\text{???}} = \overbrace{2 |E|}^{\text{Siempre par}}

Por tanto, $???$ tiene que ser impar.

Donde $V_2$ es el conjunto de los vértices de grado par y $V_1$ los vértices de grado impar.

Grafos simples

Definición

Un grafo se llama simple si no tiene lazos ni ejes paralelos.

Varios ejemplos de grafos simples:

Si un grafo es simple, entonces

\forall v \in V, \quad 0 \le \delta(v) \le |V| - 1

Definición

Si un grafo es simple y todos los vértices tienen el mismo grado

r

, entonces el grafo es $r$ -regular.

Subtipos de grafos simples:

Operaciones con grafos

Subgrafos

Definición

Sean $G = (V, E)$ y $G’ = (V’, E’)$ dos grafos.

Si $V’ \subset V$ y $E’ \subset E$ , $\implies$ $G’$ es un subgrafo de $G$ .

Por ejemplo,

Resta de grafos

Definición

Sea $G = (V, E)$ un grafo y $U \subset V$ , $U \ne \empty$ .

Sea $G - U$ el subgrafo de $G$ que se obtiene al eliminar los vértices $U$ del grafo $G$ (y los ejes incidentes).

Por ejemplo,

Isomorfismo de grafos

Definición

Sean $G = (V, E)$ y $G’ = (V’, E’)$ dos grafos.

Se dice que $G$ y $G’$ son isomorfos si existen las aplicaciones biyectivas

\begin{align*} \varphi : V &\longrightarrow V' \newline \psi : E &\longrightarrow E' \end{align*}

de forma que se cumpla

\allowbreak e = \Set{v_i, v_j} \in E \iff \psi(e) = \Set{\varphi(v_i), \\; \varphi(v_j)} \in E'

Es decir, que se mantenga la incidencia entre los mismos nodos.

Importante

Determinar si dos grafos son isomorfos es un problema NP.

Definición

Las invariantes son propiedades que se conservan entre dos grafos isomorfos y que pueden ayudar a determinar si lo son o no.

Ejemplos de algunos invariantes son:

El orden o número de vértices, $|V|$ .
El tamaño o número de ejes, $|E|$ .
La sucesión de grados, $\Set{\delta(v_i)}_{i = 1}^{|V|}$ .

Representación de grafos

Tabla de adyacencia

En una columna se colocan todos los vértices y en la otra se listan todos los vértices que están conectados con él.

Por ejemplo, la tabla de adyacencia siguiente:

Corresponde con este grafo:

Matriz de adyacencia

Definición

La matriz de adyacencia de un grafo

G

es una matriz de orden

|V| \times |V|

A_G = (a_{i j})

donde

a_{i j}

es el número de ejes que conectan el vértice

v_i

con

v_j

La matriz de adyacencia del grafo anterior sería la siguiente:

A_G = \begin{pmatrix} \newline 0 & 1 & 1 & 1 \newline 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \end{pmatrix}

Otro ejemplo:

A_{G'} = \begin{pmatrix} \newline 0 & 2 & 1 & 1 & 1 \newline 2 & 0 & 0 & 0 & 1 \newline 1 & 0 & 1 & 1 & 0 \newline 1 & 0 & 1 & 0 & 1 \newline 1 & 1 & 0 & 1 & 0 \end{pmatrix}

Observación

Las matrices de adyacencia para grafos no dirigidos siempre son simétricas, dado que un eje conecta vértices en los dos sentidos.

Observación

Si el grafo es simple, la matriz será binaria con 0s en la diagonal.

Observación

La suma de la fila o columna (contando dos veces la diagonal) es el grado del vértice.

2a_{i i} + \sum_{j \ne i} a_{i j} = \delta(v_i) = 2a_{i i} + \sum_{k \ne i} a_{k i}

Matriz de incidencia

Definición

La matriz de incidencia de un grafo $G$ es una matriz de orden $|E| \times |V|$ , $C_G = (c_{i j})$ donde

c_{i j} = \begin{cases} 1 \qquad \text{Si

(siempre es una matriz binaria)

La matriz de incidencia para $G$ es

\begin{pmatrix} \newline 1 & 1 & 1 \newline 1 & 0 & 0 \newline 0 & 0 & 1 \newline 0 & 1 & 0 \end{pmatrix}

Caminos de un grafo

Definición

Sea $G = (V, E)$ un grafo.

Un camino o trayectoria de un vértice $v$ a otro $w$ es una secuencia de ejes de $G$ (no necesariamente distintos) de la forma

e_1 = \Set{v, v_1}, \\; e_2 = \Set{v_1, v_2}, \\; \ldots, \\; e_n = \Set{v_n, w}

El número de ejes ( $n$ ) es la longitud del camino.
Un camino donde $v = w$ (el vértice inicial es el vértice final) es un camino cerrado / ciclo / circuito.
Un camino donde todos los ejes son distintos se llama camino simple.

Teorema

Sea

G

un grafo,

|V| = n

, y

A

la matriz de adyacencia de

G

. El número de caminos de longitud

k

que hay entre

v_i

v_j

es la entrada

a_{i j}

de la matriz

A^k

Ejemplo:

Y la matriz de incidencia:

A = \begin{pmatrix} \newline 0 & 0 & 0 & 1 \newline 0 & 1 & 1 & 1 \newline 0 & 1 & 1 & 2 \newline 1 & 1 & 2 & 0 \newline \end{pmatrix} \implies A^3 = \begin{pmatrix} \newline 0 & 3 & 3 & 6 \newline 3 & 10 & 13 & 12 \newline 3 & 13 & 16 & 18 \newline \textcolor{#f05}{6} & 12 & 18 & 9 \end{pmatrix}

Por tanto, hay 6 caminos de longitud 3 entre $v_1$ y $v_4$ .

Conectividad de un grafo

Definición

Se dice que dos vértices

v

w

de un grafo están conectados si

v = w

o si existe un camino entre ambos.

Definición

Un grafo es conexo si todos los vértices están unidos por un camino.

En otro caso, se llama disconexo o no conexo.

Ejemplo de un grafo disconexo:

Definición

Una componente conexa de un grafo es un subgrafo conexo maximal (de tamaño máximo, es decir, que no está contenido en otro subgrafo conexo).

En el ejemplo anterior, se separaría en 2 componentes conexas:

Teorema

Un grafo es conexo

\iff

tiene 1 componente conexa.

Teorema

Sea un grafo $G$ de orden $n$ y $A$ su matriz de adyacencia.

G es conexo $\iff$ las entradas no diagonales ( $i \ne j$ ) de $\displaystyle \sum_{i = 1}^{n - 1} A^i$ son no nulas.

Grafos bipartitos

Definición

Sea $G = (V, E)$ un grafo.

$V = V_1 \cup V_2$ con $V_1$ y $V_2$ disjuntos ( $V_1 \cap V_2 = \empty$ ) de forma que no haya ejes que inciden en dos vértices de $V_1$ ni en dos vértices de $V_2$ , entonces, es un grafo bipartito.

Ejemplo:

Podemos tomar los conjuntos $V_1$ y $V_2$ como

\begin{align*} V_1 &= \Set{A, D} \newline V_2 &= \Set{B, C} \end{align*}

Nótese que $A$ no está conectado con $D$ y que $B$ no está conectado con $C$ .

Definición

Un grafo bipartito se dice completo si todo vértice de $V_1$ está conectado con $V_2$ . Se denotan se la siguiente forma:

K_{|V_1|, |V_2|}

Además se cumple que

$K_{m, n} \approx K_{n, m}$
$|V| = m + n$
$|E| = mn$

Ejemplos:

Teorema

Un grafo es bipartido

\iff

todos los ciclos tienen longitud par.

Ejemplos, el primero no es bipartito, pero sí el segundo.

En amarillo aparecen remarcados los ciclos que no son de longitud par (nótese que solo es necesario encontrar un ciclo).

Se puede obtener la partición, esto es, los dos conjuntos diferenciados de vértices, con el siguiente algoritmo:

Algoritmo

Tomamos un vértice $v$ cualquiera.
$V_1 := \Set{ w \in V | d(v, w) \text{ es impar} }$
$V_2 := \Set{ w \in V | d(v, w) \text{ es par} }$

Donde $d(a, b)$ es la distancia (longitud del camino más corto) entre los nodos $a$ y $b$ .

Grafos Eulerianos

Definición

En un grafo

G = (V, E)

se llama camino Euleriano a un camino simple (no se repiten ejes) que contiene a todos los ejes del grafo.

Un circuito Euleriano es un camino Euleriano que emepieza y termina en el mismo vértice. Todo grafo que tenga al menos un 1 circuito Euleriano se llama grafo Euleriano.
Un grafo se llama Semieuleriano si no tiene un circuito Euleriano pero sí un camino Euleriano.

Teorema

Un grafo conexo es Euleriano $\iff$ todos los vértices tienen grado par: $\forall v \in V, \; \delta(v) \equiv 0 \pmod{2}$

Un grafo conexo es Semieuleriano $\iff$ todos los vértices tienen grado par, excepto dos: los nodos se salida y llegada.

Algunos ejemplos:

Observación

$K_{n,m}$ es Euleriano $\iff$ $n$ y $m$ son pares.

K_n es Euleriano $\iff$ $n \ge 3$ y $n$ es impar.

Algoritmo FLEURY

Definición

Un eje puente es un eje

e = \Set{v, w}

que al eliminarlo, el conjunto de vértices que estén conectados con

v

w

sean disjuntos.

Véase un ejemplo:

Si se elimina el eje puente, el grafo resultante es no conexo:

El algorimo de FLEURY permite encontrar un camino Euleriano.

Algoritmo

Elegimos un vértice cualquiera, en el caso de Semieuleriano, se escoge uno de grado impar.
Se recorre el grafo con las siguientes condiciones:
- Cada eje se elimina una vez que fue recorrido, dado que es un camino simple.
- Solo se seleccionan los ejes puente si no hay otra opción.

Grafos Hamiltonianos

Definición

Un camino Hamiltoniano es un camino simple (no repite ejes) que contiene a todos los vértices. No es necesario que pase por todos los ejes.

Si el camino es cerrado, se llama circuito Hamiltoniano.
Un grafo es Hamiltoniano si tiene un circuito Hamiltoniano (problema NP).
Un grafo es Semihamiltoniano si tiene un camino Hamiltoniano.

Condiciones suficientes

Teorema de DIRAC

Sea $G = (V, E)$ un grafo conexo de orden $n \ge 2$ .

\forall v \in V, \quad \delta(v) \ge \frac{n}{2} \implies \text{G es Hamiltoniano}

Teorema de ORE

Sea $G = (V, E)$ un grafo simple y conexo de orden $n \ge 2$ .

\delta(v) + \delta(w) \ge n \implies \text{G es Hamiltoniano}

Para cualquier par de vértices no adyacentes.

Corolario

K_{n, m} \text{ es Hamiltoniano} \iff m = n \ne 1

\delta(v) = n - 1 \implies K_n \text{ es siempre Hamiltoniano}

Condiciones necesarias

Teorema

G = (V, E)

es un grafo Hamiltoniano, entonces para cada subconjunto

U

de vértices (

U \subset V

) no nulo (

U \ne \empty

), el grafo

G - U

tiene como mucho

|U|

componentes conexas.

En este ejemplo, $|U| = 2$ , pero $G -U$ tiene 3 componentes conexas, por tanto, no es Hamiltoniano.

Grafos planos

Definición

Un grafo es plano si se puede dibujar en el plano de manera que ningún par de ejes se curce, solo en los vértices que inciden.

Como se puede ver en diagrama $K_4$ es plano, pero $K_5$ no.

Teorema de Kuratowski

Sea $G$ un grafo simple y conexo.

$G$ es plano $\iff$ no contiene ningún subgrafo isomorfo por divisiones elementales de $K_5$ o $K_{3, 3}$

Una subdivisión elemental es tomar un eje y añadir un vértice en el medio, sin cambiar nada más (en el ejemplo se añade $C$ en el medio de $A$ y $B$ ):

Fórmula de Euler

Sea $G = (V, E)$ un grafo plano, simple y conexo. Por tanto se cumple que

|C| + |V| = |E| + 2

donde $|C|$ es el número de caras o regiones cerradas del grafo.

Corolario

Sea $G = (V, E)$ un grafo plano, simple y conexo.

$|V| \ge 3 \implies |E| \le 3 |V| - 6$ .
$G$ tiene un vértice de grado $\ge 5$ .
Si $|V| \ge 3$ y no tiene circuitos de longitud 3 $\implies |E| \le 2 |V| 4$ .

Grafos ponderados

Definición

Sea $G = (V, E)$ un grafo.

Se dice que $G$ es un grafo ponderado si existe una aplicación

\begin{align*} w: E &\longrightarrow \R^{+} \cup \Set{0} \newline e &\longmapsto w(e) \end{align*}

$w(e)$ es el peso del eje.

Problema del viajante: encontrar un ciclo hamiltoniano de peso mínimo.
Algoritmo DIJKSTRA: calcular el camino más corto entre dos vértices.

Árboles

Definición

Un árbol es un grafo conexo y sin circuitos.

En este ejemplo, solo el grafo de la derecha es un árbol, porque el de la izquierda tiene un ciclo (marcado en amarillo).

Teorema de DIRAC

Son equivalentes:

$G$ es un árbol
Cada par de vértices está conectado por un único camino simple.
$G$ es conexo y cada eje es un puente.
$G$ es conexo y $|V| = |E| + 1|$ .
$G$ no tiene ciclos y $|V| = |E| + 1|$ .

Árbol generador

Definición

Sea

G

un grafo conexo. Un árbol generador de

G

es un árbol

T

subgrafo de

G

que contiene todos los vértices de

G

Definición

Un árbol generador de peso minimal es un árbol generador cuyo peso es mínimo, el menor entre todos los generadores posibles del grafo.

Algoritmo de Prim (1957)

Algoritmo

Se elige un vértice cualquiera del grafo $G$ : $T_0 = \Set{v}$
Se considera el conjunto de los ejes que inciden en todos los vértices del árbol seleccionado. De todos ellos, se elige el de peso mínimo que no forme un ciclo, siguiendo una estrategia voraz.
Se repite el paso 2 hasta que no se puedan añadir más ejes sin formar ciclos.

Algoritmo de Kruskal (1956)

Algoritmo

Se pone un contador a 1 y se elige el eje de peso mínimo, $e_1$ .
$1 \le i |V| - 2$ , con ejes $e_1, e_2, \ldots e_i$ . Se toma el eje $e_{i + 1} de peso mínimo entre todos los ejes restantes con la condición de que no se formen ciclos.
Repetir el paso 2 hasta que no se puedan añadir más ejes.

Teoría de Grafos

[date: 02-07-2023] [last modification: 08-07-2023]
[words: 3594] [reading time: 17min] [size: 78898 bytes]

Definiciones elementales

El grado de un vértice

Grafos simples

Operaciones con grafos

Subgrafos

Resta de grafos

Isomorfismo de grafos

Representación de grafos

Tabla de adyacencia

Matriz de adyacencia

Matriz de incidencia

Caminos de un grafo

Conectividad de un grafo

Grafos bipartitos

Grafos Eulerianos

Algoritmo FLEURY

Grafos Hamiltonianos

Condiciones suficientes

Condiciones necesarias

Grafos planos

Grafos ponderados

Árboles

Árbol generador

Algoritmo de Prim (1957)

Algoritmo de Kruskal (1956)

Teoría de Grafos

[date: 02-07-2023] [last modification: 08-07-2023][words: 3594] [reading time: 17min] [size: 78898 bytes]

Definiciones elementales

El grado de un vértice

Grafos simples

Operaciones con grafos

Subgrafos

Resta de grafos

Isomorfismo de grafos

Representación de grafos

Tabla de adyacencia

Matriz de adyacencia

Matriz de incidencia

Caminos de un grafo

Conectividad de un grafo

Grafos bipartitos

Grafos Eulerianos

Algoritmo FLEURY

Grafos Hamiltonianos

Condiciones suficientes

Condiciones necesarias

Grafos planos

Grafos ponderados

Árboles

Árbol generador

Algoritmo de Prim (1957)

Algoritmo de Kruskal (1956)

[date: 02-07-2023] [last modification: 08-07-2023]
[words: 3594] [reading time: 17min] [size: 78898 bytes]