MOR - Tema 2

Árboles

Bosque. Definición

Sea $G = (V, A)$, se dice bosque si es un grafo no orientado acíclico, es decir, si no contiene ciclos.

Árbol. Definición

Sea $G = (V, A)$, se dice árbol si es un grafo no orientado acíclico y conexo.

Proposición

Sea $G = (V, A)$ un bosque que no es árbol, entonces cada una de sus componentes conexas es un árbol.

Teorema 2.1

Sea $G = (V, A)$ grafo no orientado con $o(G) = n > 1$ y $t(G) = m$, las siguientes expresiones son equivalentes:

1. $G$ es un árbol.
2. Entre cada dos vértices de $G$ existe una única cadena elemental que los une
3. $G$ es conexo y $m = n - 1$
4. $G$ es acíclico y $m = n - 1$

Árbol. Definición equivalente

A partir del teorema 2.1 y la proposición 1.7, podemos definir un árbol de las siguientes maneras equivalentes:

• $G$ conexo y sin ciclos
• Entre cada dos vértices de $G$ existe una única cadena elemental que los une
• $G$ es acíclico y $m = n - 1$
• $G$ es conexo y $m = n - 1$
• $G$ es minimalmente conexo
• $G$ es conexo y todas sus aristas son puentes

Raíz, nudo y hoja. Definición

Sea $G = (V, A)$ un árbol, fijado un vértice $r \in V$ (llamado raíz) se definen:

• Nudo: Cualquier vértice intermedio $v \in V$ entre la raíz y una hoja, es decir:

$$\begin{align*} v \neq r \quad \text{y} \quad g(v) > 1 \end{align*}$$

• Hoja: Cualquier vértice $v \in V$ que cumple:

$$\begin{align*} v \neq r \quad \text{ y } \quad g(v) = 1 \end{align*}$$

A cada arista de $G$ se le llama rama.

Nivel de un vértice. Definición

Sea $G = (V, A)$ árbol y $r \in V$ su raíz, el nivel de un vértice es la longitud de la cadena elemental desde la raíz al vértice, es decir, el número de ramas que hay en dicha cadena.

Altura del árbol. Definición

Sea $G = (V, A)$ árbol y $r \in V$ su raíz, la altura del árbol es el máximo nivel entre todos los vértices de $G$.

Árbol binario. Definición

Sea $G = (V, A)$ un árbol, se dice árbol binario si, sea $r \in V$ su raíz:

$$\begin{align*} g(r) = 2 \quad \text{y} \quad g(v) = 1 \lor 3 \quad \forall v \in V, v \neq r \end{align*}$$

Árbol de unión de valor mínimo

Bosque de unión. Definición

Sea $G = (V, A)$ grafo no orientado, se dice bosque de unión a todo grafo parcial $G' = (V, A')$ de $G$ que es un bosque.

Árbol de unión. Definición

Sea $G = (V, A)$ grafo no orientado, se dice árbol de unión a todo grafo parcial $G' = (V, A')$ de $G$ que es un árbol.

Teorema 2.2

Sea $G = (V, A)$ un grafo no orientado, se cumple que:

$$\begin{align*} G \text{ conexo} \iff G \text{ contiene un árbol de unión}\\ \end{align*}$$

Redes

Red. Definición

Sea $G = (V, A)$ grao orientado (no orientado), se dice red orientada (no orientada) a la terna $R = (V, A, p)$ donde $p : A \to \mathbb{R}$ es una aplicación que a cada arco (arista) $e \in A$ le asigna un peso $p_e \in \mathbb{R}$.

Estos pesos son valores numéricos que indican el valor asociado a cada arco (arista) en la red. Pueden representar costos, distancias, capacidades u otras métricas relevantes según el contexto de la red.

Matriz de distancias de una red orientada. Definición

Sea $R = (V, A, p)$ red orientada de orden $n$, se define la matriz de distancias asociada, denotada como $D_0(G)$ o $D_0$ como la matriz $n \times n$ cuyos elementos vienen dados por:

