Grafos y algoritmos (opcional)

J3.9 · Nivel J3 · Computación científica

Mucho de lo que se hace en monitorización estructural tiene forma de red: los sensores inalámbricos que se pasan los datos hasta una pasarela, las barras de un reticulado que se unen en nudos, los grados de libertad de una matriz de rigidez que solo se acoplan con sus vecinos. Un grafo (un conjunto de nodos y de enlaces entre ellos) es la abstracción común, y con él se contestan preguntas que sin él cuestan mucho: ¿por dónde llega el dato con menos saltos o con menos energía?, ¿qué nodo, si falla, deja la red partida en dos?, ¿en cuántas piezas se parte una estructura cuando una barra se rompe? Esta unidad opcional enseña lo básico de Graphs.jl con esos ejemplos.

NotaCómo se lee esta unidad

Tiempo orientativo: 60 minutos. Objetivos (3), teoría en cinco píldoras (15), práctica guiada (22), «Pídeselo a Claude» (8), ejercicios (10) y cierre (2). Unidad opcional del perfil uco; la red de sensores se usa en M9. Los datos son sintéticos: la posición de los 16 nodos de un puente se genera en la página con semilla fija. Se usan Graphs.jl y las funciones de Resonancia.jl (red_sensores, reticulado_plano, adyacencia_barras, grafo_de_matriz, laplaciana).

Objetivos y prerrequisitos

Objetivos. Al terminar esta unidad sabrás:

• construir un grafo en Graphs.jl (a mano, desde una matriz de adyacencia) y leer sus grados y vecinos;
• recorrerlo en anchura y en profundidad, y obtener el camino mínimo en saltos o con pesos (Dijkstra);
• analizar la conectividad de una red de sensores y de una estructura reticulada: nodos críticos, alcance mínimo y subestructuras.

Prerrequisitos. El curso no los impone en el temario; conviene J1.5 (arrays) y J3.3 (matrices dispersas y valores propios).

Reparto con otras unidades. El diseño y la planificación de redes de sensores se tratan en M9; aquí se aprende la herramienta.

Teoría breve

NotaUn poco de historia: la nota de Dijkstra de 1959

El algoritmo de caminos mínimos que lleva su nombre salió en una nota de tres páginas: Edsger W. Dijkstra, «A note on two problems in connexion with graphs», Numerische Mathematik 1, 1959, pp. 269–271 (DOI 10.1007/BF01386390). Como dice su título, trata dos problemas: construir el árbol de longitud total mínima que une todos los nodos, y hallar el camino de longitud mínima entre dos nodos. Con ese primer problema se calcula en J3.9.4 el alcance mínimo de una red.

Fuente: la ficha del artículo en Springer y su resumen, accesible en el DOI enlazado. Solo se ha comprobado la referencia bibliográfica y el planteamiento de los dos problemas, no el texto completo. Consultado el 27-10-2026.

J3.9.1 Grafos y su representación

Un grafo \(G=(V,E)\) es un conjunto de vértices (nodos) \(V\) y de aristas (enlaces) \(E\) que unen pares de vértices. Es no dirigido si el enlace \(i\)–\(j\) vale en los dos sentidos, y ponderado si cada arista lleva un número (una distancia, un coste, una rigidez). Se guarda de dos maneras: como lista de vecinos de cada nodo (compacta cuando hay pocas aristas) o como matriz de adyacencia \(\mathbf A\), con \(A_{ij}\neq0\) si hay arista entre \(i\) y \(j\) (simétrica si no es dirigido). Es la misma idea que la matriz dispersa de J3.3, y Graphs.jl pasa de una a otra sin esfuerzo:

g0 = SimpleGraph(5)                                     # 5 vértices sin aristas
for (u, v) in [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)]
    add_edge!(g0, u, v)
