6.2: Redes
- Page ID
- 109950
\( \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}\)Una red es una conexión de vértices a través de aristas. Internet es un ejemplo de una red con computadoras como vértices y las conexiones entre estas computadoras como bordes.
Un subgrafo de expansión es una gráfica que une todos los vértices de una gráfica más compleja, pero no crea un circuito
Esta es una gráfica que muestra cómo seis ciudades están unidas por carreteras. Esta gráfica tiene muchos subgráficos que abarcan pero a continuación se muestran dos ejemplos.
Esta gráfica abarca todas las ciudades (vértices) de la gráfica original, pero no contiene ningún circuito.
Esta gráfica abarca todas las ciudades (vértices) de la gráfica original, pero no contiene ningún circuito.
Un árbol es una gráfica que está conectada y no tiene circuitos. Por lo tanto, una subgrafía de expansión es un árbol y los ejemplos de subgráficos de expansión en Ejemplo\(\PageIndex{1}\) anterior también son árboles.
- Si una gráfica es un árbol, hay uno y solo un camino que une dos vértices cualesquiera. Por el contrario, si hay uno y solo un camino uniendo dos vértices cualesquiera de una gráfica, la gráfica debe ser un árbol.
- En un árbol, cada borde es un puente. Por el contrario, si cada borde de una gráfica conectada es un puente, entonces la gráfica debe ser un árbol.
- Un árbol con N vértices debe tener N-1 aristas.
- Una gráfica conectada con N vértices y N-1 aristas debe ser un árbol.
Considera la subgráfica de expansión resaltada en verde que se muestra en la Figura\(\PageIndex{2}\).
- Propiedad de árbol 1
Mira los vértices Appleville y Heavytown. Dado que la gráfica es un árbol, sólo hay un camino que une estas dos ciudades. También, dado que solo hay un camino entre dos ciudades cualesquiera en toda la gráfica, entonces la gráfica debe ser un árbol.
- Propiedad de árbol 2
Dado que la gráfica es un árbol, observe que cada borde de la gráfica es un puente, que es un borde tal que si se quitara la gráfica se desconectaría.
- Propiedad de árbol 3
Dado que la gráfica es un árbol y tiene seis vértices, debe tener N — 1 o seis — 1 = cinco aristas.
- Propiedad de árbol 4
Dado que la gráfica está conectada y tiene seis vértices y cinco aristas, debe ser un árbol.
Todas las gráficas que se muestran a continuación son árboles y todas satisfacen las propiedades de los árboles.
Un árbol de expansión mínimo es el árbol que abarca todos los vértices en un problema con el menor costo (o tiempo, o distancia).
Lo anterior es un gráfico ponderado donde los números en cada borde representan el costo de cada borde. Queremos encontrar el árbol de expansión mínimo de esta gráfica para que podamos encontrar una red que llegue a todos los vértices por el menor costo total.
Este es el árbol de expansión mínimo para la gráfica con un costo total de 51.
Dado que algunas gráficas son mucho más complicadas que el ejemplo anterior, podemos usar el Algoritmo de Kruskal para siempre poder encontrar el árbol de expansión mínimo para cualquier gráfica.
- Encuentra el enlace más barato en la gráfica. Si hay más de uno, escoja uno al azar. Marcarlo en rojo.
- Encuentra el siguiente enlace más barato en la gráfica. Si hay más de uno, escoja uno al azar. Marcarlo en rojo.
- Continuar haciendo esto siempre y cuando el siguiente enlace más barato no cree un circuito rojo.
- Se termina cuando los bordes rojos abarcan cada vértice de la gráfica sin ningún circuito. Los bordes rojos son el MST (árbol de expansión mínimo).
Supongamos que se desea instalar una nueva red de cable de fibra óptica entre las seis ciudades (A, B, C, D, E y F) mostradas anteriormente para el menor costo total. Además, supongamos que el cable de fibra óptica solo se puede instalar a lo largo de las carreteras que se muestran arriba. El gráfico ponderado anterior muestra el costo (en millones de dólares) de instalar el cable de fibra óptica a lo largo de cada calzada. Queremos encontrar el árbol de expansión mínimo para esta gráfica usando el Algoritmo de Kruskal.
Paso 1: Encuentra el enlace más barato de toda la gráfica y márcalo en rojo. El vínculo más barato es entre B y C con un costo de cuatro millones de dólares.
Paso 2: Encuentra el siguiente enlace más barato de toda la gráfica y márcalo en rojo. El siguiente enlace más barato es entre A y C con un costo de seis millones de dólares.
Paso 3: Encuentra el siguiente enlace más barato de toda la gráfica y márcalo en rojo siempre y cuando no cree un circuito rojo. El siguiente enlace más barato es entre C y E con un costo de siete millones de dólares.
Paso 4: Encuentra el siguiente enlace más barato de toda la gráfica y márcalo en rojo siempre y cuando no cree un circuito rojo. El siguiente enlace más barato es entre B y D con un costo de ocho millones de dólares.
Paso 5: Encuentra el siguiente enlace más barato de toda la gráfica y márcalo en rojo siempre y cuando no cree un circuito rojo. El siguiente enlace más barato es entre A y B con un costo de nueve millones de dólares, pero eso crearía un circuito rojo por lo que no podemos usarlo. Por lo tanto, el siguiente enlace más barato después de eso es entre E y F con un costo de 12 millones de dólares, que podemos usar. No podemos usar el vínculo entre C y D que también tiene un costo de 12 millones de dólares porque crearía un circuito rojo.
Este fue el último paso y ahora tenemos el árbol de expansión mínimo para la gráfica ponderada con un costo total de $37,000,000.