$$\begin{align*} D_0(i, j) = \left\{ \begin{array}{ll} 0 & \text{ si } i = j\\ p_{ij} & \text{ si } (i, j) \in A\\ \infty & \text{ en otro caso} \end{array} \right. \end{align*}$$

Matriz de distancias de una red no orientada. Definición

Sea $R = (V, A, p)$ red no orientada de orden $n$, se define la matriz de distancias asociada, denotada como $D_0(G)$ o $D_0$ como la matriz $n \times n$ cuyos elementos vienen dados por:

$$\begin{align*} D_0(i, j) = \left\{ \begin{array}{ll} 0 & \text{ si } i = j\\ p_{ij} & \text{ si } (i, j) \in A \text{ o } (j, i) \in A\\ \infty & \text{ en otro caso} \end{array} \right. \end{align*}$$

Red no orientada conexa. Definición

Sea $R = (V, A, p)$ red no orientada, se dice conexa si $G = (V, A)$ es un grafo no orientado conexo.

Red orientada conexa. Definición

Sea $R = (V, A, p)$ red orientada, se dice débilmente conexa (cuasi-fuertemente conexa; fuertemente conexa) si $G = (V, A)$ es un grafo orientado débilmente conexo (cuasi-fuertemente conexo; fuertemente conexo).

Árbol de unión de una red. Definición

Sea $R = (V, A, p)$ red orientada (no orientada), se dice árbol de unión de la red a todo árbol $G'$ de $R$ cuyo grafo asociado es un árbol de unión.

Valor de un árbol de unión

Sea $R = (V, A, p)$ red no orientada conexa y $G' = (V, A')$ un árbol de unión del grafo $(V, A)$ asociado a la red $R$, se dice valor del árbol de unión $G'$ al valor:

$$\begin{align*} p(G') = \displaystyle \sum_{e \in A'} p_e\\ \end{align*}$$

Árbol de unión de valor mínimo

Sea $R = (V, A, p)$ una red no orientada conexa y sea $G'$ un árbol de unión de $R$, se dice árbol de unión de valor mínimo de $R$ si:

$$\begin{align*} p(G') = \min_{T \in AU(R)} p(T) \end{align*}$$

donde $AU(R)$ es el conjunto de todos los árboles de unión en el grafo $(V, A)$ asociados a la red $R = (V, A, p)$.

Teorema 2.3

Sea $R = (V, A, p)$ red no orientada conexa, $G'$ un árbol de unión de valor mínimo en $R$ y $G^{(k)} = (V^{(k)}, A^{(k)})$ con $k = 1, \dots, q$ los $q$ subgrafos conexos de $G'$ tales que $\{V^{(1)}, \dots, V^{(q)}\}$ forman una partición de $V$. Dado $s \in \{1, \dots, q\}$, si $e_s \in A$ es una arista de menor valor entre las aristas con un extremo en $V^{(s)}$ y otro en $V \setminus V^{(s)}$, entonces:

$$\begin{align*} e_s \text{ pertenece a un árbol de unión de valor mínimo de } R\\ \end{align*}$$

Consecuencias del teorema 2.3

Como consecuencias del teorema 2.3, tenemos:

• Una arista de menor peso en un grafo conexo $G$ estará contenida en un árbol de unión de valor mínimo de $G$.

• Si el AUVM es único, entonces es evidente que aplicando sucesivamente el teorema 2.3 se puede reconstruir el AUVM completo.
• Si no es único, se podría probar que la aplicación reiterada de el teorema 2.3 permite construir uno de los AUVM del grafo.
• Basándose en el teorema 2.3, se puedeen obtener distintos algoritmos para hallar un AUVM en una red conexa.

Algoritmo de Prim

El algoritmo de Prim es un método voraz para encontrar un árbol de unión de valor mínimo en una red no orientada $R = (V, A, p)$, donde $G = (V, A)$ es un grafo con $o(G) = n \geq 2$ y $t(G) > 0$:

1. Seleccionamos $v \in V$ cualquiera y definimos $V' = \{v\}$ y $A' = \emptyset$
2. Sea $e' = (x', y') \in A$ con $x' \in V'$ e $y' \notin V'$ tal que:

$$\begin{align*} p_{e'} = \min \left\{p_e : e = (x, y) \text{ con } x \in V', y \notin V' \right\} \end{align*}$$

Hacemos $V' = V' \cup \{y'\}$ y $A' = A' \cup \{e'\}$ y avanzamos a 3. Si no existen ninguna arista, avanzamos a 4. 3. Si $|A'| < n - 1$ ir a 2. Si $|A'| = n - 1$ parar porque $G' = (V', A')$ es un AUVM de $R$. 4. Parar, el grafo no es conexo y por tanto no existe AUVM.

Unicidad del AUVM. Proposición 2.4

Sea $R = (V, A, p)$ una red no orientada conexa. Si todos los pesos asociados a las aristas son distintos, existe un único árbol de unión de valor mínimo en dicha red.

Bosque de unión de valor mínimo

Sea $R = (V, A, p)$ red no conexa, las $k$ componentes conexas de $G$ generan $k$ subgrafos y cada uno de ellos contiene un árbol de unión de valor mínimo. El bosque de unión de valor mínimo de $R$ es el conjunto formado por los $k$ árboles de unión de valor mínimo de cada una de las componentes conexas de $G$.

Árboles y bosque de unión de valor máximo

Sea $R = (V, A, p)$ red n orientada, si se aplican los algoritmos vistos anteriormente considerando los pesos $-p_e$ en lugar de $p_e$, se obtienen árboles y bosques de unión de valor máximo.

Transformaciones monótonas de los pesos

Sea $R = (V, A, p)$ red no orientada conexa, puesto que el AUVM los forman las $n - 1$ aristas de menor peso que no formen ciclos, encontrar el AUVM en $R$ es equivalente a encontrar el AUVM en la red $R' = (V, A, p')$ donde:

$$\begin{align*} p_e' = f(p_e) \quad \forall e \in A \quad \text{ con } f: \mathbb{R} \to \mathbb{R} \text{ función estrictamente creciente}\\ \end{align*}$$

Análogamente, se llega a que el árbol de unión de valor máximo en $R$ es equivalente al árbol de unión de valor máximo en $R' = (V, A, p')$ donde:

$$\begin{align*} p_e' = - f(p_e) \quad \forall e \in A \quad \text{ con } f: \mathbb{R} \to \mathbb{R} \text{ función continua estrictamente creciente}\\ \end{align*}$$

Arborescencias

La idea de arborescencia es similar a la de árbol, pero en este caso se trabaja con grafos orientados.

$$\begin{array}{c|l} \textbf{No orientados} & \textbf{Orientados}\\ \hline \hline & Raíz de entrada/salida\\[2ex] Árbol & Arborescencia de entrada/salida\\[2ex] Árbol de unión & Arborescencia de unión de entrada/salida\\[2ex] Grafo conexo & Grafo cuasi-fuertemente conexo en sentido ascendiente/descendente\\[2ex] AUVM & Arborescencia de unión de entrada/salida de valor mínimo \end{array}$$

Raíz de un grafo orientado. Definición

Sea $G = (V, A)$ grafo orientado, se dice que $r \in V$ es raíz de salida de $G$ si todo vértice es alcanzable desde $r$, es decir, si para todo $v \in V$ existe $\pi_{rv}$ o, en otras palabras:

$$\begin{align*} Ds(r) = V\\ \end{align*}$$

Análogamente, se dice que $r \in V$ es raíz de entrada de $G$ si todo vértice alcanza a $r$, es decir, si para todo $v \in V$ existe $\pi_{vr}$ o, en otras palabras:

$$\begin{align*} As(r) = V\\ \end{align*}$$

Teorema 2.5

Sea $G = (V, A)$ grafo orientado:

$$\begin{align*} G \text{ tiene raíz de entrada/salida} \iff G \text{ cuasi-fuertemente conexo}\\ \end{align*}$$

Arborescencia de salida/entrada.

Idea

La idea de la arborescencia de salida es que tiene que ser la forma minimal de ir de un vértice a todos los demás, por lo que $G$ debe tener un vértice del que se pueda ir a todos los demás, es decir, una raíz de salida.

Por otra parte, la forma de ir debería de ser única y no resulta suficiente exigir que $G$ no tenga circuitos, hay que exigir que $G^s$ no tenga ciclos.

Aún así, no es suficiente y hay que exigir que $G$ no tenga arcos de doble sentido, es decir:

$$\begin{align*} \nexists i, j \in V : (i,j), (j,i) \in A \iff G \text{ no tiene circuitos}\\ \end{align*}$$

Redundancia de las condiciones

Podemos plantearnos si alguna de las condiciones previas es redundante, es decir, si alguna de ellas se puede deducir de las otras. La condición candidata podría ser:

$$\begin{align*} G^s \text{ acíclico} \iff G \text{ no tiene circuitos} \end{align*}$$

Sin embargo, esto no es cierto en general, existen grafos cuyo grafo subyacente es acíclico pero que contienen circuitos. También pueden existir grafos sin circuitos cuyo grafo subyacente no es acíclico.

Por tanto, ninguna de las condiciones es redundante y todas son necesarias para definir una arborescencia de salida/entrada.

Arborescencia de salida. Definición formal

Sea $G = (V, A)$ grafo orientado, se dice que es arborescencia de salida si:

• $G$ tiene una raíz de salida o equivalentemente, $G$ es cuasi-fuertemente conexo en sentido descendiente.
• $G^s$ es acíclico.
• $G$ no tiene circuitos.

Además, son equivalentes las siguientes condiciones:

• $G$ no contiene circuitos entonces $\nexists i, j \in V : (i,j), (j,i) \in A$
• Si $G^s$ es acíclico, es suficiente saber que no existen arcos de doble sentido para asegurar que $G$ no tiene circuitos. Esto se debe a que si el circuito tiene al menos 3 arcos, $G^s$ contendrá un ciclo y si tiene 2 arcos, tiene que ser de doble sentido. Por tanto:

$$\begin{align*} \nexists i,j \in V : (i,j), (j,i) \in A \implies G \text{ no tiene circuitos} \end{align*}$$

Por lo que se puede definir alternativamente la arborescencia de salida mediante las condiciones:

• G tiene una raíz de salida o equivalentemente, $G$ es cuasi-fuertemente conexo en sentido descendiente.
• $G^s$ es acíclico.
• $\nexists i,j \in V : (i,j), (j,i) \in A$

Arborescencia de entrada. Definición formal

Análogamente, sea $G = (V, A)$ grafo orientado, se dice que es arborescencia de entrada si:

• $G$ es cuasi-fuertemente conexo en sentido ascendiente o equivalentemente, $G$ tiene una raíz de entrada.
• $G^s$ es acíclico.
• $G$ no tiene circuitos o equivalentemente, no tiene arcos de doble sentido.

Arborescencia de salida/entrada binaria

Se dice que una arborescencia de salida/entrada es binaria a aquella en la que cada vértice tiene grado de salida/entrada igual a 0 o 2

Teorema 2.6

Sea $G = (V, A)$ grafo orientado con $o(G) = n > 1$ entonces son equivalentes:

1. $G$ es una arborescencia de salida con raíz de salida $r$.
2. Existe $r \in V$ de $G$ tal que $\exists ! \pi_{rv}$ con $v \in V, v \neq r$.
3. $G$ es minimalmente cuasi-fuertemente conexo en sentido descendiente con raíz de salida $r$

Arborescencia de unión. Definición

Sea $G = (V, A)$ grafo orientado, se dice arborescencia de unión (de entrada/salida) a una arborescencia $G' = (V, A')$ (de entrada/salida) donde $A'\subseteq A$.