end
(vertices = nv(g0), aristas = ne(g0), grados = degree(g0), vecinos_del_4 = neighbors(g0, 4),
 simetrica = issymmetric(adjacency_matrix(g0)), suma_de_la_fila_2 = sum(adjacency_matrix(g0)[2, :]))

(vertices = 5, aristas = 6, grados = [2, 3, 3, 3, 1], vecinos_del_4 = [2, 3, 5], simetrica = true, suma_de_la_fila_2 = 3)

La suma de una fila de \(\mathbf A\) es el grado del nodo (cuántos enlaces tiene), y la suma de todos los grados es \(2|E|\) (cada arista se cuenta dos veces).

El ejemplo de la unidad es una red inalámbrica de 16 sensores en un puente de 70 m: dos filas de 8 nodos separadas 6 m, con una variación aleatoria de la posición (semilla fija). Dos nodos pueden comunicarse si están a menos del alcance \(r\) de la radio (Figura 1). red_sensores de Resonancia.jl devuelve la matriz de adyacencia ponderada (con las distancias) y SimpleGraph(W) la convierte en grafo:

Figura 1: De la red física al grafo: dos nodos están unidos si su distancia es menor que el alcance \(r\) de la radio, y el peso de la arista es esa distancia.

rng = MersenneTwister(9)
pos = reduce(vcat, [[10.0 * i + 3 * (rand(rng) - 0.5) y + 2 * (rand(rng) - 0.5)] for i in 0:7 for y in (0.0, 6.0)])   # 16 × 2, en m
W = red_sensores(pos; alcance=12.0)
g = SimpleGraph(W)                                      # aristas donde W ≠ 0
(nodos = nv(g), enlaces = ne(g), grados = degree(g), grado_medio = round(mean(degree(g)), digits=2))

(nodos = 16, enlaces = 28, grados = [2, 2, 4, 4, 5, 4, 3, 5, 5, 4, 3, 4, 3, 3, 2, 3], grado_medio = 3.5)

La red de 16 sensores tiene 28 enlaces. ¿Cuánto vale la suma de los grados de todos los nodos?

\(2|E|=2\cdot28=56\): cada enlace suma un grado a cada uno de sus dos extremos (con sum(degree(g))).

J3.9.2 Recorridos: anchura y profundidad

Un recorrido visita todos los nodos alcanzables desde uno inicial. En anchura (BFS, breadth-first search) se visitan primero los vecinos, luego los vecinos de los vecinos, y así por capas; da, para cada nodo, el número mínimo de saltos desde el origen. En profundidad (DFS) se avanza por una rama hasta agotarla y se retrocede; es la base de la detección de ciclos y de componentes. Ambos cuestan \(\mathcal O(|V|+|E|)\). Con el nodo 1 como pasarela (el nodo base que envía los datos al exterior):

saltos = gdistances(g, 1)                               # BFS: saltos mínimos desde el nodo 1
bfs, dfs = bfs_tree(g, 1), dfs_tree(g, 1)
(saltos = saltos, nodos_por_nivel = [count(==(k), saltos) for k in 0:maximum(saltos)],
 profundidad_BFS = maximum(gdistances(bfs, 1)), profundidad_DFS = maximum(gdistances(dfs, 1)))

(saltos = [0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 7, 6, 8, 7], nodos_por_nivel = [1, 2, 3, 2, 2, 2, 1, 2, 1], profundidad_BFS = 8, profundidad_DFS = 15)

Los 15 nodos restantes están a entre 1 y 8 saltos de la pasarela (la excentricidad del nodo 1 es 8). El árbol BFS tiene profundidad 8, la mínima posible; el DFS llega a profundidad 15 (recorre la red como un pasillo largo): para saltos mínimos se usa BFS, y el DFS se reserva para analizar la estructura (componentes, puentes, ciclos).

