spanning tree

Angol

Főnév

spanning tree (tsz. spanning trees)

(informatika) feszítőfa

A spanning tree (magyarul: feszítőfa) egy olyan alapvető fogalom a gráfelméletben, amely fontos szerepet játszik hálózatok, útvonalak, kommunikációs rendszerek, és algoritmusok tervezésében. A spanning tree segítségével egy összefüggő, irányítatlan gráfból kiválaszthatunk egy minimális élhalmazt, amely összeköti az összes csúcsot, de nem tartalmaz ciklusokat.

1. Mi az a spanning tree?

Egy adott összefüggő, irányítatlan gráf ${\textstyle G=(V,E)}$ feszítőfája egy olyan részgráf, amely:

Tartalmazza az összes csúcsot ( ${\textstyle V}$ )
Összefüggő (minden csúcs elérhető a többiből)
Fa (nincsenek benne ciklusok)
${\textstyle |V|-1}$ élből áll

Ez azt jelenti, hogy a spanning tree minimálisan összeköti az összes csúcsot, épp elég éllel ahhoz, hogy minden pont elérhető legyen.

2. Példa

Tegyük fel, hogy van egy gráf 4 csúccsal:

   A —— B
   |   / |
   |  /  |
   C —— D

Ez a gráf több kört (ciklust) is tartalmaz. A lehetséges spanning tree-k közül egy:

   A —— B
   |
   C —— D

Itt minden csúcs elérhető, és pontosan 3 él van (4 csúcs – 1).

3. Miért fontos?

A spanning tree alkalmazása számos helyen kulcsfontosságú:

Hálózattervezés – minimális költségen akarjuk összekötni a gépeket
Kábelezés – nincs szükség fölösleges vezetékekre
Kommunikáció – nincs visszacsatolási hurok
Fájlstruktúrák, keresőfák
Routing protokollok – pl. Spanning Tree Protocol (STP) az Ethernet hálózatokban

4. Minimum Spanning Tree (MST)

Ha a gráf éleihez súlyokat rendelünk (pl. távolság, költség), akkor a minimum spanning tree az a spanning tree, amelyben az élek összsúlya minimális.

Formálisan:

Legyen ${\textstyle G=(V,E)}$ , minden élhez tartozik egy ${\textstyle w(e)}$ súly. A minimum spanning tree az a fa ${\textstyle T\subseteq E}$ , amelyre:

$\sum _{e\in T}w(e){\text{ minimális}}$

5. Minimum Spanning Tree algoritmusok

Két klasszikus algoritmus van MST keresésére:

a) Kruskal algoritmusa

Az éleket súly szerint növekvő sorrendbe rendezi
Felveszi a legkisebb súlyú élt, ha nem okoz ciklust
Addig folytatja, míg ${\textstyle |V|-1}$ élt nem tartalmaz

b) Prim algoritmusa

Egy kiválasztott kezdőcsúcsból indul
Mindig a legkisebb súlyú élt veszi fel, amely összeköt egy meglévő csúcsot egy újjal

6. Kruskal algoritmus – C++ példa

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int u, v;
    int weight;
    bool operator<(const Edge& e) const {
        return weight < e.weight;
    }
};

std::vector<int> parent;

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

bool unite(int a, int b) {
    int rootA = find(a), rootB = find(b);
    if (rootA == rootB) return false;
    parent[rootB] = rootA;
    return true;
}

int kruskal(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end());
    parent.resize(n);
    for (int i = 0; i < n; ++i) parent[i] = i;

    int totalWeight = 0;
    for (Edge e : edges) {
        if (unite(e.u, e.v)) {
            totalWeight += e.weight;
            std::cout << e.u << " -- " << e.v << " (" << e.weight << ")\n";
        }
    }
    return totalWeight;
}

int main() {
    int n = 4; // csúcsok száma (0-3)
    std::vector<Edge> edges = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
    };

    int minCost = kruskal(n, edges);
    std::cout << "Minimum spanning tree összköltsége: " << minCost << "\n";

    return 0;
}

7. Tulajdonságok

Egy gráfnak több spanning fája lehet
Az MST nem feltétlenül egyértelmű
Minden MST egy spanning tree, de nem minden spanning tree minimális
Egy összefüggő gráfnak mindig van spanning tree-je

8. Spanning Tree Protocol (STP)

Az Ethernet-hálózatokban a Spanning Tree Protocol megakadályozza a hurok kialakulását. Az STP automatikusan kialakít egy spanning tree-t a kapcsolók között, és blokkolja azokat a kapcsolatokat, amelyek hurkot okoznának.

9. Felhasználási területek

Hálózattervezés (telekommunikáció, áramkörök, városi infrastruktúra)
Térinformatika (pl. útvonalhálózat optimalizálása)
Játékkészítés (pl. labirintusgenerálás)
Tömörítés (pl. Huffman-fák egyfajta súlyozott fák)

10. Összefoglalás

A spanning tree:

Egy összefüggő gráf minimális részhalmaza, amely még mindig összefüggő
Nem tartalmaz ciklusokat
Segítségével hatékonyan összeköthető minden csúcs minimális élkészlettel
Ha súlyozott gráfról van szó, akkor a minimum spanning tree biztosítja a legolcsóbb lefedést

A spanning tree egy alapvető fogalom, amelynek megértése elengedhetetlen a hálózatelmélet, kombinatorika, algoritmuselmélet és informatikai rendszerek területén.

További információk

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