Saltar al contenido principal
LibreTexts Español

6.2: Redes

  1. Última actualización
  2. Guardar como PDF
  • 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}}\)

    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.

    Definición: Spanning Subgraph

    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

    Ejemplo\(\PageIndex{1}\): Spanning Subgraph

    Figura\(\PageIndex{1}\): Mapa de Ciudades Conectantes

    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.

    Figura\(\PageIndex{2}\): Subgráfico de expansión 1

    Esta gráfica abarca todas las ciudades (vértices) de la gráfica original, pero no contiene ningún circuito.

    Figura\(\PageIndex{3}\): Subgráfico de expansión 2

    Esta gráfica abarca todas las ciudades (vértices) de la gráfica original, pero no contiene ningún circuito.

    Definición: Árbol

    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.

    Propiedades de los árboles

    1. 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.
    2. 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.
    3. Un árbol con N vértices debe tener N-1 aristas.
    4. Una gráfica conectada con N vértices y N-1 aristas debe ser un árbol.

    Ejemplo\(\PageIndex{2}\): Tree Properties

    Considera la subgráfica de expansión resaltada en verde que se muestra en la Figura\(\PageIndex{2}\).

    1. 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.

    1. 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.

    1. 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.

    1. Propiedad de árbol 4

    Dado que la gráfica está conectada y tiene seis vértices y cinco aristas, debe ser un árbol.

    Ejemplo\(\PageIndex{3}\): More Examples of Trees

    Todas las gráficas que se muestran a continuación son árboles y todas satisfacen las propiedades de los árboles.

    Figura\(\PageIndex{4}\): Más ejemplos de árboles

    Definición: Árbol de expansión mínimo

    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).

    Ejemplo\(\PageIndex{4}\): Minimum Spanning Tree

    Figura\(\PageIndex{5}\): Gráfico ponderado 1

    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.

    Figura\(\PageIndex{6}\): Árbol de expansión mínimo para el gráfico ponderado 1

    Este es el árbol de expansión mínimo para la gráfica con un costo total de 51.

    Algoritmo de Kruskal

    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.

    1. Encuentra el enlace más barato en la gráfica. Si hay más de uno, escoja uno al azar. Marcarlo en rojo.
    2. Encuentra el siguiente enlace más barato en la gráfica. Si hay más de uno, escoja uno al azar. Marcarlo en rojo.
    3. Continuar haciendo esto siempre y cuando el siguiente enlace más barato no cree un circuito rojo.
    4. 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).

    Ejemplo\(\PageIndex{5}\): Using Kruskal’s Algorithm

    Figura\(\PageIndex{7}\): Gráfica ponderada 2

    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.

    Figura\(\PageIndex{8}\): Algoritmo de Kruskal Paso 1

    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.

    Figura\(\PageIndex{9}\): Algoritmo de Kruskal Paso 2

    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.

    Figura\(\PageIndex{10}\): Algoritmo de Kruskal Paso 3

    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.

    Figura\(\PageIndex{11}\): Algoritmo de Kruskal Paso 4

    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.

    Figura\(\PageIndex{12}\): Algoritmo de Kruskal Paso 5

    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.

    This page titled 6.2: Redes is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Maxie Inigo, Jennifer Jameson, Kathryn Kozak, Maya Lanzetta, & Kim Sonier via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.