let
    arist = [(src(e), dst(e)) for e in edges(g)]
    seg(lista) = [Point2f(pos[i, 1], pos[i, 2]) => Point2f(pos[j, 1], pos[j, 2]) for (i, j) in lista]
    fig = Figure(size=(720, 330))
    ax1 = Axis(fig[1, 1], title="(a) saltos a la pasarela", ylabel="y (m)", aspect=DataAspect())
    ylims!(ax1, -3, 10)
    linesegments!(ax1, seg(arist), color=GRIS, linewidth=1)
    sc = scatter!(ax1, pos[:, 1], pos[:, 2], color=saltos, colormap=:viridis, markersize=14)
    scatter!(ax1, pos[[1], 1], pos[[1], 2], color=:white, strokecolor=TINTA, strokewidth=2, marker=:rect, markersize=10)
    scatter!(ax1, pos[[12, 14], 1], pos[[12, 14], 2], color=:transparent, strokecolor=NARANJA, strokewidth=3, markersize=22)
    Colorbar(fig[1, 2], sc, label="saltos")
    h, vmap = induced_subgraph(g, setdiff(1:nv(g), 12))
    comp = connected_components(h)
    grupo = zeros(Int, nv(g)); for (k, c) in enumerate(comp), v in c; grupo[vmap[v]] = k; end
    ax2 = Axis(fig[2, 1], title="(b) sin el nodo 12", xlabel="x (m)", ylabel="y (m)", aspect=DataAspect())
    ylims!(ax2, -3, 10)
    linesegments!(ax2, seg([(i, j) for (i, j) in arist if i != 12 && j != 12]), color=GRIS, linewidth=1)
    scatter!(ax2, pos[grupo .> 0, 1], pos[grupo .> 0, 2], color=[c == argmax(length.(comp)) ? AZUL : NARANJA for c in grupo[grupo .> 0]], markersize=14)
    scatter!(ax2, pos[[12], 1], pos[[12], 2], color=:white, strokecolor=GRIS, strokewidth=1.5, markersize=14)
    fig
end

Figura 2: Red de 16 sensores con alcance de 12 m. (a) Color: número de saltos hasta la pasarela (nodo 1, cuadrado); los aros naranjas marcan los nodos 12 y 14, que son puntos de articulación. (b) La red al retirar el nodo 12: queda partida en una parte de 11 nodos y otra de 4, y el nodo 1 pierde el contacto con las dos últimas columnas de sensores.

¿Cuántos saltos hay desde la pasarela (nodo 1) hasta el nodo más lejano de la red?

maximum(gdistances(g, 1)), o eccentricity(g, 1).

8 saltos (hasta el nodo 15, en el extremo del puente). Es el número de retransmisiones de la peor ruta, y fija la latencia mínima de la red.

J3.9.3 Caminos mínimos: Dijkstra

Cuando las aristas tienen peso (una distancia, un tiempo, una energía), el camino con menos saltos no tiene por qué ser el de menor peso total. El algoritmo de Dijkstra da el camino de peso mínimo desde un origen a todos los demás, siempre que ningún peso sea negativo. En Graphs.jl se le pasa el grafo, el origen y la matriz de pesos: dijkstra_shortest_paths(g, origen, W), y enumerate_paths reconstruye la ruta.

En una red inalámbrica cuesta más energía transmitir más lejos: la energía de un enlace crece como \(d^{2}\) (modelo sencillo). Si los nodos pueden transmitir más lejos (alcance de 20 m) hay muchos más enlaces, y las tres ideas de «mejor ruta» dejan de coincidir. Se comparan las rutas de la pasarela al nodo 16:

W20 = red_sensores(pos; alcance=20.0)
g20 = SimpleGraph(W20)
rutas = Dict("mínimo de saltos" => dijkstra_shortest_paths(g20, 1),                      # todos los pesos valen 1
             "mínima distancia" => dijkstra_shortest_paths(g20, 1, W20),
             "mínima energía" => dijkstra_shortest_paths(g20, 1, W20 .^ 2))