Teorema 2.7

Sea $G = (V, A)$ grafo orientado entonces:

$$\begin{align*} G \text{ cuasi-fuertemente conexo} \iff G \text{ contiene arborescencia de unión} \end{align*}$$

Arborescencia de unión de valor mínimo

Idea

Partimos de una red orientada $R = (V, A, p)$ cuasi-fuertemente conexa (ascendiente/descendente) y queremos encontrar una red orientada $R' = (V, A', p)$ tal que $G' = (V, A')$ sea una arborescencia de unión (de entrada/salida) del grafo $G = (V, A)$ que minimice el valor:

$$\begin{align*} \displaystyle \sum_{e \in A'} p_e\\ \end{align*}$$

AUVM fijada la raíz de salida

Sea $R = (V, A, p)$ red orientada cuasi-fuertemente conexa en sentido descendiente y sea $r \in V$ la raíz de salida de una arborescencia de unión de $R$. Se dice arborescencia de unión de valor mínimo con raíz de salida $r$ a toda arborescencia de unión $G' = (V, A')$ de $R$ que minimice:

$$\begin{align*} \displaystyle \sum_{e \in A'} p_e\\ \end{align*}$$

Análogamente se puede definir la arborescencia de unión de valor mínimo con raíz de entrada $r$.

Algoritmo de Edmonds

Este algoritmo se escapa del alcance de este curso. No obstante, si se da el caso particular en el que todos los arcos son en ambos sentidos y el peso es el mismo en todas las direcciones, se podría resolver este problema empleado los algoritmos para grafos no orientados, sin más que adaptar la solución de forma adecuada.

Existencia del AUVM

No siempre el árbol de unión de valor mínimo genera una arborescencia de unión.