Építése a minimális feszítőfa (MST)

1. Nyilatkozat a probléma

Legyen egy csatlakoztatott irányítatlan gráf [matematikai] G = (V, E) [/ matematikai] súlyokkal élek [matematikai] f (e) [/ Math]. Részgráf, amely egy fa és áthaladó összes csúcsot [matematikai] G [/ Math]. Ez az úgynevezett elsődleges fa. Feszítőfának hívják minimális. ha a teljes súlya a élek minimális között átívelő fák.

2 változat a probléma

Ha az eredeti gráf [matematikai] G [/ Math] megszakad, a beállított minimális feszítőfa összes csatlakoztatott komponensek nevezzük minimális átívelő erdő (Minimális Spanning Forest, MSF).

Egy grafikont egész súlyokkal lehet használni speciális technikák, mint például a Radix rendezési. ami egy algoritmus a probléma megoldásának a lineáris időben.

Egy elosztott problémát jelenthet egy további követelmény, hogy az adatcsere zajlik csak szélei mentén a grafikonon.

3. Feladat tulajdonságok

Tömeg. Megoldás nem függ az értékrend, és azok sorrendjét. Így ahelyett, hogy a súlyok állítható hozzárendelés érdekében - predikátum „kisebb vagy egyenlő” a párok halmaza élek a grafikon. Emiatt lehetséges, az általánosság elvesztése nélkül, feltételezzük, hogy minden a súlya a szélei más - meg kell ésszerűsíteni élek először súly szerint, majd a számot. Amellett, hogy a kezdeti súlyokat lehet alkalmazni bármilyen növekvő függvénye, és nem vezet a döntés megváltoztatására. Ennek következtében, feltételezhetjük, hogy minden súly egy előre meghatározott tartományban, például, [matematikai] [0, 1] [/ Math].

A létezése és egyedisége. Minimális támogatás erdő mindig ott van, és ha az összes súly élek eltérnek egymástól, akkor ez egyedülálló. Mint már említettük, ez mindig lehetséges, hogy a különböző súlyú élek. Ha ez az állapot különböző súlyú nem teljesül, akkor könnyű építeni egy példát, amelyben nem lesz több, mint a minimális feszítőfa.

A összeomlása a fragmentumok. Legyen [matematikai] F [/ Math] - fragmens a minimális feszítőfa a gráf [matematikai] G [/ Math]. és a számlálási [matematikai] G „[/ Math] kapott [matematikai] G [/ matematikai] ragasztás csúcsok tartozó [matematikai] F [/ Math]. Ezután a szakszervezet [matematikai] F [/ math], valamint a minimális feszítőfa gráf [math] G „[/ math] megadja a minimális feszítőfa gráf kiindulási [math] G [/ math].

Minimális szélén fragmens. Legyen [matematikai] F [/ Math] - molekularészt és egy minimális feszítőfa [matematikai] e_F [/ Math] - borda legalább tömeg származó [matematikai] F [/ Math] (azaz pontosan egy vége van a csúcsa a [matematikai] F [/ Math]). Ha a széle [matematikai] e_F [/ math] egyedi, akkor tartozik a minimális feszítőfa. Az ingatlan alapú algoritmus és egy algoritmus Borůvka Prima.

Minimális széle a grafikon. Ha a [math] e ^ * [/ math] - csak egy él minimális súlyt, hogy tartozik a minimális feszítőfa. Az ingatlan alapú algoritmus Kruskal.

Asszociativitás a bordák. Hagyja [matematika] MSF (E) [/ math] - minimális átívelő erdő a gráf élei [math] E [/ math]. majd

[Math] MSF (E_1 \ cup E_2 \ cup \ dots \ cup E_k) = MSF (MSF (E_1) \ cup MSF (E_2) \ cup \ dots \ cup MSF (E_k)). [/ Math]

A bordák száma átívelő erdőben a gráfot [matematikai] N [/ matematikai] csúcsok és [matematikai] c [/ matematikai] csatlakoztatott komponensek egyenlő [matematikai] n-C [/ Math]. Ez a tulajdonság lehet használni a gyorsabb befejezését algoritmusok ha a szám a csatlakoztatott komponensek előre ismert.

4 Leírás bemeneti és kimeneti adatok

Bemenet. súlyozott gráf [matematikai] (V, E, W) [/ matematikai] ([matematikai] N [/ matematikai] csúcsok [matematikai] v_i [/ ​​matematikai] és [matematikai] m [/ matematikai] borda [matematikai] e_j = ( v ^ _, v ^ _) [/ matematikai] súlyokkal [matematikai] f_j [/ Math]).

A kötet a bemeneti adatokat. [Math] O (m + n) [/ Math].

Nyomot. listája élek egy minimális feszítőfa (a leválasztott gráf - egy listát a minimális feszítőfa az összes csatlakoztatott komponensek).

Termelés volumene az adatokat. [Math] O (n) [/ Math].

5 algoritmusok a probléma megoldására

Három klasszikus megközelítés a probléma megoldásának:

Minden esetben összhangban komplexitása algoritmust [matematikai] O (m \ ln m) [/ matematikai] állíthatjuk elő hagyományos adatstruktúrák. (Jelmagyarázat: [matematikai] m [/ matematikai] - élek számát, [matematikai] N [/ Math] - a csúcsok számát.)

Minden más algoritmusok általában egy változata a három felsorolt, vagy ezek kombinációja.

• GHS algoritmus (Gallager, Humblet, Spira) [6] és annak későbbi változatai [7] [8] vannak elosztva egy Borůvka algoritmus. Ez az algoritmus általánosan használt automatikusan elosztani feszítőfának hálózati kapcsolók.
• Algoritmus Gabova et al. [9] alkalmazásra halom Fibonacci rendelési élek Borůvka algoritmus. A komplexitás [matematikai] O (m \ ln \ beta (m, n)) [/ Math].
• Fredmana és Willard algoritmust [10] gráfokra egész súlyok és lineáris becslés komplexitás [matematikai] O (m) [/ Math]. Prim algoritmus együtt használják egy speciálisan kialakított halom algoritmus (AF-kupac).
• Algoritmus Karger et al. [11] megoldja az átlagos lineáris idő [matematikai] O (m) [/ Math]. (Létezése determinisztikus algoritmus lineáris komplexitás kötött, még nyitott kérdés.)

Meg kell jegyezni, hogy az algoritmusok aszimptotikus összetettsége jobb, mint [matematikai] O (m \ ln n) [/ Math]. általában a gyakorlatban lassabb klasszikus algoritmusok állandó az értékelés olyan nagy, hogy az erősítés aszimptotikus viselkedését a legjobb lesz látható, csak nagyon nagy gráfok.

6 Forrás párhuzamosság

1. Tulajdonságok összeomlása fragmensek és minimális fragmensei bordák lehetővé teszik önállóan feldolgozzák fragmensek. Ennek alapján ezek a tulajdonságok, az algoritmus a legnagyobb erőforrás Borůvka párhuzamosság a három klasszikus algoritmusok.
2. Asszociativitás a bordák lehet használni, hogy összevessünk algoritmusok és Kruskal Prima, amely kezdetben alapvetően megegyeznek.
3. Egy párhuzamos rendezési algoritmusok széleit a grafikon, vagy egy párhuzamos válogató élek minden csúcs vagy minden egyes fragmentum.