longitud(r) = sum(W20[r[k], r[k+1]] for k in 1:length(r)-1)
energia(r) = sum(W20[r[k], r[k+1]]^2 for k in 1:length(r)-1)
filas = String[]
for criterio in ["mínimo de saltos", "mínima distancia", "mínima energía"]
    r = enumerate_paths(rutas[criterio], 16)
    push!(filas, "| $criterio | $(length(r) - 1) | $(coma(longitud(r), d=1)) | $(coma(energia(r), d=0)) | $(join(r, "–")) |")
end
println("| criterio | saltos | longitud (m) | energía (m²) | ruta |\n|---|---|---|---|---|\n" * join(filas, "\n"))

Tabla 1: Rutas de la pasarela (nodo 1) al nodo 16 con alcance de 20 m según el criterio. La energía es la suma de \(d^2\) de los enlaces.

criterio	saltos	longitud (m)	energía (m²)	ruta
mínimo de saltos	5	74,3	1195	1–4–8–11–14–16
mínima distancia	5	71,8	1134	1–4–8–10–14–16
mínima energía	8	75,8	747	1–3–5–7–9–11–12–14–16

La ruta de mínima energía usa 8 saltos cortos y gasta 747 m² frente a los 1 195 m² de la de mínimos saltos (5 saltos largos): un 37 % menos de energía a cambio de 3 retransmisiones más (más latencia). Qué criterio conviene depende del problema: batería o retardo.

let
    seg(lista) = [Point2f(pos[i, 1], pos[i, 2]) => Point2f(pos[j, 1], pos[j, 2]) for (i, j) in lista]
    tramos(r) = [(r[k], r[k+1]) for k in 1:length(r)-1]
    fig = Figure(size=(720, 250))
    ax = Axis(fig[1, 1], xlabel="x (m)", ylabel="y (m)", aspect=DataAspect())
    ylims!(ax, -3, 10)
    linesegments!(ax, seg([(src(e), dst(e)) for e in edges(g20)]), color=(GRIS, 0.35), linewidth=0.8)
    linesegments!(ax, seg(tramos(enumerate_paths(rutas["mínimo de saltos"], 16))), color=AZUL, linewidth=3, label="mínimo de saltos")
    linesegments!(ax, seg(tramos(enumerate_paths(rutas["mínima energía"], 16))), color=NARANJA, linewidth=3, linestyle=:dash, label="mínima energía")
    scatter!(ax, pos[:, 1], pos[:, 2], color=:white, strokecolor=TINTA, strokewidth=1.5, markersize=11)
    scatter!(ax, pos[[1], 1], pos[[1], 2], color=VERDE, marker=:rect, markersize=13)
    Legend(fig[2, 1], ax, orientation=:horizontal, framevisible=false)
    fig
end

Figura 3: Rutas de la pasarela (cuadrado) al nodo 16 en la red con alcance de 20 m: la de mínimo número de saltos (azul, 5 saltos largos) y la de mínima energía (naranja, 8 saltos cortos). Los enlaces grises son todos los posibles.

Según Tabla 1, ¿qué porcentaje de energía ahorra la ruta de mínima energía frente a la de mínimo número de saltos?

\((1195-747)/1195\approx37{,}5\ \%\) (747 y 1 195 m² son los valores redondeados de la tabla).

El algoritmo de Dijkstra sirve también cuando algunos pesos de las aristas son negativos.

Falso. Dijkstra supone que añadir una arista nunca acorta un camino, lo que exige pesos no negativos. Con pesos negativos se usa Bellman–Ford (bellman_ford_shortest_paths).

J3.9.4 Conectividad y nodos críticos

