The network is given as a symmetric adjacency matrix. Each entry is either a positive integer edge weight or the symbol - for "no direct edge". We want to remove as much total weight as possible while keeping all 40 vertices connected. If \(G=(V,E,w)\) is the original weighted graph, the target quantity is the largest possible saving
$$\operatorname{saving}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
where \(H\) ranges over connected spanning subgraphs of \(G\).
The key observation is that an optimal connected network can never contain a cycle. That turns the problem into a minimum spanning tree problem: keep the cheapest possible connected backbone, then subtract its weight from the original total.
Let \(G=(V,E,w)\) be the weighted undirected graph extracted from the matrix, with \(n=|V|=40\). The derivation has two distinct parts. First we identify what a minimal network must look like. Then we justify the greedy construction used by the implementations.
Suppose \(H\) is a connected spanning subgraph of \(G\) with minimum total weight. If \(H\) contained a cycle, then deleting any one edge from that cycle would leave all vertices on the cycle still connected through the remaining edges of the cycle. So the graph would stay connected but become strictly lighter. That contradicts the assumption that \(H\) was already minimal.
Therefore every optimal connected spanning subgraph is acyclic. A connected acyclic graph on \(n\) vertices is a spanning tree, so any optimal network has exactly \(n-1\) edges. The problem is therefore equivalent to
$$\text{find a spanning tree }T\subseteq G\text{ minimizing }W(T).$$
Any such tree is a minimum spanning tree (MST). Once its weight is known, the saving is simply
$$\operatorname{saving}=W(G)-W(T_{\min}).$$
Uniqueness is irrelevant here: even if several MSTs exist, they all have the same total weight, so the saving is well defined.
Because the graph is undirected, the adjacency matrix is symmetric. The edge between vertices \(i\) and \(j\) appears twice, at positions \((i,j)\) and \((j,i)\). So the correct way to build the graph is to read only the upper triangle \(i<j\). Every non-dash entry contributes one undirected edge and one copy of its weight.
That means the total original weight is
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
This formula matches the way the implementations accumulate the original network cost before any edges are removed.
List the edges as \(e_1,e_2,\dots,e_m\) in nondecreasing order of weight:
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
Kruskal's algorithm scans this list from left to right. An edge is accepted exactly when its endpoints lie in different connected components of the forest built so far; otherwise it would create a cycle and is skipped.
Two invariants drive the proof. First, the chosen edges always form a forest, because no accepted edge ever closes a cycle. Second, after every accepted edge there is still some MST containing all chosen edges. This is the safe-edge statement behind the cut property: when the algorithm selects the lightest edge joining two current components, that edge is a minimum-weight edge crossing the cut determined by either component, so replacing another crossing edge in an MST cannot increase the total weight.
Each accepted edge reduces the number of connected components by one. Starting from \(n\) isolated vertices, after exactly \(n-1\) accepted edges we obtain a connected acyclic graph, hence a spanning tree. By the invariant above, that spanning tree has minimum possible total weight.
The only dynamic question in Kruskal's algorithm is whether two vertices are already in the same component. A disjoint-set union structure stores the current partition of the vertex set. The operation "find" identifies the representative of a component, and "union" merges two components after a safe edge is accepted.
With path compression and union by rank, the amortized cost per operation is \(O(\alpha(n))\), where \(\alpha\) is the inverse Ackermann function. For a 40-vertex graph this cost is effectively constant, so the dominant work lies in sorting the edges, not in maintaining connectivity.
The sample network in the statement has 7 vertices. Reading only the upper triangle gives the 12 edge weights
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31,$$
so the total weight of the original graph is
$$W(G)=243.$$
Processing these weights in ascending order, Kruskal accepts
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,$$
because each of them still joins two different components at the moment it is considered. Those six edges already connect all 7 vertices, so they form a spanning tree with weight
$$W(T_{\min})=11+12+16+17+18+19=93.$$
Every remaining edge would create a cycle and is therefore redundant. The saving is
$$243-93=150,$$
which is exactly the value quoted in the problem statement and checked by the C++ implementation.
Once the minimum spanning tree has been found, the output is not another graph but a scalar difference:
$$\boxed{\operatorname{saving}=W(G)-W(T_{\min}).}$$
So the computation naturally splits into two totals: one over all original edges, and one over the \(n-1\) edges that survive in the MST.
The C++, Python, and Java implementations read the comma-separated matrix row by row and ignore blank lines. For row \(i\), they inspect only columns \(j>i\). If an entry is -, no edge is added. Otherwise the token is converted to an integer weight, appended to the edge list, and added to the running total \(W(G)\).
This upper-triangle scan is the concrete implementation of the mathematical observation that each undirected edge should be counted exactly once.
After the edge list has been built, the implementation sorts it by weight and initializes one disjoint-set component per vertex. It then scans the sorted edges. Whenever an edge connects two different components, that edge is accepted into the spanning tree, its weight is added to the MST total, and the two components are merged.
If both endpoints are already in the same component, the edge would close a cycle and is ignored. The C++ implementation stops as soon as \(n-1\) edges have been accepted. The Python and Java implementations continue scanning the sorted list, but the connectivity test prevents any extra weight from being added after the tree is complete.
At the end, all three implementations subtract the MST total from the original total. The C++ implementation also includes the 7-vertex sample network as a checkpoint and verifies that the saving for that sample is \(150\) before solving the full instance.
Let \(n\) be the number of vertices and \(m\) the number of edges that actually appear in the network. Parsing the matrix costs \(O(n^2)\), because the input is an \(n\times n\) table. The dominant step in Kruskal's algorithm is sorting the edge list:
$$O(m\log m).$$
The disjoint-set operations contribute \(O(m\,\alpha(n))\), which is asymptotically smaller than the sorting cost. Space usage is \(O(m+n)\): the edge list stores the graph, and the disjoint-set structure stores one representative and one rank-like value per vertex.
For Problem 107 specifically, \(n=40\), and even a complete graph would have only \(40\cdot 39/2=780\) edges. So the program is easily fast enough; the real content of the problem is the mathematical reduction from "remove redundant weight while preserving connectivity" to "compute an MST and subtract".
Das Netzwerk ist als symmetrische Adjazenzmatrix gegeben. Jeder Eintrag ist entweder ein positives ganzzahliges Kantengewicht oder das Symbol - fur "keine direkte Kante". Gesucht ist die maximal mogliche Einsparung, wenn man Kanten entfernt, ohne die Konnektivitat der 40 Knoten zu verlieren. Fur den ursprunglichen gewichteten Graphen \(G=(V,E,w)\) ist also
$$\operatorname{Einsparung}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
zu maximieren, wobei \(H\) ein zusammenhangender aufspannender Teilgraph von \(G\) ist.
Die entscheidende Beobachtung lautet: Ein optimales zusammenhangendes Netzwerk kann keinen Kreis enthalten. Damit wird die Aufgabe unmittelbar zu einem Problem des minimalen Spannbaums: Man behalt den billigsten moglichen zusammenhangenden Kern und zieht dessen Gewicht von der ursprunglichen Gesamtsumme ab.
Sei \(G=(V,E,w)\) der aus der Matrix gelesene gewichtete ungerichtete Graph mit \(n=|V|=40\). Die Herleitung hat zwei Schritte. Zuerst muss geklart werden, wie ein minimales Netzwerk uberhaupt aussieht. Danach wird begrundet, warum die gierige Konstruktion von Kruskal genau dieses Objekt liefert.
Angenommen, \(H\) sei ein zusammenhangender aufspannender Teilgraph von \(G\) mit minimalem Gesamtgewicht. Falls \(H\) einen Kreis enthielte, konnte man eine beliebige Kante dieses Kreises entfernen. Die ubrigen Kanten des Kreises verbinden dessen Knoten weiterhin, also bliebe der Graph zusammenhangend, hatte aber strikt kleineres Gewicht. Das widerspricht der Minimalitat von \(H\).
Also ist jeder optimale zusammenhangende aufspannende Teilgraph kreisfrei. Ein zusammenhangender kreisfreier Graph auf \(n\) Knoten ist ein Spannbaum, also besitzt jedes optimale Netzwerk genau \(n-1\) Kanten. Die Aufgabe ist daher aquivalent zu
$$\text{einen Spannbaum }T\subseteq G\text{ mit minimalem }W(T)\text{ zu finden.}$$
Ein solcher Baum ist ein minimaler Spannbaum (MST), und danach gilt schlicht
$$\operatorname{Einsparung}=W(G)-W(T_{\min}).$$
Ob der MST eindeutig ist, spielt keine Rolle: Alle MSTs haben dasselbe Gesamtgewicht, also ist auch die Einsparung eindeutig bestimmt.
Weil der Graph ungerichtet ist, ist die Matrix symmetrisch. Die Kante zwischen \(i\) und \(j\) erscheint sowohl an Position \((i,j)\) als auch an \((j,i)\). Um doppelte Zahlung zu vermeiden, liest man daher nur das obere Dreieck mit \(i<j\). Jeder Eintrag ungleich - erzeugt genau eine ungerichtete Kante mit genau einem Gewichtsbeitrag.
Damit lautet das Gesamtgewicht des Ausgangsgraphen
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
Genau diese Summe wird in den Implementierungen aufgebaut, bevor uberhaupt eine MST-Kante ausgewahlt wird.
Ordne die Kanten als \(e_1,e_2,\dots,e_m\) nach nicht absteigendem Gewicht:
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
Kruskals Algorithmus durchlauft diese Liste von links nach rechts. Eine Kante wird genau dann ubernommen, wenn ihre Endpunkte in verschiedenen Zusammenhangskomponenten des bisher aufgebauten Waldes liegen; andernfalls wurde sie einen Kreis schliessen und wird verworfen.
Zwei Invarianten tragen den Beweis. Erstens bilden die gewahlten Kanten zu jedem Zeitpunkt einen Wald, weil nie eine Kante akzeptiert wird, die einen Kreis erzeugt. Zweitens existiert nach jeder akzeptierten Kante weiterhin ein MST, der alle bisher akzeptierten Kanten enthalt. Das ist die Safe-Edge-Aussage hinter der Schnitteigenschaft: Wenn der Algorithmus die leichteste Kante zwischen zwei aktuellen Komponenten nimmt, ist sie eine Kante minimalen Gewichts uber den zugehorigen Schnitt hinweg; daher kann man einen MST so anpassen, dass diese Kante enthalten ist, ohne das Gesamtgewicht zu erhohen.
Jede akzeptierte Kante reduziert die Zahl der Komponenten um eins. Beginnend mit \(n\) isolierten Knoten entsteht nach genau \(n-1\) akzeptierten Kanten ein zusammenhangender kreisfreier Graph, also ein Spannbaum. Wegen der zweiten Invariante hat dieser Baum minimales mogliches Gewicht.
Die einzige dynamische Frage in Kruskals Verfahren lautet, ob zwei Knoten bereits in derselben Komponente liegen. Eine Disjoint-Set-Union-Struktur speichert die aktuelle Partition der Knotenmenge. "Find" liefert den Reprasentanten einer Komponente, und "Union" verschmilzt zwei Komponenten, wenn eine sichere Kante akzeptiert wird.
Mit Pfadkompression und Union by Rank betragt die amortisierte Laufzeit pro Operation \(O(\alpha(n))\), wobei \(\alpha\) die inverse Ackermann-Funktion ist. Fur einen Graphen mit 40 Knoten ist das praktisch konstant; die eigentliche Arbeit steckt also im Sortieren der Kanten.
Im Beispielnetz mit 7 Knoten liefert das obere Matrixdreieck die 12 Kantengewichte
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31,$$
also insgesamt
$$W(G)=243.$$
In aufsteigender Reihenfolge akzeptiert Kruskal die sechs Gewichte
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,$$
weil jede dieser Kanten zum Zeitpunkt ihrer Betrachtung noch zwei verschiedene Komponenten verbindet. Diese sechs Kanten verbinden bereits alle 7 Knoten und bilden daher einen Spannbaum mit Gewicht
$$W(T_{\min})=11+12+16+17+18+19=93.$$
Alle ubrigen Kanten wurden einen Kreis erzeugen und sind somit uberflussig. Die Einsparung betragt also
$$243-93=150,$$
genau wie im Beispiel der Aufgabe und in der eingebauten Prufung der C++-Implementierung.
Sobald der minimale Spannbaum feststeht, ist die Ausgabe keine weitere Graphstruktur mehr, sondern nur noch eine Differenz:
$$\boxed{\operatorname{Einsparung}=W(G)-W(T_{\min}).}$$
Die gesamte Rechnung zerfallt also naturlich in zwei Summen: eine uber alle ursprunglichen Kanten und eine uber die \(n-1\) Kanten, die im MST verbleiben.
Die C++-, Python- und Java-Implementierungen lesen die kommaseparierte Matrix zeilenweise ein und ignorieren leere Zeilen. Fur Zeile \(i\) werden nur die Spalten \(j>i\) betrachtet. Steht dort -, existiert keine Kante. Andernfalls wird der Eintrag in ein ganzzahliges Gewicht umgewandelt, in die Kantenliste aufgenommen und zum laufenden Wert \(W(G)\) addiert.
Dieses Einlesen des oberen Dreiecks ist die direkte Umsetzung der mathematischen Beobachtung, dass jede ungerichtete Kante genau einmal gezahlt werden darf.
Nach dem Aufbau der Kantenliste sortiert die Implementierung diese nach Gewicht und initialisiert fur jeden Knoten eine eigene Disjoint-Set-Komponente. Anschliessend werden die sortierten Kanten durchlaufen. Immer wenn eine Kante zwei verschiedene Komponenten verbindet, wird sie in den Spannbaum ubernommen, ihr Gewicht zum MST-Gesamtgewicht addiert und die beiden Komponenten werden vereinigt.
Liegen beide Endpunkte bereits in derselben Komponente, wurde die Kante einen Kreis schliessen und wird ignoriert. Die C++-Version stoppt, sobald \(n-1\) Kanten akzeptiert wurden. Die Python- und Java-Versionen durchlaufen die restliche sortierte Liste weiter, aber der Komponenten-Test verhindert jedes zusatzliche Gewicht, sobald der Baum vollstandig ist.
Am Ende ziehen alle drei Implementierungen das MST-Gewicht vom ursprunglichen Gesamtgewicht ab. Die C++-Implementierung enthalt zusatzlich das 7-Knoten-Beispiel als Kontrolltest und verifiziert vor der eigentlichen Aufgabe, dass dort die Einsparung \(150\) herauskommt.
Sei \(n\) die Zahl der Knoten und \(m\) die Zahl der tatsachlich vorhandenen Kanten. Das Einlesen der Matrix kostet \(O(n^2)\), weil die Eingabe eine \(n\times n\)-Tabelle ist. Der dominierende Schritt in Kruskals Algorithmus ist das Sortieren der Kantenliste:
$$O(m\log m).$$
Die Disjoint-Set-Operationen tragen \(O(m\,\alpha(n))\) bei und sind damit asymptotisch kleiner als die Sortierkosten. Der Speicherverbrauch ist \(O(m+n)\): Die Kantenliste speichert den Graphen, und die Disjoint-Set-Struktur speichert pro Knoten einen Reprasentanten und eine Ranginformation.
Fur Problem 107 gilt konkret \(n=40\), und selbst ein vollstandiger Graph hatte nur \(40\cdot 39/2=780\) Kanten. Das Programm ist also ohne Weiteres schnell genug; der eigentliche mathematische Kern ist die Reduktion von "uberflussiges Gewicht entfernen, aber verbunden bleiben" auf "MST berechnen und abziehen".
Ag, simetrik bir komsuluk matrisi olarak verilir. Her giris ya pozitif bir kenar agirligi ya da "dogrudan kenar yok" anlamina gelen - semboludur. Amac, 40 dugumun tamami bagli kalacak sekilde toplam agirliktan mumkun olan en buyuk miktari cikarmaktir. Orijinal agirlikli graf \(G=(V,E,w)\) icin hedef buyukluk
$$\operatorname{tasarruf}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
olup burada \(H\), \(G\)'nin bagli ve tum dugumleri kapsayan alt graflari arasindan secilir.
Temel gozlem sudur: en iyi bagli ag hicbir zaman dongu iceremez. Bu nedenle soru dogrudan minimum yayilan agac problemine indirgenir. Once baglantiyi koruyan en ucuz iskelet bulunur, sonra bu iskeletin agirligi orijinal toplamdan cikarilir.
Matriksten elde edilen agirlikli yonsuz grafi \(G=(V,E,w)\) ile gosterelim; burada \(n=|V|=40\). Turetim iki parcalidir. Ilk olarak "minimal ag" denen nesnenin nasil bir yapi olmak zorunda oldugunu belirleriz. Ardindan, uygulamalarda kullanilan acgozlu kuralin neden dogru oldugunu aciklariz.
Diyelim ki \(H\), \(G\)'nin toplam agirligi en kucuk olan bagli bir yayilan alt grafigi olsun. Eger \(H\) bir dongu icerseydi, bu dongudeki herhangi bir kenari silebilirdik. Dongunun geri kalan kenarlari ayni dugumleri birbirine bagli tutacagi icin graf bagli kalirdi; fakat toplam agirlik azalirdi. Bu da \(H\)'nin zaten minimal oldugu varsayimiyla celisir.
Dolayisiyla optimal bagli yayilan alt graf dongusuz olmak zorundadir. \(n\) dugumlu bagli ve dongusuz bir graf tam olarak bir yayilan agactir; bu yuzden optimal ag tam \(n-1\) kenar icerir. Problem su hale gelir:
$$\text{agirligi en kucuk olan bir }T\subseteq G\text{ yayilan agacini bul.}$$
Boyle bir agac minimum yayilan agactir (MST) ve sonra tasarruf dogrudan
$$\operatorname{tasarruf}=W(G)-W(T_{\min})$$
olur. Birden fazla MST olsa bile sorun degildir; hepsinin toplam agirligi aynidir, dolayisiyla tasarruf degeri de tektir.
Graf yonsuz oldugu icin komsuluk matrisi simetriktir. \(i\) ile \(j\) arasindaki kenar hem \((i,j)\) hem de \((j,i)\) konumunda gorunur. Cifte sayimi engellemek icin yalnizca \(i<j\) olan ust ucgen okunur. - olmayan her giris, tek bir yonsuz kenar ve agirliginin tek bir kopyasi demektir.
Buna gore orijinal toplam agirlik
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}$$
seklindedir. Uygulamalar MST hesaplamasina gecmeden once tam olarak bu toplami biriktirir.
Kenarlar \(e_1,e_2,\dots,e_m\) olacak sekilde artmayan degil, artan agirlik sirasina dizilsin:
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
Kruskal algoritmasi bu listeyi soldan saga tarar. Bir kenar ancak iki ucu o ana kadar kurulmus ormandaki farkli baglanti bilesenlerinde ise kabul edilir; aksi durumda bir dongu olusturacagi icin atlanir.
Isbatti tasiyan iki degismez vardir. Birincisi, secilen kenarlar her zaman bir orman olusturur; cunku kabul edilen hicbir kenar dongu kapatmaz. Ikincisi, her kabul edilen kenardan sonra secilmis kenarların tumunu iceren en az bir MST hala vardir. Bu, kesim ozelliginin verdigi "guvenli kenar" sonucudur: algoritma mevcut iki bileseni birlestiren en hafif kenari aldiginda, bu kenar o kesiti gecen minimum agirlikli bir kenardir; dolayisiyla bir MST icindeki baska bir gecis kenari bununla degistirilebilir ve toplam agirlik artmaz.
Her kabul edilen kenar baglanti bileseni sayisini bir azaltir. Baslangicta \(n\) ayri dugum vardir; tam \(n-1\) kabulden sonra bagli ve dongusuz bir graf, yani bir yayilan agac elde edilir. Ikinci degismez nedeniyle bu agac mumkun olan en kucuk toplam agirligina sahiptir.
Kruskal'da dinamik olarak sorulan tek soru, iki dugumun zaten ayni bilesende olup olmadigidir. Ayrik kumeler birlesimi yapisi, dugumlerin o anki parcali yapisini saklar. "Find" bir dugumun temsilcisini verir, "union" ise guvenli bir kenar kabul edilince iki bileseni birlestirir.
Yol sikistirma ve dereceye gore birlestirme kullanildiginda, bu islemlerin amortize maliyeti islem basina \(O(\alpha(n))\) olur; burada \(\alpha\), ters Ackermann fonksiyonudur. 40 dugumlu bir ag icin bu maliyet fiilen sabittir; yani asil yuk kenarlari siralamaktadir.
Sorudaki 7 dugumlu ornek agda ust ucgen okununca 12 kenar agirligi elde edilir:
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31.$$
Bunlarin toplami
$$W(G)=243$$
eder. Kruskal bu agirliklari kucukten buyuge islerken
$$11,\ 12,\ 16,\ 17,\ 18,\ 19$$
agirliklarini kabul eder; cunku bunlarin her biri ele alindigi anda hala iki farkli bileseni baglamaktadir. Bu alti kenar 7 dugumun tamamini baglamaya yettigi icin bir yayilan agac verir ve bu agacin agirligi
$$W(T_{\min})=11+12+16+17+18+19=93$$
olur. Geri kalan her kenar bir dongu kapatacagindan gereksizdir. Tasarruf miktari
$$243-93=150$$
olup hem problemdeki ornekle hem de C++ uygulamasindaki kontrolle aynidir.
Minimum yayilan agac bulunduktan sonra istenen cikti yeni bir graf degil, yalnizca bir farktir:
$$\boxed{\operatorname{tasarruf}=W(G)-W(T_{\min}).}$$
Dolayisiyla hesap iki dogal toplama ayrilir: biri orijinal tum kenarlar, digeri de MST'de kalan \(n-1\) kenar uzerinden.
C++, Python ve Java uygulamalari virgulle ayrilmis matrisi satir satir okur ve bos satirlari yok sayar. \(i\). satir icin yalnizca \(j>i\) sutunlari incelenir. Bir giris - ise kenar yoktur. Aksi halde deger tamsayi agirligina cevrilir, kenar listesine eklenir ve ayni anda \(W(G)\) toplamına katilir.
Bu ust ucgen taramasi, yonsuz her kenarin tam bir kez sayilmasi gerektigi yolundaki matematiksel gozlemin dogrudan koddaki karsiligidir.
Kenar listesi hazir olunca uygulama onu agirliga gore siralar ve her dugum icin ayri bir ayrik-kume bileseni baslatir. Daha sonra sirali kenarlar taranir. Bir kenar iki farkli bileseni bagliyorsa MST'ye alinir, agirligi MST toplamına eklenir ve iki bilesen birlestirilir.
Iki uc zaten ayni bilesendeyse bu kenar dongu olusturur ve yok sayilir. C++ uygulamasi \(n-1\) kenar kabul edildigi anda durur. Python ve Java uygulamalari ise listenin kalanini da gezer; ancak bilesen testi agac tamamlandiktan sonra hicbir ek agirligin eklenmesine izin vermez.
Son adimda uc uygulamanin tamami MST toplamını orijinal toplamdan cikarir. C++ uygulamasi ayrica 7 dugumlu ornek agi bir kontrol noktasi olarak icerir ve tam probleme gecmeden once bu ornekte tasarrufun \(150\) oldugunu dogrular.
\(n\) dugum sayisi, \(m\) ise agda gercekten bulunan kenar sayisi olsun. Matrisi okumak, girdi \(n\times n\) tablo oldugu icin \(O(n^2)\) maliyetlidir. Kruskal'daki baskin adim kenar listesini siralamaktir:
$$O(m\log m).$$
Ayrik-kume islemleri \(O(m\,\alpha(n))\) katkisi yapar ve bu, asimptotik olarak siralamadan daha kucuktur. Bellek kullanimi \(O(m+n)\)'dir: kenar listesi grafin kendisini, ayrik-kume yapisi ise her dugum icin bir temsilci ve bir seviye bilgisi tutar.
Problem 107 icin ozel olarak \(n=40\)'tir ve tam graf olsa bile sadece \(40\cdot 39/2=780\) kenar vardir. Bu nedenle calisma suresi acisindan hicbir zorluk yoktur; asil nokta, "baglantiyi bozmadan gereksiz agirligi sil" ifadesinin "MST hesapla ve cikar" ile ayni sey oldugunu gormektir.
La red se presenta como una matriz de adyacencia simetrica. Cada entrada es un peso entero positivo o el simbolo -, que indica que no hay arista directa. Queremos eliminar la mayor cantidad posible de peso total sin perder la conectividad entre los 40 vertices. Si \(G=(V,E,w)\) es el grafo ponderado original, la cantidad buscada es
$$\operatorname{ahorro}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
donde \(H\) recorre los subgrafos conexos que abarcan todos los vertices.
La idea central es que una red conexa optima no puede contener ciclos. Por tanto, el problema se convierte exactamente en uno de arbol de expansion minima: conservar la estructura conexa mas barata posible y restar su peso al total original.
Sea \(G=(V,E,w)\) el grafo no dirigido y ponderado obtenido de la matriz, con \(n=|V|=40\). La explicacion matematica tiene dos etapas. Primero se identifica la forma que debe tener una red minima. Despues se justifica la regla voraz que usan las implementaciones para construirla.
Supongamos que \(H\) es un subgrafo conexo que contiene todos los vertices y tiene peso total minimo. Si \(H\) contuviera un ciclo, entonces podriamos borrar cualquiera de las aristas de ese ciclo. Los vertices del ciclo seguirian conectados por las aristas restantes del mismo ciclo, asi que el grafo continuaria siendo conexo pero con menor peso total. Eso contradice la minimalidad de \(H\).
Por consiguiente, todo subgrafo conexo optimo debe ser aciclico. Un grafo conexo y aciclico con \(n\) vertices es un arbol generador, de modo que cualquier red optima tiene exactamente \(n-1\) aristas. El problema equivale entonces a
$$\text{encontrar un arbol generador }T\subseteq G\text{ que minimice }W(T).$$
Ese arbol es un arbol de expansion minima (MST), y el ahorro final vale
$$\operatorname{ahorro}=W(G)-W(T_{\min}).$$
La unicidad no importa: aunque existieran varios MST, todos tendrian el mismo peso total, asi que el ahorro queda perfectamente determinado.
Como el grafo es no dirigido, la matriz es simetrica. La arista entre \(i\) y \(j\) aparece dos veces, en \((i,j)\) y en \((j,i)\). Para no contar dos veces la misma arista, basta leer el triangulo superior con \(i<j\). Cada entrada distinta de - aporta exactamente una arista no dirigida y una sola copia de su peso.
Por eso el peso total original es
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
Esa es precisamente la suma que calculan las implementaciones antes de empezar la construccion del MST.
Ordenemos las aristas como \(e_1,e_2,\dots,e_m\) de modo que
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
El algoritmo de Kruskal recorre esa lista de menor a mayor. Una arista se acepta exactamente cuando sus extremos pertenecen a componentes conexas distintas del bosque construido hasta ese momento; si no, formaria un ciclo y se descarta.
La demostracion descansa en dos invariantes. Primero, las aristas elegidas siempre forman un bosque, porque nunca se acepta una arista que cierre un ciclo. Segundo, tras cada aceptacion sigue existiendo algun MST que contiene todas las aristas ya elegidas. Ese es el argumento de arista segura derivado de la propiedad del corte: cuando el algoritmo toma la arista mas ligera que une dos componentes actuales, esa arista tiene peso minimo entre las que cruzan el corte asociado, por lo que un MST puede modificarse para incluirla sin aumentar el peso total.
Cada arista aceptada reduce en uno el numero de componentes conexas. Empezando con \(n\) vertices aislados, despues de exactamente \(n-1\) aceptaciones obtenemos un grafo conexo y aciclico, es decir, un arbol generador. Por el segundo invariante, ese arbol tiene peso minimo posible.
La unica pregunta dinamica que Kruskal necesita contestar es si dos vertices ya estan en la misma componente. La estructura de conjuntos disjuntos almacena la particion actual del conjunto de vertices. La operacion "find" devuelve el representante de la componente de un vertice y "union" fusiona dos componentes cuando se acepta una arista segura.
Con compresion de caminos y union por rango, el costo amortizado de cada operacion es \(O(\alpha(n))\), donde \(\alpha\) es la funcion inversa de Ackermann. Para un grafo de 40 vertices, esto es esencialmente constante, asi que el costo dominante sigue siendo ordenar las aristas.
En el ejemplo de 7 vertices, leer el triangulo superior produce los 12 pesos
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31,$$
de modo que
$$W(G)=243.$$
Al procesarlos en orden creciente, Kruskal acepta
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,$$
porque cada uno de esos pesos aun conecta dos componentes distintas en el momento en que se considera. Esas seis aristas ya conectan los 7 vertices, por lo que forman un arbol generador de peso
$$W(T_{\min})=11+12+16+17+18+19=93.$$
Todas las demas aristas son redundantes porque cerrarian ciclos. El ahorro es entonces
$$243-93=150,$$
exactamente el valor citado en el enunciado y comprobado por la implementacion en C++.
Una vez conocido el MST, la salida ya no es otro objeto combinatorio, sino simplemente una diferencia:
$$\boxed{\operatorname{ahorro}=W(G)-W(T_{\min}).}$$
Toda la computacion se separa de manera natural en dos sumas: una sobre todas las aristas originales y otra sobre las \(n-1\) aristas que permanecen en el MST.
Las implementaciones en C++, Python y Java leen la matriz separada por comas fila por fila e ignoran las lineas vacias. Para la fila \(i\), solo inspeccionan las columnas \(j>i\). Si la entrada es -, no existe arista. En caso contrario, se convierte en un entero, se anade a la lista de aristas y se suma al acumulado \(W(G)\).
Ese recorrido por el triangulo superior es la traduccion directa al codigo de la observacion matematica de que cada arista no dirigida debe contarse una sola vez.
Una vez creada la lista de aristas, la implementacion la ordena por peso e inicializa una estructura de conjuntos disjuntos con una componente por vertice. Luego recorre las aristas ordenadas. Cuando una arista une dos componentes distintas, se incorpora al arbol, su peso se suma al total del MST y ambas componentes se fusionan.
Si los dos extremos ya pertenecen a la misma componente, esa arista formaria un ciclo y se ignora. La version en C++ se detiene en cuanto ha aceptado \(n-1\) aristas. Las versiones en Python y Java siguen recorriendo la lista, pero la prueba de conectividad impide sumar peso adicional una vez completado el arbol.
Al final, las tres implementaciones restan el peso del MST al peso total original. La implementacion en C++ tambien incluye la red de ejemplo de 7 vertices como comprobacion interna y verifica que el ahorro en ese caso sea \(150\) antes de resolver la instancia completa.
Sean \(n\) el numero de vertices y \(m\) el numero de aristas realmente presentes. Leer la matriz cuesta \(O(n^2)\), porque la entrada es una tabla \(n\times n\). El paso dominante de Kruskal es ordenar la lista de aristas:
$$O(m\log m).$$
Las operaciones sobre la estructura de conjuntos disjuntos aportan \(O(m\,\alpha(n))\), que es asintoticamente menor que el costo de ordenacion. El espacio usado es \(O(m+n)\): la lista de aristas almacena el grafo y la estructura disjunta mantiene un representante y una informacion de rango por vertice.
En el Problema 107, \(n=40\), y aun el grafo completo tendria solo \(40\cdot 39/2=780\) aristas. Asi que el tiempo de ejecucion es trivial; lo importante es reconocer matematicamente que "eliminar peso redundante sin perder conectividad" equivale a "calcular un MST y restarlo".
题目把网络写成一个对称的邻接矩阵。矩阵中的每个条目要么是正整数边权，要么是符号 -，表示两个顶点之间没有直接边。目标是在保持全部 40 个顶点连通的前提下，尽可能删去冗余的总权重。若把原始加权无向图记为 \(G=(V,E,w)\)，那么要求的量就是
$$\operatorname{saving}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
其中 \(H\) 在 \(G\) 的所有连通生成子图中取值。
核心观察是：最优的连通网络不可能含有回路。一旦看出这一点，题目就不再是“删边”问题，而是标准的最小生成树问题。先求出在保持连通的条件下必须保留的最小总权重，再用原图总权重减去它，就得到最大节省量。
设从矩阵中读出的加权无向图为 \(G=(V,E,w)\)，其中 \(n=|V|=40\)。这一题的数学结构很清楚：先证明所谓“最小网络”一定是一棵生成树，再证明按边权从小到大贪心地选边确实能得到权重最小的那棵生成树。
设 \(H\) 是一个覆盖全部顶点的连通子图，并且它的总权重已经最小。如果 \(H\) 中含有一个回路，那么删掉这个回路上的任意一条边之后，回路上的顶点仍然可以通过回路剩下的边彼此到达，所以整个图仍然连通；但总权重却严格变小。这与 \(H\) 已经最优相矛盾。
因此，任何最优的连通生成子图都必须无环。连通且无环的图正是一棵生成树，所以最优网络必然恰好含有 \(n-1\) 条边。题目于是等价于
$$\text{在 }G\text{ 中找一棵使 }W(T)\text{ 最小的生成树 }T.$$
这棵树就是最小生成树。设其权重为 \(W(T_{\min})\)，那么答案直接变成
$$\operatorname{saving}=W(G)-W(T_{\min}).$$
即使最小生成树不唯一也没有关系，因为所有最小生成树的总权重都相同，所以节省量是唯一确定的。
由于图是无向图，邻接矩阵是对称的。顶点 \(i\) 与 \(j\) 之间的一条边会在 \((i,j)\) 和 \((j,i)\) 位置各出现一次。为了避免重复计数，只需要读取上三角部分，也就是所有满足 \(i<j\) 的位置。凡是条目不等于 -，就表示存在一条无向边，其权重就是该整数。
所以原图总权重应写成
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
这正是三种实现先累加出来的原始网络成本。先把原图总权重算对，最后的节省量才能正确。
把所有边按权重从小到大排成 \(e_1,e_2,\dots,e_m\)，满足
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
Kruskal 算法依次扫描这张有序边表。当前边的两个端点如果属于不同的连通分量，就把这条边加入当前森林；如果已经在同一分量内，那么加入它只会形成回路，因此必须跳过。
正确性的证明建立在两个不变式上。第一，已经选中的边始终构成一片森林，因为算法从不接受会闭合回路的边。第二，每接受一条边之后，仍然存在某棵最小生成树包含目前为止所有被接受的边。这就是最小生成树理论中的“安全边”思想，本质上来自割性质：当算法选择一条连接两个当前分量的最轻边时，这条边是某个割上的最小权边，因此总可以把某棵最小生成树调整为包含它而不增加总权重。
每接受一条边，连通分量数就减少 1。开始时有 \(n\) 个孤立顶点；经过恰好 \(n-1\) 次接受后，得到的是一个连通且无环的图，也就是一棵生成树。由于第二个不变式始终成立，这棵生成树的总权重必然最小。
Kruskal 算法在执行时需要不断回答一个动态问题：当前边的两个端点是否已经属于同一个连通分量。并查集正是为这个问题服务的。它维护当前顶点集合的划分状态；“find” 返回某个顶点所在分量的代表元，“union” 在接受一条安全边后把两个分量合并。
实现里使用路径压缩和按秩合并，因此单次操作的均摊复杂度是 \(O(\alpha(n))\)，其中 \(\alpha\) 是反 Ackermann 函数。对 40 个顶点这样的规模来说，它几乎可以看成常数，所以真正主导时间的是对边进行排序。
题目给出的 7 顶点样例，只读上三角后会得到 12 条边的权重：
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31.$$
因此原图总权重为
$$W(G)=243.$$
按照从小到大的顺序运行 Kruskal，算法会接受
$$11,\ 12,\ 16,\ 17,\ 18,\ 19$$
这 6 条边，因为在它们各自被考察时，它们仍然连接着两个不同的分量。7 个顶点的生成树正好需要 6 条边，所以这时已经得到一棵生成树，其权重为
$$W(T_{\min})=11+12+16+17+18+19=93.$$
剩下的边全都会形成回路，因此都是可以删去的冗余边。于是节省量就是
$$243-93=150,$$
这与题目陈述中的样例结果一致，也和 C++ 实现里的内置校验一致。
一旦最小生成树求出，最终输出就不再是某种图结构，而只是一个数值差：
$$\boxed{\operatorname{saving}=W(G)-W(T_{\min}).}$$
因此整个计算自然分成两部分：先求原图所有边权之和，再求最小生成树上那 \(n-1\) 条保留边的总权重，最后做减法。
C++、Python 和 Java 实现都会逐行读取逗号分隔的矩阵，并忽略空行。对于第 \(i\) 行，只检查满足 \(j>i\) 的列。如果读到的是 -，说明没有边；否则就把它转成整数权重，加入边表，同时累加到原图总权重 \(W(G)\) 中。
只扫描上三角这一点非常重要，因为它直接对应“无向边只能统计一次”这一数学事实。
边表建立完成后，实现会按权重排序，并为每个顶点初始化一个独立的并查集分量。随后按排序后的顺序扫描所有边。若当前边连接了两个不同分量，就把它并入生成树，把它的权重加入 MST 总权重，并执行一次分量合并。
如果两个端点本来就在同一分量中，那么这条边只会闭合一个回路，因此直接跳过。C++ 实现会在已经接受 \(n-1\) 条边时立即停止。Python 和 Java 实现则继续扫完整个有序边表，但由于并查集检测仍在，树完成之后不会再增加任何权重。
最后，三种实现都用原图总权重减去 MST 总权重。C++ 实现还额外包含了 7 顶点样例网络作为检查点，在求解完整实例之前先验证该样例的节省量确实是 \(150\)。
设 \(n\) 是顶点数，\(m\) 是图中实际存在的边数。读取矩阵需要 \(O(n^2)\) 时间，因为输入本身就是一个 \(n\times n\) 表。Kruskal 算法中真正占主导的步骤是排序：
$$O(m\log m).$$
并查集操作一共贡献 \(O(m\,\alpha(n))\)，渐近上小于排序代价。空间复杂度是 \(O(m+n)\)：边表存储图本身，并查集为每个顶点存一个代表信息和一个秩信息。
对 Problem 107 而言，\(n=40\)，即使是完全图也只有 \(40\cdot 39/2=780\) 条边，所以程序运行几乎是瞬间完成的。真正值得说明的不是性能，而是把“在保持连通的前提下去掉冗余权重”准确识别为“求最小生成树后做一次减法”。
Сеть задана симметричной матрицей смежности. Каждый элемент матрицы либо является положительным целым весом ребра, либо символом -, означающим отсутствие прямого ребра. Нужно удалить как можно больший суммарный вес, сохранив связность всех 40 вершин. Если исходный взвешенный граф обозначить через \(G=(V,E,w)\), то искомая величина равна
$$\operatorname{saving}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
где \(H\) пробегает все связные остовные подграфы графа \(G\).
Ключевое наблюдение состоит в том, что оптимальная связная сеть не может содержать цикл. После этого задача сразу превращается в задачу о минимальном остовном дереве: нужно оставить самый дешёвый связный каркас и вычесть его вес из исходной суммы.
Пусть \(G=(V,E,w)\) — взвешенный неориентированный граф, восстановленный из матрицы, причём \(n=|V|=40\). Обоснование состоит из двух частей. Сначала нужно понять, какой объект вообще может быть оптимальной "минимальной сетью". Затем надо объяснить, почему жадное правило Краскала действительно строит этот объект.
Предположим, что \(H\) — связный остовный подграф минимального веса. Если бы в \(H\) был цикл, то можно было бы удалить любое ребро этого цикла. Остальные рёбра цикла всё равно сохраняли бы достижимость между его вершинами, поэтому граф остался бы связным, но его суммарный вес строго уменьшился бы. Это противоречит минимальности \(H\).
Значит, любой оптимальный связный остовный подграф ацикличен. Связный ацикличный граф на \(n\) вершинах — это остовное дерево, поэтому оптимальная сеть содержит ровно \(n-1\) рёбер. Следовательно, задача эквивалентна следующей:
$$\text{найти остовное дерево }T\subseteq G\text{ с минимальным }W(T).$$
Такое дерево и есть минимальное остовное дерево. После этого экономия выражается формулой
$$\operatorname{saving}=W(G)-W(T_{\min}).$$
Единственность здесь несущественна: даже если минимальных остовных деревьев несколько, их общий вес одинаков, а значит и ответ однозначен.
Поскольку граф неориентированный, матрица смежности симметрична. Ребро между вершинами \(i\) и \(j\) появляется дважды: в позициях \((i,j)\) и \((j,i)\). Чтобы не считать одно и то же ребро два раза, достаточно читать только верхний треугольник, то есть элементы с \(i<j\). Каждый элемент, отличный от -, даёт ровно одно неориентированное ребро с соответствующим весом.
Поэтому полный вес исходной сети равен
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
Именно эту величину программы накапливают до запуска построения MST.
Упорядочим рёбра как \(e_1,e_2,\dots,e_m\) по неубыванию веса:
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
Алгоритм Краскала проходит этот список слева направо. Ребро принимается тогда и только тогда, когда его концы лежат в разных компонентах связности леса, построенного к текущему моменту. Если концы уже в одной компоненте, добавление такого ребра создало бы цикл, поэтому оно отбрасывается.
Доказательство опирается на два инварианта. Во-первых, выбранные рёбра всегда образуют лес, потому что алгоритм никогда не принимает ребро, замыкающее цикл. Во-вторых, после каждого принятого ребра существует минимальное остовное дерево, содержащее все уже принятые рёбра. Это и есть утверждение о безопасном ребре, следующее из свойства разреза: когда алгоритм выбирает самое лёгкое ребро, соединяющее две текущие компоненты, оно является ребром минимального веса, пересекающим соответствующий разрез, и потому некоторое MST можно перестроить так, чтобы включить это ребро без увеличения суммарного веса.
Каждое принятое ребро уменьшает число компонент связности на единицу. Начиная с \(n\) изолированных вершин, после ровно \(n-1\) принятия получается связный ацикличный граф, то есть остовное дерево. Благодаря второму инварианту это дерево имеет минимально возможный вес.
Единственный динамический вопрос в алгоритме Краскала — находятся ли две вершины уже в одной компоненте. Структура непересекающихся множеств хранит текущее разбиение множества вершин. Операция "find" возвращает представителя компоненты вершины, а операция "union" объединяет две компоненты после принятия безопасного ребра.
Если использовать сжатие путей и объединение по рангу, амортизированная стоимость одной операции равна \(O(\alpha(n))\), где \(\alpha\) — обратная функция Аккермана. Для графа из 40 вершин это практически константа, поэтому основное время тратится на сортировку рёбер.
В примере из условия, если читать только верхний треугольник матрицы, получаем 12 весов рёбер:
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31.$$
Их сумма равна
$$W(G)=243.$$
Обрабатывая рёбра по возрастанию, алгоритм Краскала принимает
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,$$
поскольку каждое из этих рёбер в момент рассмотрения ещё соединяет две разные компоненты. Этих шести рёбер уже достаточно, чтобы соединить все 7 вершин, так что получается остовное дерево веса
$$W(T_{\min})=11+12+16+17+18+19=93.$$
Все остальные рёбра избыточны, потому что они замыкали бы цикл. Следовательно, экономия составляет
$$243-93=150,$$
что совпадает и с примером из условия, и с контрольной проверкой в реализации на C++.
После нахождения минимального остовного дерева выход задачи — это уже не новый граф, а просто разность:
$$\boxed{\operatorname{saving}=W(G)-W(T_{\min}).}$$
Поэтому всё вычисление естественным образом распадается на две суммы: сначала суммируются веса всех исходных рёбер, затем веса \(n-1\) рёбер, оставшихся в MST, после чего берётся разность.
Реализации на C++, Python и Java построчно читают матрицу, разделённую запятыми, и игнорируют пустые строки. Для строки \(i\) рассматриваются только столбцы \(j>i\). Если встречается -, ребра нет. Иначе значение преобразуется в целый вес, добавляется в список рёбер и одновременно в сумму \(W(G)\).
Такой проход только по верхнему треугольнику — это точное программное отражение математического факта, что каждое неориентированное ребро нужно учитывать ровно один раз.
После формирования списка рёбер программа сортирует его по весу и создаёт по одной компоненте disjoint-set для каждой вершины. Затем она проходит по отсортированным рёбрам. Если очередное ребро соединяет две разные компоненты, оно включается в дерево, его вес прибавляется к сумме MST, а компоненты объединяются.
Если концы ребра уже лежат в одной компоненте, это ребро замкнуло бы цикл, поэтому его игнорируют. Реализация на C++ прекращает работу, как только принято \(n-1\) рёбер. Реализации на Python и Java продолжают просмотр до конца списка, но проверка компонент гарантирует, что после завершения дерева никакой дополнительный вес уже не добавится.
В конце все три реализации вычитают вес MST из исходного общего веса. Реализация на C++ дополнительно содержит примерную сеть из 7 вершин как контрольную точку и перед решением полной задачи проверяет, что для неё получается значение \(150\).
Пусть \(n\) — число вершин, а \(m\) — число реально существующих рёбер. Разбор матрицы стоит \(O(n^2)\), поскольку вход имеет вид таблицы \(n\times n\). Главный шаг в алгоритме Краскала — сортировка списка рёбер:
$$O(m\log m).$$
Операции disjoint-set дают вклад \(O(m\,\alpha(n))\), который асимптотически меньше стоимости сортировки. Память составляет \(O(m+n)\): список рёбер хранит граф, а структура множеств хранит по одному представителю и одному рангу на вершину.
В задаче 107 конкретно \(n=40\), и даже полный граф содержит лишь \(40\cdot 39/2=780\) рёбер. Поэтому программа работает очень быстро; важна не производительность как таковая, а корректная математическая редукция от "удалить лишний вес, не потеряв связность" к "найти MST и вычесть его вес".
تُعطى الشبكة على هيئة مصفوفة تجاور متناظرة. كل خانة فيها إما وزن صحيح موجب لحافة، أو الرمز - الذي يعني عدم وجود حافة مباشرة. المطلوب هو حذف أكبر قدر ممكن من الوزن الكلي مع الإبقاء على اتصال جميع الرؤوس الأربعين. إذا رمزنا إلى البيان الأصلي الموزون غير الموجه بـ \(G=(V,E,w)\)، فإن الكمية المطلوبة هي
$$\operatorname{saving}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$
حيث يمر \(H\) على جميع الرسوم الجزئية المولدة المتصلة داخل \(G\).
الفكرة الحاسمة هي أن أي شبكة مثلى تحافظ على الاتصال لا يمكن أن تحتوي دورة. وبمجرد فهم ذلك تتحول المسألة مباشرة إلى مسألة شجرة توليد صغرى: نحتفظ بأرخص هيكل متصل ممكن ثم نطرح وزنه من الوزن الأصلي للشبكة.
لنكتب البيان الموزون غير الموجه المستخرج من المصفوفة على صورة \(G=(V,E,w)\)، مع \(n=|V|=40\). البرهان يتكون من جزأين. أولاً نحدد الشكل الذي يجب أن تبدو عليه "الشبكة الدنيا" في الحل الأمثل. ثم نبرر لماذا تعطي القاعدة الجشعة في خوارزمية كروسكال هذا الشكل بالضبط.
افترض أن \(H\) رسم جزئي متصل ويشمل جميع الرؤوس وله أقل وزن ممكن. لو احتوى \(H\) على دورة، لأمكن حذف أي حافة من تلك الدورة من غير أن ينقطع الاتصال، لأن بقية حواف الدورة ما زالت تؤمن طريقاً بين رؤوسها. عندئذ يبقى الرسم متصلاً ولكن بوزن أصغر، وهذا يناقض فرضية المثالية.
إذن كل رسم جزئي متصل أمثل لا بد أن يكون خالياً من الدورات. والرسم المتصل الخالي من الدورات على \(n\) رأساً هو شجرة توليد، ولذلك فإن الشبكة المثلى تحتوي بالضبط على \(n-1\) حافة. وهكذا تصبح المسألة مسألة تصغير صريحة لوزن شجرة توليد:
$$W(T_{\min})=\min_{T\in\mathcal{T}(G)} W(T),$$
حيث \(\mathcal{T}(G)\) هي مجموعة جميع أشجار التوليد في \(G\).
وهذه هي شجرة التوليد الصغرى. بعد إيجاد وزنها \(W(T_{\min})\)، يكون مقدار التوفير
$$\operatorname{saving}=W(G)-W(T_{\min}).$$
ولا تهم مسألة الفرادة هنا؛ حتى لو وُجدت عدة أشجار توليد صغرى، فإن أوزانها الكلية متساوية، وبالتالي تكون قيمة التوفير محددة تحديداً وحيداً.
بما أن البيان غير موجه، فمصفوفة التجاور متناظرة. الحافة بين الرأسين \(i\) و\(j\) تظهر مرتين: في الموضع \((i,j)\) وفي الموضع \((j,i)\). لتجنب العد المزدوج، يكفي أن نقرأ المثلث العلوي فقط، أي كل المواضع التي تحقق \(i<j\). وكل قيمة تختلف عن - تمثل حافة غير موجهة واحدة مع نسخة واحدة من وزنها.
لذلك يكون الوزن الكلي الأصلي
$$W(G)=\sum_{0\le i<j<n,\ a_{ij}\ne \text{-}} a_{ij}.$$
وهذا بالضبط هو المجموع الذي تجمعه التطبيقات قبل أن تبدأ باختيار حواف شجرة التوليد الصغرى.
رتب الحواف على صورة \(e_1,e_2,\dots,e_m\) بحيث
$$w(e_1)\le w(e_2)\le \cdots \le w(e_m).$$
تمر خوارزمية كروسكال على هذه القائمة من الأصغر إلى الأكبر. وتُقبل الحافة إذا كان طرفاها يقعان في مكونين متصلين مختلفين في الغابة المبنية حتى تلك اللحظة، أما إذا كانا في المكون نفسه فإن إضافتها ستنشئ دورة، ولذلك تُهمل.
تعتمد الصحة على ثابتين أساسيين. الأول أن الحواف المقبولة تشكل دائماً غابة، لأن الخوارزمية لا تقبل أي حافة تغلق دورة. والثاني أنه بعد كل قبول تبقى هناك شجرة توليد صغرى تحتوي جميع الحواف المقبولة حتى الآن. هذه هي فكرة "الحافة الآمنة" الناتجة من خاصية القطع: عندما تختار الخوارزمية أخف حافة تصل بين مكونين حاليين، فإنها تكون حافة ذات وزن أصغري تعبر قطعاً مناسباً، ولذلك يمكن تعديل شجرة توليد صغرى لتشملها من دون زيادة الوزن الكلي.
كل حافة مقبولة تُنقص عدد المكونات المتصلة بمقدار واحد. نبدأ من \(n\) رؤوس معزولة؛ وبعد قبول \(n-1\) حافة بالضبط نحصل على رسم متصل وخال من الدورات، أي على شجرة توليد. وبفضل الثابت الثاني نعلم أن وزن هذه الشجرة هو الأدنى الممكن.
السؤال الديناميكي الوحيد الذي تحتاج إليه خوارزمية كروسكال هو: هل يقع رأسا الحافة الحالية في المكون نفسه أم لا؟ بنية المجموعات المنفصلة تخزن التقسيم الحالي لمجموعة الرؤوس. العملية "find" تعيد ممثل المكون الذي ينتمي إليه رأس ما، بينما تدمج العملية "union" مكونين عندما تُقبل حافة آمنة.
مع ضغط المسارات والدمج حسب الرتبة، تصبح الكلفة المتوسطة لكل عملية \(O(\alpha(n))\)، حيث \(\alpha\) هي دالة آكرمان العكسية. وعند حجم مثل \(40\) رأساً يمكن اعتبار هذه الكلفة ثابتة عملياً، ولذلك يبقى فرز الحواف هو الخطوة المهيمنة زمنياً.
في المثال ذي الرؤوس السبعة، يعطينا قراءة المثلث العلوي أوزان الحواف الاثني عشر التالية:
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,\ 20,\ 21,\ 23,\ 27,\ 28,\ 31.$$
ومن ثم يكون الوزن الكلي الأصلي
$$W(G)=243.$$
وعند تطبيق كروسكال تصاعدياً، تُقبل الأوزان
$$11,\ 12,\ 16,\ 17,\ 18,\ 19,$$
لأن كل واحدة منها تصل بين مكونين مختلفين لحظة النظر فيها. وهذه الحواف الست تكفي لربط الرؤوس السبعة جميعاً، فتشكل شجرة توليد وزنها
$$W(T_{\min})=11+12+16+17+18+19=93.$$
أما بقية الحواف فكلها زائدة لأنها ستغلق دورات. ولذلك يكون مقدار التوفير
$$243-93=150,$$
وهو تماماً الرقم المذكور في المثال داخل نص المسألة والمتحقق منه في تطبيق ++C.
بعد العثور على شجرة التوليد الصغرى، لا يبقى لدينا كائن بياني جديد نحسبه، بل مجرد فرق عددي:
$$\boxed{\operatorname{saving}=W(G)-W(T_{\min}).}$$
ولهذا ينقسم الحساب طبيعياً إلى مجموعين: مجموع أوزان جميع حواف الشبكة الأصلية، ومجموع أوزان الحواف \(n-1\) التي تبقى داخل شجرة التوليد الصغرى، ثم نأخذ الفرق بينهما.
تقرأ تطبيقات C++ وPython وJava المصفوفة المفصولة بفواصل سطراً سطراً، وتتجاهل السطور الفارغة. وبالنسبة إلى السطر \(i\)، فهي تفحص فقط الأعمدة التي تحقق \(j>i\). إذا كانت القيمة - فلا توجد حافة، وإلا تُحوَّل القيمة إلى عدد صحيح وتُضاف إلى قائمة الحواف وإلى المجموع الجاري \(W(G)\).
هذا المرور على المثلث العلوي وحده هو الترجمة البرمجية المباشرة للملاحظة الرياضية القائلة إن كل حافة غير موجهة يجب أن تُحسب مرة واحدة فقط.
بعد استخراج قائمة الحواف، ترتبها التطبيقات حسب الوزن، ثم تهيئ بنية مجموعات منفصلة يكون فيها كل رأس مكوناً مستقلاً في البداية. بعد ذلك تُفحص الحواف المرتبة واحدة تلو الأخرى. إذا كانت الحافة تصل بين مكونين مختلفين، فإنها تُضم إلى الشجرة ويُضاف وزنها إلى مجموع MST وتُدمج المكونات.
أما إذا كان الطرفان في المكون نفسه، فستنشئ الحافة دورة ولذلك تُترك. تطبيق ++C يتوقف فور قبول \(n-1\) حافة. أما تطبيقا Python وJava فيكملان المرور حتى نهاية القائمة، لكن اختبار المكونات يمنع إضافة أي وزن جديد بعد اكتمال الشجرة.
في النهاية تطرح التطبيقات الثلاثة وزن MST من الوزن الكلي الأصلي. ويحتوي تطبيق ++C أيضاً على شبكة المثال ذات الرؤوس السبعة كنقطة فحص داخلية، ويتأكد أولاً من أن مقدار التوفير فيها يساوي \(150\) قبل حل الحالة الكاملة.
ليكن \(n\) عدد الرؤوس و\(m\) عدد الحواف الموجودة فعلاً في الشبكة. قراءة المصفوفة تكلف \(O(n^2)\) لأن المدخل نفسه جدول \(n\times n\). أما الخطوة المهيمنة في خوارزمية كروسكال فهي فرز قائمة الحواف:
$$O(m\log m).$$
وتضيف عمليات بنية المجموعات المنفصلة مقدار \(O(m\,\alpha(n))\)، وهو أصغر تقاربياً من كلفة الفرز. أما الذاكرة المستعملة فهي \(O(m+n)\): قائمة الحواف تخزن البيان، وبنية المجموعات المنفصلة تخزن ممثلاً ورتبة تقريبية لكل رأس.
في Problem 107 لدينا \(n=40\)، وحتى لو كان البيان كاملاً فلن يتجاوز عدد الحواف \(40\cdot 39/2=780\). لذلك فالبرنامج سريع جداً عملياً؛ المهم رياضياً هو إدراك أن عبارة "احذف الوزن الزائد مع الحفاظ على الاتصال" تعني بالضبط "احسب شجرة توليد صغرى ثم اطرح وزنها".