A fa minimális súlya

A gráfelméletben , egy összekapcsolt, irányítatlan gráf alapján, amelynek élei súlyozottak, ennek a grafikonnak a legkisebb súlyát átfogó fája ( MCA ) egy átfogó fa ( egy részhalmaz, amely egy fa, és amely az összes csúcsot összeköti), amelynek az élek súlyának összege minimális (vagyis súlya kisebb vagy egyenlő, mint a grafikon összes többi átnyúló fájának súlya). A minimális súlyt átfogó fa bizonyos más nevekkel is ismert, például a minimális átfogó fa vagy az alatta lévő fa minimuma .

A minimális átfogó fa különböző módon értelmezhető attól függően, hogy a grafikon mit ábrázol. Általánosságban, ha figyelembe vesszük egy olyan hálózatot, ahol egy objektumkészletet össze kell kapcsolni (például egy elektromos hálózatot és házakat), akkor a minimális takarófa az ilyen hálózat kiépítésének módja, miközben minimalizálja az élsúly által képviselt költségeket (pl. az elektromos hálózat kiépítéséhez használt kábel teljes hossza).

Tulajdonságok

Sokaság vagy egyediség

Amint az a szemközti ábrán látható, egy összekapcsolt gráfnak több különböző minimális átfedő fája lehet, de ha az összes tömeg különbözik, akkor egyedi. Irányítatlan és általános grafikonon átfedő erdő minimális súlyú .

A ciklusok és vágások tulajdonságai

A grafikon bármely ciklusánál , ha egy él szigorúan nagyobb súlyú, mint a többi, akkor ez az él nincs a minimális súlyú átfogó fában. Más szavakkal, a gráf bármely élének (u, v) súlya nagyobb, vagy egyenlő a fán az u-val és v-vel összekötő maximális tömeg szélével .

Ha a gráf bármely részénél egy él súlya szigorúan kisebb, mint a többi, akkor ez a minimális súlyú fához tartozik.

Egy pontkészlet tengelyének súlya

Klasszikus probléma az, ha az euklideszi normával összhangban egy sor pontot megtudunk, mi a súlya a minimális átívelő fának. Átlag nagyságrendű és 1 valószínűséggel. ${\ mathbb {R}} ^ {d}$ $n ^ {\ frac {d-1} {d}}$

Algoritmikus szempontok

Klasszikus algoritmusok

Sok algoritmus létezik egy minimális súlyú átfogó fa létrehozására. Például a Borůvka algoritmus (először kitalálta erre a problémára a algoritmust ), a Prim algoritmus és Kruskal algoritmusa . Ezek az algoritmusok mind kapzsi algoritmusok .

Gyors algoritmusok

Gyorsabb és összetettebb algoritmus Bernard Chazelle-nek köszönhető . A komplexitás szinte lineáris.

Vannak lineáris időalgoritmusok néhány speciális esetre, például sűrű grafikonokra . Valószínűségi algoritmussal elérhetünk egy lineáris időt is .

Ellenőrzési algoritmus

Van egy lineáris időalgoritmus, amely egy átfogó fára tekintettel ellenőrzi, hogy minimális súlyú-e.

Alkalmazások

A fákat többféle hálózatban használják, például telefonhálózatokban és terjesztési hálózatokban . A hálózatok kontextusán kívül hasznosak például az adatok particionálásához és a képfeldolgozáshoz .

Más algoritmusok egy minimális súlyú fát számolnak. Például a Christofides algoritmus kiszámít egy minimális súlyú fát, hogy közelítse az utazó eladó problémáját a metrikus esetben.

Változatok és kapcsolódó tárgyak

Meghatározhatjuk a minimális átívelő fa probléma különféle változatait, például a grafikon geometriai beágyazását, vagy dinamikus, elosztott modellel stb. Kapcsolódó probléma a Steiner-fa probléma .

Megjegyzések és hivatkozások

Jillian Beardwood, John H Halton és John Michael Hammersley, „ A legrövidebb út sok ponton keresztül ”, Matematikai Proceedings of the Cambridge Philosophical Society , Cambridge University Press , vol. 55, n o 04, 1959, P. 299-327
Bernard Chazelle , „ Minimális átívelő fa algoritmus inverz-ackermann típusú komplexitással ”, Journal of the ACM , vol. 47, n o 6, 2000, P. 1028-1047.
Michael L. Fredman és Robert Endre Tarjan , „ Fibonacci-halmok és felhasználásuk a továbbfejlesztett hálózatoptimalizáló algoritmusokban ”, Journal of the ACM , vol. 34, n o 3, 1987, P. 596-615.
David R. Karger , Philip N. Klein és Robert Endre Tarjan , „ Randomizált lineáris időbeli algoritmus a minimális fák megtalálásához ”, Journal of the ACM , vol. 42, n o 2 1995, P. 321-328 ( DOI 10,1145 / 201.019,201022 )
(in) Valerie King , " Egy egyszerűbb minimális átfogó fa algoritmus-ellenőrzés " , Algorithmica , vol. 18, n o 2 1997, P. 263-270
Valerie King által bemutatott minimális átfogó fa igazolás lineáris idő komplexitás módszerrel
R. L. Graham és Pavol Hell , „ A minimum átívelő fa problémájának történetéről ”, Annals of the History of Computing , vol. 7, n o 1,1985, P. 43–57 ( DOI 10.1109 / MAHC.1985.10011 , Math Reviews 783327 )

(fr) Ez a cikk részben vagy egészben az angol Wikipedia " Minimum spanning tree " című cikkéből származik ( lásd a szerzők felsorolását ) .

Bibliográfia

Cikkek

(en) Jaroslav Nesetril, Eva Milková et Helena Nesetrilová, Otakar Boruvka on Minimum Spanning Tree Problem , 2000 (Mindkét 1926-os cikk, kommentár, történelem fordítása; A 7. szakasz megadja algoritmusát, amely Prim és Kruskal keresztezésének tűnik.)
(en) [PDF] James Allen Fill és J. Michael Steele, A minimális átfedő fák pontos elvárásai véletlenszerű élsúlyú gráfokhoz , 2004

Művek

(en) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmusokba , az MIT Press és a McGraw-Hill ,2001, 2 nd ed. [ a kiadás részlete ], fej. 23: minimális feszítőfa, p. 561–579

Külső linkek

Jason Eisner, „ Korszerű algoritmusok a minimális átívelő fákhoz: A bemutató vita ” , a Pennsylvaniai Egyetemen ,1997