10.2: Árboles de expansión

Última actualización
Guardar como PDF

Page ID: 117146

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Motivación

El tema de los árboles de expansión está motivado por un problema de optimización gráfica.

Una gráfica de la Universidad Atlantis (Figura$\PageIndex{1}$) muestra que hay cuatro campus en el sistema. Se está instalando un nuevo sistema de comunicaciones seguras y el objetivo es permitir la comunicación entre dos campus cualquiera; para lograr este objetivo, la universidad debe comprar líneas directas entre ciertos pares de campus. Dejar$G$ ser la gráfica con un vértice para cada campus y un borde para cada línea directa. La comunicación total equivale a$G$ ser una gráfica conectada. Esto se debe a que dos campus pueden comunicarse a través de cualquier número de líneas. Para minimizar costos, la universidad quiere comprar un número mínimo de líneas.

$clipboard_e8f2ad5b97030e51220f44b764735a735.png$ Figura$\PageIndex{1}$: Gráfica de Atlantis University

Las soluciones a este problema son todos árboles. Cualquier gráfica que satisfaga los requisitos de la universidad debe estar conectada, y si existe un ciclo, se puede eliminar cualquier línea del ciclo, reduciendo el costo. Cada uno de los dieciséis árboles que se pueden dibujar para conectar los vértices Norte, Sur, Este y Oeste (ver Ejercicio 10.1.1) resuelve el problema tal como se afirma. Tenga en cuenta que en cada caso, se deben adquirir tres líneas directas. Hay dos consideraciones que pueden ayudar a reducir el número de soluciones que se considerarían.

Objetivo 1: Dado que el costo de cada línea depende de ciertos factores, como la distancia entre los campus, seleccionar un árbol cuyo costo sea lo más bajo posible.
Objetivo 2: Supongamos que la comunicación a través de múltiples líneas es más ruidosa a medida que aumenta el número de líneas. Seleccione un árbol con la propiedad que el número máximo de líneas que cualquier par de campus debe usar para comunicarse sea lo más pequeño posible.

Por lo general, estos objetivos no son compatibles; es decir, no siempre se pueden lograr simultáneamente estos objetivos. En el caso del sistema universitario Atlantis, la solución con respecto al Objetivo 1 se indica con líneas continuas en la Figura$\PageIndex{1}$. Hay cuatro soluciones al problema con respecto al Objetivo 2: cualquier árbol en el que un campus esté conectado directamente con los otros tres. Una solución con respecto al Objetivo 2 se indica con líneas punteadas en la Figura$\PageIndex{1}$. Después de satisfacer las condiciones del Objetivo 2, parecería razonable seleccionar el más barato de los cuatro árboles.

Definición

Definición$\PageIndex{1}$: Spanning Tree

Dejar$G = (V, E)$ ser una gráfica no dirigida conectada. Un árbol de expansión para$G$ es un subgrafo de expansión, Definición 9.1.5, de$G$ eso es un árbol.

Nota$\PageIndex{1}$