Un grafo es conexo si hay camino entre cualquier par de nodos; si no, se parte en componentes conexas. Para una red de sensores interesan los puntos de articulación (nodos cuya pérdida parte la red) y los puentes (enlaces con la misma propiedad): son los puntos débiles, porque un único fallo (una batería, una rama que tapa el enlace) deja sin datos a toda una parte. Graphs.jl los calcula con articulation y bridges, y induced_subgraph permite ver qué pasaría al quitar un nodo. El alcance mínimo para que la red sea conexa es el mayor enlace del árbol generador de peso mínimo (kruskal_mst) del grafo completo, el primer problema de la nota de Dijkstra:

Wc = red_sensores(pos; alcance=Inf)                      # todos con todos
arbol = kruskal_mst(SimpleGraph(Wc), Wc)
partes(v) = sort(length.(connected_components(induced_subgraph(g, setdiff(1:nv(g), v))[1])), rev=true)
(conexo = is_connected(g), articulacion = articulation(g), puente = [(src(e), dst(e)) for e in bridges(g)],
 alcance_minimo_m = round(maximum(Wc[src(e), dst(e)] for e in arbol), digits=2),
 partes_sin_el_12 = partes(12), partes_sin_el_14 = partes(14))

(conexo = true, articulacion = [12, 14], puente = [(12, 14)], alcance_minimo_m = 11.35, partes_sin_el_12 = [11, 4], partes_sin_el_14 = [12, 3])

Con 12 m, la red es conexa pero frágil: los nodos 12 y 14 son puntos de articulación y el enlace 12–14 es un puente. El alcance mínimo es 11,35 m, casi igual que el usado (12 m), por lo que no hay holgura. Subir el alcance da redundancia, pero cuesta energía (suma de \(d^{2}\) de todos los enlaces):

filas = map([12.0, 13.0, 14.0]) do r
    Wr = red_sensores(pos; alcance=r)
    gr = SimpleGraph(Wr)
    art = articulation(gr)
    "| $(coma(r, d=0)) | $(ne(gr)) | $(isempty(art) ? "ninguno" : join(art, ", ")) | $(coma(sum(abs2, nonzeros(Wr)) / 2, d=0)) |"
end
println("| alcance (m) | enlaces | puntos de articulación | energía total de enlaces (m²) |\n|---|---|---|---|\n" * join(filas, "\n"))

Tabla 2: Efecto del alcance en la robustez y el coste de la red.

alcance (m)	enlaces	puntos de articulación	energía total de enlaces (m²)
12	28	12, 14	2483
13	34	ninguno	3388
14	36	ninguno	3740

Con 13 m desaparecen los puntos de articulación (la red sobrevive a la caída de cualquier nodo), a cambio de 36 % más de energía total de enlaces (3 388 frente a 2 483 m²). Es el compromiso típico de diseño de una red de sensores.

¿Cuál es el alcance mínimo, en metros, con el que la red de 16 sensores es conexa?

Es el mayor peso del árbol generador mínimo del grafo completo.

11,35 m (el enlace limitante es el de mayor longitud del árbol mínimo). Con 11,0 m la red no es conexa.

J3.9.5 Estructuras reticuladas y subestructuras

Un reticulado (cercha) es un conjunto de barras articuladas en nudos: es un grafo, con los nudos como vértices y las barras como aristas. reticulado_plano(nx, ny) genera uno rectangular con diagonales, adyacencia_barras su matriz de adyacencia, y SimpleGraph el grafo. El conteo de Maxwell para uno plano con \(j\) nudos, \(b\) barras y \(r\) reacciones dice que hacen falta \(b+r\ge2j\) para que sea estable: con \(j=14\) y \(r=3\) apoyos, \(b\ge25\).

posr, barras = reticulado_plano(6, 1; dx=2.0, dy=2.0)    # 6 módulos de 2 m × 2 m
n = size(posr, 1)
A = adyacencia_barras(n, barras)
gr = SimpleGraph(A)
(nudos = nv(gr), barras = ne(gr), maxwell_2j_menos_3 = 2n - 3, conexo = is_connected(gr),
 laplaciana_igual_a_Graphs = laplaciana(A) == Matrix(laplacian_matrix(gr)))

