minimum spanning tree problem

minimum spanning tree problem (tsz. minimum spanning tree problems)

1. (informatika) A Minimum Spanning Tree (MST) Problem egy alapvető gráfelméleti optimalizációs feladat: adott egy összefüggő, súlyozott, egyszerű, nem irányított gráf, keressük azt az élsorozatot (feszítőfát), amely lefedi az összes csúcsot, összesített él­súlya (költsége) pedig minimális.

• Bemenet:
  • Egy gráf ${\textstyle G=(V,E)}$, ahol ${\textstyle |V|=n}$, ${\textstyle |E|=m}$.
  • Minden élhez ${\textstyle w:E\to \mathbb {R} }$ súly (költség) van rendelve.
  • ${\textstyle G}$ összefüggő, nincs irány, párhuzamos él vagy hurok.
• Kimenet: Egy részhalmaz ${\textstyle T\subseteq E}$ úgy, hogy
  1. ${\textstyle (V,T)}$ feszítőfa (spanning tree), azaz összefüggő és ${\textstyle |T|=n-1}$.
  2. ${\textstyle \sum _{e\in T}w(e)}$ minimális az összes lehetséges feszítőfára vetítve.

1. Cut Property Egy gráf bármely vágásán (vertex-partícióján) belül a legkisebb súlyú él biztosan része valamilyen MST-nek.
2. Cycle Property Egy gráf bármelyik körében a legnagyobb súlyú él nem lehet benne semelyik MST-ben.

Ezek a tulajdonságok igazolják a klasszikus „greedy” algoritmusok helyességét.

1. Rendezés: Rendezd az éleket növekvő súly szerint.
2. Élek válogatása: Kezdetben az MST üres, majd iterálsz a legkisebb súlyú él­től felfelé: ha a két végpont még külön komponensben van (DSU-val ellenőrizve), vedd be az MST-be és egyesítsd a komponenseket.
3. Befejezés: Amikor már ${\textstyle n-1}$ élt felvettél, kész az MST.

• Futásidő: ${\textstyle O(m\log m+m\,\alpha (n))\approx O(m\log n)}$ (DSU-op­erációk szinte konstans).

1. Kezdet: Válassz egy tetszőleges kezdőcsúcsot, jelöld meg feszítettként.
2. Bővítés: Minden lépésben válaszd ki a kitevett és a még nem feszített csúcsok között a legkisebb súlyú él­t, vedd fel az MST-be, és jelöld új csúcsodat feszítettnek.
3. Adatszerkezet: Használj min-prioritás­sorozatot (bináris kupac, Fibonacci-kupac), hogy megtaláld a következő minimális élt.

• Futásidő:
  • Kupaccal: ${\textstyle O(m\log n)}$.
  • Fibonacci-heap­pel: ${\textstyle O(m+n\log n)}$.

Több lépésben minden komponenshez egyszerre választjuk a bennük legkisebb kimenő élt, majd egyesítjük a komponenseket. Végtére is ${\textstyle \log n}$ lépés alatt összeolvadnak egyetlen fává.

• Futásidő: ${\textstyle O(m\log n)}$.

• Disjoint Set Union (DSU) vagy Union–Find: hatékonyan kezeli a komponens­egyesítést és lekérdezést.
• Adatszerkezetek Prim-hoz:
  • Bináris kupac: egyszerű, ${\textstyle O(m\log n)}$.
  • Fibonacci-kupac: amortizált ${\textstyle O(m+n\log n)}$, de bonyolultabb.

1. Hálózattervezés (villamos-, telekommunikációs hálózatok), ahol minimális költséggel kell összekötni csomópontokat.
2. Klaszterezés (single-linkage clustering): MST-ből szétszedéssel hierarchikus klaszterek.
3. Képfeldolgozás: szeg­mentálás, ahol élek súlya pixel-különbség.
4. Univerzális hasonlóságfa (phylogenetic tree) építése biológiai adatokból.

• A Minimum Spanning Tree Problem gyors, hatékony, polinomiális idejű (tractable) megoldásokat engedő példa a kombinatorikus optimalizációban.
• Három fő greedy algoritmusa (Kruskal, Prim, Borůvka) ${\textstyle O(m\log n)}$ komplexitással fut.
• Alkalmazása számos mérnöki és tudományos területen elterjedt, mivel minimalizálja a kapcsolatok vagy utak összköltségét egy összefüggő hálózatban.

• minimum spanning tree problem - Szótár.net (en-hu)
• minimum spanning tree problem - Sztaki (en-hu)
• minimum spanning tree problem - Merriam–Webster
• minimum spanning tree problem - Cambridge
• minimum spanning tree problem - WordNet
• minimum spanning tree problem - Яндекс (en-ru)
• minimum spanning tree problem - Google (en-hu)
• minimum spanning tree problem - Wikidata
• minimum spanning tree problem - Wikipédia (angol)