Si$(V, E')$ es un árbol de expansión,$\lvert E' \rvert =\lvert V \rvert - 1\text{.}$
La importancia de un árbol de expansión es que es un conjunto de expansión mínimo. Un conjunto menor no abarcaría la gráfica, mientras que un conjunto más grande tendría un ciclo, que tiene una arista que es superflua.

Para lo que resta de esta sección, discutiremos dos de los muchos temas que se relacionan con los árboles que abarcan. El primero es el problema de encontrar árboles de expansión mínimos, que aborda el Objetivo 1 anterior. El segundo es el problema de encontrar árboles que abarcan el Diámetro Mínimo, que aborda el Objetivo 2.

Definición$\PageIndex{2}$: Minimal Spanning Tree

Dado un gráfico no dirigido conectado ponderado,$G = (V, E, w)\text{,}$ un árbol de expansión mínimo es un árbol de expansión$(V, E')$ para el cual$\sum_{e\in E'} w(e)$ es lo más pequeño posible.

Algoritmo de Prim

A diferencia de muchos de los problemas de optimización gráfica que hemos examinado, se puede obtener una solución a este problema de manera eficiente. Es una situación en la que funciona un algoritmo codicioso.

Definición$\PageIndex{3}$: Bridge

Dejar$G = (V, E)$ ser una gráfica no dirigida y dejar$\{L, R\}$ ser una partición de$V\text{.}$ Un puente entre$L$ y$R$ es un borde en$E$ que conecta un vértice$L$ a un vértice en$R\text{.}$

Teorema$\PageIndex{1}$

Let$G = (V, E, w)$ Ser una gráfica no dirigida conectada ponderada. Dejar$V$ ser particionado en dos conjuntos$L$ y$R\text{.}$ Si$e^*$ es un puente de menor peso entre$L$ y$R\text{,}$ entonces existe un árbol de expansión mínimo para$G$ eso incluye$e^*\text{.}$

Prueba: ASupone que no$e^*$ existe ningún árbol de expansión mínimo incluyendo. Deja$T = (V, E')$ ser un árbol de expansión mínimo. Si agregamos$e^*$ a$T\text{,}$ un ciclo se crea, y este ciclo debe contener otro puente,$e\text{,}$ entre$L$ y$R\text{.}$ Desde$w\left(e^*\right) \leq w(e)\text{,}$ podemos eliminar$e$ y el nuevo árbol, que incluye también$e^*$ debe ser un árbol de expansión mínimo.

Ejemplo$\PageIndex{1}$: Some Bridges

Los puentes entre los conjuntos de vértices$\{a, b, c\}$ y$\{d, e\}$ en Figura$\PageIndex{2}$ son los bordes$\{b, d\}$ y$\{c, e\}\text{.}$ Según el teorema anterior,$\{b, d\}$ existe un árbol de expansión mínimo que incluye. Por examen, deberías poder ver que esto es cierto. ¿Es cierto que solo los puentes de peso mínimo pueden formar parte de un árbol de expansión mínima?

$clipboard_e600bf60ec503fae50fc89e33f13c178d.png$ Figura$\PageIndex{2}$: Puentes entre dos conjuntos

El teorema$\PageIndex{1}$ esencialmente nos dice que un árbol de expansión mínimo se puede construir recursivamente agregando continuamente puentes mínimamente ponderados a un conjunto de bordes.

Algorithm$\PageIndex{1}$: Prim's Algorithm

Dejar$G = (V, E, w)$ ser un gráfico conectado, ponderado, no dirigido, y dejar$v_0$ ser un vértice arbitrario en$V\text{.}$ Los siguientes pasos conducen a un árbol de expansión mínimo para$G\text{.}$$L$ y$R$ serán conjuntos de vértices y$E'$ es un conjunto de bordes.

(Inicializar)$L = V - \left\{v_0\right\}\text{;}$$R = \left\{v_0\right\}\text{;}$$E' = \emptyset\text{.}$
(Construye el árbol) Mientras$L\neq \emptyset\text{:}$
1. Encuentra$e^* = \left\{v_L,v_R\right\}\text{,}$ un puente de peso mínimo entre$L$ y$R\text{.}$
2. $R = R \cup \left\{v_L \right\}\text{;}$$L = L - \left\{v_L\right\}$;$E' =E'\cup \left\{e^*\right\}$
Terminar con un árbol de expansión mínimo$(V, E')\text{.}$

Nota$\PageIndex{2}$

Si existe más de un árbol de expansión mínimo, entonces el que se obtiene depende$v_0$ y de los medios por los cuales$e^*$ se selecciona en el Paso 2.
Advertencia: Si existen dos puentes mínimamente ponderados entre$L$ y$R\text{,}$ no intente acelerar el algoritmo sumando ambos a$E$ '.
Ese algoritmo$\PageIndex{1}$ produce un árbol de expansión mínimo que puede ser probado por inducción con el uso del Teorema$\PageIndex{1}$.
Si no se sabe si$G$ está conectado, el Algoritmo$\PageIndex{1}$ puede ser revisado para manejar esta posibilidad. El cambio de clave (en el Paso 2.1) sería determinar si existe algún puente entre$L$ y$R\text{.}$ La condición del bucle while en el Paso 2 también debe cambiarse algo.

Ejemplo$\PageIndex{2}$: A Small Example

Considera la gráfica en la Figura$\PageIndex{3}$. Si aplicamos Algoritmo de Prim$\PageIndex{1}$, Algoritmo, a partir de$a\text{,}$ obtenemos la siguiente lista de bordes en el orden dado:$\{a, f\}, \{f, e\}, \{e, c\}, \{c, d\}, \{f, b\}, \{b, g\}\text{.}$ El total de los pesos de estos bordes es 20. El método que hemos utilizado (en el Paso 2.1) para seleccionar un puente cuando existe más de un puente mínimamente ponderado es ordenar todos los puentes alfabéticamente por el vértice en$L$ y luego, si existen más lazos, por el vértice en$R\text{.}$ El primer vértice en ese orden se selecciona en el Paso 2.1 de la algoritmo.

$clipboard_e30a3d5155df109eff6d336fc57d50780.png$ Figura$\PageIndex{3}$: Un pequeño gráfico ponderado

Definición$\PageIndex{4}$: Minimum Diameter Spanning Tree

Dada una gráfica no dirigida conectada,$G = (V, E)\text{,}$ encuentra un árbol$T = (V, E')$ de expansión de$G$ tal manera que el camino más largo en$T$ es lo más corto posible.

Ejemplo$\PageIndex{3}$: The Case for Complete Graphs

El problema del árbol de expansión de diámetro mínimo es trivial de resolver en un$K_n\text{.}$ Seleccionar cualquier vértice$v_0$ y construir el árbol de expansión cuyo conjunto de bordes es el conjunto de aristas que se conectan$v_0$ a los otros vértices en el$K_n$. La figura$\PageIndex{4}$ ilustra una solución para$n=5\text{.}$

$clipboard_e0a54a570ef03a1304d91766e99449420.png$ Figura$\PageIndex{4}$: Árbol de expansión de diámetro mínimo para$K_{5}$

Para gráficas incompletas, se necesita un algoritmo de dos etapas. En definitiva, el primer paso es ubicar un “centro” de la gráfica. La distancia máxima de un centro a cualquier otro vértice es lo más pequeña posible. Una vez que se localiza un centro, se utiliza una búsqueda de la gráfica en primer lugar en la amplitud para construir el árbol de expansión.

Ejercicios

Ejercicio$\PageIndex{1}$

Supongamos que después de que el sistema telefónico de la Universidad Atlantis esté en su lugar, se establezca un quinto campus y que se pueda comprar una línea de transmisión para conectar el nuevo campus con cualquier campus antiguo. ¿Es este sistema más grande el más económico posible con respecto al Objetivo 1? ¿Siempre puedes satisfacer el Objetivo 2?

Responder: Podría no ser lo más económico con respecto al Objetivo 1. Deberías poder encontrar un ejemplo para ilustrar esta afirmación. El nuevo sistema siempre se puede hacer más económico con respecto al Objetivo 2 si el sistema antiguo se diseñó con ese objetivo en mente.

Ejercicio$\PageIndex{2}$

Construir un árbol de expansión mínimo para las capitales de Nueva Inglaterra (ver Tabla 9.5.1).

Ejercicio$\PageIndex{3}$

Demostrar que la respuesta a la pregunta planteada en Ejemplo$\PageIndex{1}$ es “no”.

Responder: En la siguiente figura, no$\{1,2\}$ es un puente mínimo entre$L=\{1,4\} \textrm{ and } R=\{2,3\}\text{,}$ sí sino que forma parte del árbol de expansión mínimo para esta gráfica.

$clipboard_ec4bf32632c0075d7db4878fdc8db486f.png$ Figura$\PageIndex{5}$

Ejercicio$\PageIndex{4}$

Encuentre un árbol de expansión mínimo para las siguientes gráficas.

$clipboard_ef5e9e58863428c7318402f15db9c4144.png$ Figura$\PageIndex{6}$

$clipboard_ee8b56ba0ebeb30bf53e7dec33bce6a40.png$ Figura$\PageIndex{7}$

$clipboard_e8011afa500e471f1507b598254f71359.png$ Figura$\PageIndex{8}$

Ejercicio$\PageIndex{5}$

Encuentre un árbol de expansión de diámetro mínimo para las siguientes gráficas.

$clipboard_eeb3e5d84bc277c9f4b95139255df28ec.png$ Figura$\PageIndex{9}$

$clipboard_ed47c65da6c916b853419e338db4a1e78.png$ Figura$\PageIndex{10}$

Responder

Los bordes en una solución son:$\{8,7\},\{8,9\},\{8,13\},\{7,6\},\{9,4\},\{13,12\},\{13,14\},\{6,11\},\{6,1\},\{1,2\},\{4,3\},\{4,5\},\{14,15\}, \textrm{ and } \{5,10\}$
Los vértices 8 y 9 son centros de la gráfica. A partir del vértice 8, un árbol de expansión de diámetro mínimo es$\{\{8, 3\}, \{8, 7\}, \{8, 13\}, \{8, 14\}, \{8, 9\}, \{3, 2\}, \{3, 4\}, \{7, 6\}, \{13, 12\}, \{13, 19\}, \{14, 15\}, \{9, 16\}, \{9, 10\}, \{6, 1\}, \{12, 18\}, \{16, 20\}, \{16, 17\}, \{10, 11\}, \{20, 21\}, \{11, 5\}\}.$ El diámetro del árbol es 7.

Ejercicio$\PageIndex{6}$

En cada una de las siguientes partes justifica tu respuesta ya sea con una prueba o un contraejemplo.

Supongamos que una gráfica ponderada no dirigida tenía pesos de borde distintos. ¿Es posible que ningún árbol de expansión mínimo incluya el borde del peso mínimo?
Supongamos que una gráfica ponderada no dirigida tenía pesos de borde distintos. ¿Es posible que cada árbol de expansión mínimo incluya el borde del peso máximo? Si es cierto, ¿bajo qué condiciones sucedería?

Search

Text Color

Text Size

Margin Size

Font Type

Ejercicios