(nudos = 14, barras = 25, maxwell_2j_menos_3 = 25, conexo = true, laplaciana_igual_a_Graphs = true)

Con 25 barras es justamente isostático (\(b+3=2j\)). La laplaciana del grafo, \(\mathbf L=\mathbf D-\mathbf A\) (laplaciana o laplacian_matrix), es la matriz de rigidez de una red de muelles sin apoyos: su núcleo tiene tantas dimensiones como componentes conexas (los movimientos de sólido rígido que no cuestan energía), y su segundo valor propio más pequeño, la conectividad algebraica de Fiedler, mide lo lejos que está el grafo de partirse. Al quitar las barras que cruzan el módulo central (tres: dos cordones y una diagonal) se ve cómo la estructura se separa en subestructuras:

cruce = [k for (k, (i, j)) in enumerate(barras) if posr[i, 1] < 5.0 && posr[j, 1] > 5.0]    # barras entre x = 4 y x = 6
filas = map([0, 1, 2, 3]) do q
    resto = barras[setdiff(1:length(barras), cruce[1:q])]
    ev = eigvals(Symmetric(laplaciana(adyacencia_barras(n, resto))))
    "| $q | $(length(connected_components(SimpleGraph(adyacencia_barras(n, resto))))) | $(count(<(1e-9), ev)) | $(coma(max(ev[2], 0.0), d=3)) |"
end
println("| barras quitadas | componentes | núcleo de L | λ₂ (Fiedler) |\n|---|---|---|---|\n" * join(filas, "\n"))

Tabla 3: Barras retiradas del módulo central del reticulado de 14 nudos (cruzan en total tres). Con las tres quitadas aparecen dos subestructuras y un segundo modo de sólido rígido.

barras quitadas	componentes	núcleo de L	λ₂ (Fiedler)
0	1	1	0,295
1	1	1	0,243
2	1	1	0,154
3	2	2	0,000

Dos avisos. (1) La conectividad es una condición necesaria para que una estructura sea estable, no suficiente: quitar una sola barra del reticulado (Tabla 3) lo deja conexo pero ya sin \(b+r\ge2j\), es decir, hipostático (un mecanismo); eso lo detecta el conteo de Maxwell y la rigidez, no solo el grafo. (2) La unión con la vía M es directa: el patrón de ceros de la matriz de rigidez es un grafo (grafo_de_matriz), y sus componentes conexas son bloques desacoplados que se pueden resolver por separado (J3.3). Para el edificio de tres plantas, el grafo es un camino 1–2–3 (cada planta solo se acopla con la contigua).

let
    seg(lista) = [Point2f(posr[i, 1], posr[i, 2]) => Point2f(posr[j, 1], posr[j, 2]) for (i, j) in lista]
    quitadas = barras[cruce]
    resto = setdiff(barras, quitadas)
    comp = connected_components(SimpleGraph(adyacencia_barras(n, resto)))
    col = fill(GRIS, n); for (k, c) in enumerate(comp), v in c; col[v] = [AZUL, VERDE, NARANJA][k]; end
    fig = Figure(size=(720, 310))
    ax1 = Axis(fig[1, 1], title="(a) intacto", ylabel="y (m)", aspect=DataAspect())
    linesegments!(ax1, seg(resto), color=GRIS, linewidth=2)
    linesegments!(ax1, seg(quitadas), color=NARANJA, linewidth=3.5)
    scatter!(ax1, posr[:, 1], posr[:, 2], color=:white, strokecolor=TINTA, strokewidth=1.5, markersize=11)
    ax2 = Axis(fig[2, 1], title="(b) sin las tres barras", xlabel="x (m)", ylabel="y (m)", aspect=DataAspect())
    linesegments!(ax2, seg(resto), color=GRIS, linewidth=2)
    scatter!(ax2, posr[:, 1], posr[:, 2], color=col, markersize=14)
    fig
