• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Minimalne drzewo rozpinające

    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.
    Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

    Minimalne drzewo rozpinające (ang. MST, minimum spanning tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.

    Definicja formalna[]

    Dany jest graf ważony G(V, E, w), gdzie V – zbiór wierzchołków, E – zbiór krawędzi, w – funkcja przypisująca krawędzi Ei wagę (liczbę rzeczywistą lub całkowitą).

    Minimalnym drzewem rozpinającym nazywamy drzewo rozpinające T, dla którego suma wag

    Funkcja (łac. functio, -onis, „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.Zbiór liczb rzeczywistych – uzupełnienie zbioru liczb wymiernych. Zbiór liczb rzeczywistych zawiera m.in. liczby naturalne, ujemne, całkowite, pierwiastki liczb dodatnich, wymierne, niewymierne, przestępne, itd. Z drugiej strony na liczby rzeczywiste można też patrzeć jak na szczególne przypadki liczb zespolonych.

    jest najmniejsza z możliwych. Dla niektórych grafów można wskazać wiele drzew rozpinających spełniających tę własność.

    Algorytm Borůvki wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu.

    Istnieją trzy deterministyczne algorytmy o złożoności liniowo-logarytmicznej znajdujące dla zadanego grafu minimalne drzewo rozpinające. Są to:

  • algorytm Borůvki (błędnie nazywany algorytmem Sollina),
  • algorytm Prima (nazywany też algorytmem Dijkstry-Prima),
  • algorytm Kruskala.
  • (window.RLQ=window.RLQ||).push(function(){mw.log.warn("Gadget \"edit-summary-warning\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"wikibugs\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"ReferenceTooltips\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"main-page\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");});
    Krawędź grafu jest to para (zbiór dwuelementowy) wyróżnionych wierzchołków grafu, czyli takich, które są ze sobą połączone (sąsiednie). W reprezentacji graficznej jest to linia łącząca te wierzchołki. W szczególności krawędź może łączyć dwa te same wierzchołki i jest wówczas nazywana pętlą. Krawędź skierowaną, czyli będącą parą uporządkowanych wierzchołków, nazywamy łukiem.



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.015 sek.