Minimalne pokrycie drzewa – Wikipedia

Posted on by
before-content-x4

W teorii wykresów, biorąc pod uwagę wykres z ważeniem łuków, minimalne drzewo pokrywające O Minimalne pokrycie kosztów ( minimalne drzewo rozpinające W MST ) [Pierwszy] Jest to pokryte drzewo, w którym dodając ciężary łuków, uzyskuje się minimalną wartość.

after-content-x4

Biorąc pod uwagę wykres

G = ( N W A ) {DisplayStyle g = (n, a)}

nie zorientowane, połączone i zważenia i zakładając, że

w ( W W W ) ∈ R + {DisplayStyle w (u, v) w Mathbb {r} ^{+}}

być funkcją wagi

G {DisplayStyle g}

.

MST PE

G {DisplayStyle g}

Jest to zestaw łuków, tak, że: [2]

Gdzie

S {DisplayStyle s}

Jest to zestaw wszystkich zadaszonych drzew

T {DisplayStyle T}

Z

G {DisplayStyle g}

, to znaczy zestaw wszystkich podsumowań, które szanują następujące warunki:

Biorąc pod uwagę wykres

G = ( N W A ) {DisplayStyle g = (n, a)}

nie zorientowane i związane z kosztami

C I W J {DisplayStyle C_ {i, j}}

związane z łukami i wektorem przepływów na łukach

Drzewo minimalnego pokrycia (MST) jest rozwiązaniem następującego modelu matematycznego [3]

min∑(i,j)∈Acijxij,∑(i,j)∈Axij=n−1(vincolo grafo connesso),∑i∈S,j∈Sxij⩽|S|−1,∀S⊆A,|S|⩾3(vincolo assenza di cicli nel grafo),{DisplayStyle {start {wyrównany} & min sum _ {(i, j) w a} c_ {ij} x_ {ij}, \ & sum _ {(i, j) w} x_ {ij} = n- { Text {(Connected Graph Ograniczenie)}}, \ & sum _ {iin s, jin s} x_ {ij} leqslant | s | -1, qquad forall ssubseteq a, | s | geqslant 3quad {text {(Bond of Cycles in in Cycles in in wykresy)}}, end {wyrównany}}}

Gdzie

S {DisplayStyle s}

To zestaw łuków tworzą drzewo dachowe

T {DisplayStyle T}

i ma następujące właściwości:

  • jest podzbiorem
  • Krytynalność tej całości musi być co najmniej równa 3 (ponieważ przy mniej niż 3 elementach w całości nie można utworzyć cyklu).

Wiązanie z brakiem cykli na wykresie można również wyrażać przy użyciu koncepcji cięcia na wykresie. Drugie ograniczenie modelu stanie się zatem:

Warunki optymalności [[[ zmiana |. Modifica Wikitesto ]

Minimalne drzewo pokrycia kosztów

T {DisplayStyle T}

który jest uzyskiwany przez zastosowanie decydującego algorytmu, jest doskonałe, jeśli szanuje następujące warunki:

  • Na cyklach:
  • Na cięciach:

Algorytm ogólny [[[ zmiana |. Modifica Wikitesto ]

Algorytm ogólny do budowy minimalnego drzewa pokrycia jest chciwym typem. [Pierwszy] Biorąc pod uwagę wykres

G = ( W W I ) {DisplayStyle g = (v, e)}

nie zorientowane, połączone i z funkcją wagi

w : I → R + {DisplayStyle Wcolon Erightarrow Mathbb {r} ^{+}}

, algorytm działa na całość

A ⊆ T {DisplayStyle Asubseteq t}

(Syn

T {DisplayStyle T}

MST di

G {DisplayStyle g}

) do którego łuk jest dodawany na każdym etapie

( W W w ) {DisplayStyle (u, w)}

co pozwala

A {DisplayStyle A}

Aby pozostać podzbiorem finału MST, taki łuk zostanie wywołany bezpieczna krawędź . [2]

  2. chwila
  3. zakończyć
  4. powrót A

Znajdź odpowiedni łuk [[[ zmiana |. Modifica Wikitesto ]

Aby znaleźć prawidłowy łuk, należy uciekać się do niektórych definicji.

Przede wszystkim

( S W W – S ) {DisplayStyle (s, v-s)}

dziecko

S ⊆ W {DisplayStyle ssubseteq v}

Będzie się nazywać cięcie, a my będziemy to mieć:

  1. Łuk np. w budowli
  2. drzewo

Łuk np. w budowli

( W W W ) {displayStyle (u, v)}

definiuje światło W porównaniu do cięcia

( S W W – S ) {DisplayStyle (s, v-s)}

, jeśli jest to minimalna waga wśród wszystkich łuków, które przecinają.

Zakrztusił całość

A {DisplayStyle A}

łuków zawartych w minimalnym drzewie połączeniowym, oba

( S W W – S ) {DisplayStyle (s, v-s)}

Cięcie, które szanuje

A {DisplayStyle A}

I niech to będzie

A = ( W W W ) {DisplayStyle a = (u, v)}

lekki łuk, a potem łuk

A {DisplayStyle A}

Jest bezpieczny (bezpieczny).

Algorytmy używane w praktyce [[[ zmiana |. Modifica Wikitesto ]

Biorąc pod uwagę wykres, istnieje kilka algorytmów do identyfikacji jednego z jego MSS, wśród nich:

W przypadku, gdy wykres nie jest podłączony, to znaczy jest wynikiem połączenia najbardziej podłączonych wykresów, nadal można zdefiniować minimalny las zadaszony takich jak związek drzew objętych zidentyfikowanymi na poszczególnych podłączonych wykresach. Na połączonych wykresach las i zadaszone drzewo pokrywają się.

Minimalne drzewo obejmujące bezpośrednie aplikacje w projektowaniu sieci, w tym sieci komputerowe, sieci telekomunikacyjne, sieci transportowe, sieci zaopatrzenia w wodę i sieć elektryczną. [4]

Inne praktyczne zastosowania oparte na minimalnych osłonach:

  • Taksonomia. [5]
  • Klastrowanie: grupowanie punktów w samolocie, [6]
  • Budowa drzew do nadawania w sieciach komputerowych. [7]
  • Wydobycie Curvilinea w wizji komputerowej. [8]
  • Uznanie pisania dla wyrażeń matematycznych. [9]
  • Regionalizacja obszarów społeczno-geograficznych, czyli w grupach w obszarach jednorodnych i ciągłego. [dziesięć]
  • Minimalne zadaszone drzewa można użyć do opisania rynków finansowych. [11] [dwunasty] Macierz korelacji można utworzyć poprzez obliczenie współczynnika korelacji między dwoma zapasami. Ta macierz może być reprezentowana topologicznie jako złożona sieć i można zbudować minimalne zadaszone drzewo, aby zobaczyć jego relacje.
  1. ^ A B Goodrich-Tamassia, s. 1 564 .
  2. ^ A B ( W ) Samuel J. Lomonaco, Jr., Minimalne drzewa ( PDF ), Czy cseese.umbc.edu , Maryland University – Wydział IT i inżynieria elektryczna. URL skonsultował się 2 stycznia 2017 r. .
  3. ^ G. Bigi, A. Calloni, Rare. Galladiles Pallottino, M. G. Stutelli: Notatki z badań operacyjnych , SEU – PISA University Editorial Service
  4. ^ R. L. Graham E Pavol Hell, O historii minimalnego problemu drzewa rozpinającego , W Annals of the History of Computing , tom. 7, n. 1, 1985, s. 43–57, doi: 10.1109/mahc.1985.10011 , PAN 783327 .
  5. ^ P. H. A. Sneath, Zastosowanie komputerów do taksonomii , W Journal of General Microbiology , tom. 17, n. 1, 1 sierpnia 1957 r., S. 201–226, doi: 10.1099/00221287-17-1-201 , PMID 13475686 .
  6. ^ T. Asano, B. Bhattacharya, M. Keil E F. Yao, Algorytmy grupowania na podstawie minimalnych i maksymalnych drzew rozpinających W Czwarte doroczne sympozjum na temat geometrii obliczeniowej (SCG ’88) , vol. 1, 1988, s. 252–257, dwa: 10.1145/73393.73419 .
  7. ^ Yogen K. Dalal E Robert M. Metcalfe, Odwrotna ścieżka przekazywania pakietów nadawczych , W Komunikacja ACM , tom. 21, n. 12, 1 grudnia 1978 r., S. 1040–1048, doi: 10.1145/359657.359665 .
  8. ^ Minsoo Suk E Ohyoung Song, Wydobycie cech krzywoliniowych przy użyciu minimalnych drzew spędzających , W Wizja komputerowa, grafika i przetwarzanie obrazu , tom. 26, n. 3, 1 czerwca 1984 r., S. 400–411, doi: 10.1016/0734-189x (84) 90221-4 .
  9. ^ Ernesto tapia e raúl rojas, Rozpoznawanie odręcznych wyrażeń matematycznych na linii przy użyciu minimalnej konstrukcji drzewa rozpinającego się i dominacji symboli ( PDF ), W Rozpoznawanie grafiki. Ostatnie postępy i perspektywy , Notatki z wykładu w informatyce, t. 3088, Berlin Heidelberg, Springer-Verlag, 2004, s. 329–340, ISBN 978-3-540-22478-5.
  10. ^ R. M. Assunção, M. C. Neves, G. Câmara i C. da Costa Freitas, Skuteczne techniki regionalizacji dla społeczno -ekonomicznych jednostek geograficznych z wykorzystaniem minimalnych drzew obejmujących , W International Journal of Geographical Information Science , tom. 20, n. 7, 2006, s. 797–811, doi: 10 1080/13658810600665111 .
  11. ^ Mantegna, R. N. (1999). Hierarchiczna struktura na rynkach finansowych . Europejski dziennik fizyczny B-Condensed Matter and Complex Systems, 11 (1), 193–197.
  12. ^ Djauhari, M., i Gan, S. (2015). Problem optymalności topologii sieci w analizie rynku akcji . Physica A: Mechanika statystyczna i jej zastosowania, 419, 108-114.

after-content-x4