end

Figura 4: Reticulado de 6 módulos (14 nudos y 25 barras). (a) Intacto, con las tres barras del módulo central en naranja. (b) Sin esas tres barras, el reticulado se separa en dos subestructuras (azul, 6 nudos, y verde, 8 nudos) sin ninguna unión entre ellas.

NotaIdea clave

Un grafo convierte preguntas sobre redes y estructuras en preguntas con algoritmo y coste conocidos: BFS para saltos mínimos, Dijkstra para pesos no negativos, componentes, articulaciones y puentes para robustez, árbol generador mínimo para el alcance mínimo. Y el grafo de una matriz dispersa muestra qué grados de libertad están acoplados. Pero el grafo solo ve la conexión, no la rigidez: una estructura puede ser conexa y ser un mecanismo.

AdvertenciaErrores frecuentes

1. Confundir el camino de menos saltos con el de menor peso (Tabla 1). (2) Usar Dijkstra con pesos negativos. (3) Pasar a dijkstra_shortest_paths una matriz de pesos con ceros donde sí hay aristas (un peso cero se confunde con «sin arista» al construir el grafo a partir de la matriz). (4) Dar por buena una red «conexa» sin mirar sus puntos de articulación. (5) Construir una matriz de adyacencia densa para miles de nodos, cuando hay pocas aristas. (6) Tomar un grafo conexo por estructura estable (conexo no es rígido). (7) Olvidar que SimpleGraph numera los vértices desde 1 y que quitar un vértice renumera los demás (usa el vmap de induced_subgraph).

Para saber más

• La documentación de Graphs.jl (algoritmos de caminos, conectividad y árboles).
• Comparación con Python: networkx ofrece shortest_path, articulation_points y minimum_spanning_tree con la misma lógica; no se ejecuta aquí.

Práctica guiada

Diagnostica la robustez de la red de sensores del puente, paso a paso.

Paso 1. La red. Con el alcance de 12 m, ¿qué nodos tienen solo 2 enlaces (los más vulnerables) y a qué distancia está su vecino más cercano?

(nodos_de_grado_2 = findall(==(2), degree(g)), distancia_al_vecino_mas_cercano_m = round.([minimum(nonzeros(W[:, v])) for v in findall(==(2), degree(g))], digits=1))

(nodos_de_grado_2 = [1, 2, 15], distancia_al_vecino_mas_cercano_m = [6.4, 6.4, 7.3])

Paso 2. Qué se pierde. Para cada uno de los nodos de articulación, ¿cuántos sensores quedan sin conexión con la pasarela si cae?

function aislados(v)
    h, vmap = induced_subgraph(g, setdiff(1:nv(g), v))
    c = connected_components(h)
    sin_pasarela = [c_ for c_ in c if !(1 in vmap[c_])]
    return sum(length, sin_pasarela; init=0)
end
Dict(v => aislados(v) for v in articulation(g))

Dict{Int64, Int64} with 2 entries:
  12 => 4
  14 => 3

Si cae el nodo 12 se pierden 4 sensores (13, 14, 15 y 16, que quedan sin camino hasta la pasarela); si cae el 14, se pierden 3 (13, 15 y 16). Si cae un nodo que no es de articulación, no se pierde ninguno (salvo él). La pasarela (nodo 1) tiene solo dos enlaces, como los nodos 2 y 15: conviene vigilarlos.

Paso 3. Reforzar la red. El diseñador puede subir el alcance (energía) o añadir un nodo repetidor. Se coloca uno a mitad del enlace puente 12–14 y se comprueba que desaparecen los puntos de articulación sin subir el alcance:

extra = vcat(pos, (pos[12:12, :] .+ pos[14:14, :]) ./ 2)       # nodo 17 en el punto medio del enlace 12–14
g17 = SimpleGraph(red_sensores(extra; alcance=12.0))
(nodos = nv(g17), enlaces = ne(g17), articulacion = articulation(g17), conexo = is_connected(g17),
 saltos_maximos_a_pasarela = maximum(gdistances(g17, 1)))

(nodos = 17, enlaces = 32, articulacion = Int64[], conexo = true, saltos_maximos_a_pasarela = 8)

«Pídeselo a Claude»

TipPrompt

«Con Julia, --project=., Graphs y Resonancia.jl: genera las 16 posiciones de sensores del puente con MersenneTwister(9) (dos filas, x = 10 i + 3(u−0,5), y ∈ {0; 6} + 2(u−0,5)), construye la red con red_sensores(pos; alcance=12.0) y (1) dime el número de enlaces, los puntos de articulación y los puentes; (2) calcula con dijkstra_shortest_paths la ruta del nodo 1 al 16 de mínima energía (peso W .^ 2) con alcance de 20 m y compárala con la de mínimo número de saltos; (3) halla el alcance mínimo de conexión con kruskal_mst. Comprueba cada resultado con una segunda vía (por ejemplo, la conectividad con los valores propios de la laplaciana). No inventes valores: si algo no sale, dilo.»

Verifica. (a) Que hay 28 enlaces, puntos de articulación 12 y 14, y un puente 12–14. (b) Que la ruta de mínima energía tiene 8 saltos y 747 m², y la de mínimo número de saltos, 5 y 1 195 m². (c) Que el alcance mínimo es 11,35 m. (d) Que la segunda vía coincide (el número de valores propios nulos de la laplaciana es el de componentes). (e) Que no ha usado pesos cero para «sin enlace» donde sí había enlace. (f) Que no ha ordenado nodos por índice dando por hecho que son contiguos tras quitar uno.

Ejercicios

Un reticulado plano tiene 10 nudos y 3 reacciones. ¿Cuántas barras tiene, como mínimo, para ser estable según el conteo de Maxwell (\(b+r\ge2j\))?

\(b\ge2j-r=20-3=17\) barras.

Tras añadir el nodo repetidor en el punto medio del enlace 12–14 (Paso 3), ¿cuántos puntos de articulación tiene la red?

Ninguno: el repetidor, a unos 5,7 m de los nodos 12 y 14, se une también a sus vecinos más próximos y crea caminos alternativos que rodean el enlace puente.

Si el grafo de un reticulado es conexo, la estructura es estable.

Falso. La conexión es necesaria, pero no suficiente: un reticulado conexo puede ser un mecanismo (menos barras de las que pide el conteo de Maxwell, o mal distribuidas).

Un compañero afirma: «mi red de sensores está bien, todos los nodos están conectados». ¿Qué le preguntas antes de darla por buena?

• Pregunta por los puntos de articulación y puentes: qué se pierde si cae un solo nodo.
• Pregunta por el alcance usado frente al mínimo de conexión, para saber la holgura.
• Pregunta por el criterio de ruta (saltos, distancia o energía) y por la latencia y la batería.
• Propone redundancia (más alcance o repetidores) y la compara en coste.

La doy por superada si…

• Construyo un grafo en Graphs.jl (a mano o desde una matriz) y leo grados y vecinos.
• Sé cuándo usar BFS, DFS y Dijkstra, y que Dijkstra exige pesos no negativos.
• Calculo la conectividad de una red de sensores: componentes, puntos de articulación, puentes y alcance mínimo.
• Represento un reticulado como grafo y explico por qué la conexión no basta para la estabilidad.

Cierre. Escribe tres líneas: qué he entendido, qué todavía no domino y cuál es mi siguiente paso pequeño. Antes de aceptar una «ruta óptima» de Claude, pregunta por el criterio de peso.

Siguiente: M9 · Nodos embebidos y redes de sensores, donde se usa la red de sensores, o el índice de J3.