[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/minimalne-pokrycie-drzewa-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/minimalne-pokrycie-drzewa-wikipedia\/","headline":"Minimalne pokrycie drzewa – Wikipedia","name":"Minimalne pokrycie drzewa – Wikipedia","description":"before-content-x4 W teorii wykres\u00f3w, bior\u0105c pod uwag\u0119 wykres z wa\u017ceniem \u0142uk\u00f3w, minimalne drzewo pokrywaj\u0105ce O Minimalne pokrycie koszt\u00f3w ( minimalne","datePublished":"2019-01-05","dateModified":"2019-01-05","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/b4c9714297c6218145c379c2f6404714063b9e24","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/b4c9714297c6218145c379c2f6404714063b9e24","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/minimalne-pokrycie-drzewa-wikipedia\/","wordCount":8715,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4W teorii wykres\u00f3w, bior\u0105c pod uwag\u0119 wykres z wa\u017ceniem \u0142uk\u00f3w, minimalne drzewo pokrywaj\u0105ce O Minimalne pokrycie koszt\u00f3w ( minimalne drzewo rozpinaj\u0105ce W MST ) [Pierwszy] Jest to pokryte drzewo, w kt\u00f3rym dodaj\u0105c ci\u0119\u017cary \u0142uk\u00f3w, uzyskuje si\u0119 minimaln\u0105 warto\u015b\u0107.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Bior\u0105c pod uwag\u0119 wykres G = ( N W A ) {DisplayStyle g = (n, a)} nie zorientowane, po\u0142\u0105czone i zwa\u017cenia i zak\u0142adaj\u0105c, \u017ce w ( W W W ) \u2208 R + {DisplayStyle w (u, v) w Mathbb {r} ^{+}} by\u0107 funkcj\u0105 wagi        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4G {DisplayStyle g} . MST PE G {DisplayStyle g} Jest to zestaw \u0142uk\u00f3w, tak, \u017ce: [2]        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4w ( M S T ) = min MST\u2208S\u2211 (u,v)\u2208MSTw ( W W W ) . {DisplayStyle W (mST) = min _ {mstin s} sum _ {(u, v) w mST} w (u, v).} Gdzie S {DisplayStyle s} Jest to zestaw wszystkich zadaszonych drzew T {DisplayStyle T} Z G {DisplayStyle g} , to znaczy zestaw wszystkich podsumowa\u0144, kt\u00f3re szanuj\u0105 nast\u0119puj\u0105ce warunki: T \u2286 A {DisplayStyle tsubseteq a} , Dlatego T {DisplayStyle T} Zawiera tylko cz\u0119\u015b\u0107 oryginalnych \u0142uk\u00f3w, na limicie wszystkich, ale nie wi\u0119cej. ( N W T ) {displayStyle (n, t)} Jest pod\u0142\u0105czony: wszystkie w\u0119z\u0142y s\u0105 ze sob\u0105 pod\u0142\u0105czone. Bior\u0105c pod uwag\u0119 wykres G = ( N W A ) {DisplayStyle g = (n, a)} nie zorientowane i zwi\u0105zane z kosztami C I W J {DisplayStyle C_ {i, j}} zwi\u0105zane z \u0142ukami i wektorem przep\u0142yw\u00f3w na \u0142ukach X i,j= {1,se l’albero contiene l’arco\u00a0(i,j),0,altrimenti.{displayStyle x_ {i, j} = {begin {cales} 1, & {text {l’A al}}} Drzewo minimalnego pokrycia (MST) jest rozwi\u0105zaniem nast\u0119puj\u0105cego modelu matematycznego [3] min\u2211(i,j)\u2208Acijxij,\u2211(i,j)\u2208Axij=n\u22121(vincolo grafo connesso),\u2211i\u2208S,j\u2208Sxij\u2a7d|S|\u22121,\u2200S\u2286A,|S|\u2a7e3(vincolo assenza di cicli nel grafo),{DisplayStyle {start {wyr\u00f3wnany} & 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\u00f3wnany}}}  Gdzie S {DisplayStyle s} To zestaw \u0142uk\u00f3w tworz\u0105 drzewo dachowe T {DisplayStyle T} i ma nast\u0119puj\u0105ce w\u0142a\u015bciwo\u015bci: jest podzbiorem A {DisplayStyle A} (Zestaw \u0142uk\u00f3w wykresu); Krytynalno\u015b\u0107 tej ca\u0142o\u015bci musi by\u0107 co najmniej r\u00f3wna 3 (poniewa\u017c przy mniej ni\u017c 3 elementach w ca\u0142o\u015bci nie mo\u017cna utworzy\u0107 cyklu). Wi\u0105zanie z brakiem cykli na wykresie mo\u017cna r\u00f3wnie\u017c wyra\u017ca\u0107 przy u\u017cyciu koncepcji ci\u0119cia na wykresie. Drugie ograniczenie modelu stanie si\u0119 zatem: \u2211 i\u2208S,j\u2209SX ij+ \u2211 i\u2209S,j\u2208SX ij\u2a7e Pierwszy W \u2200 S \u2286 N (ograniczenie powi\u0105zanych w\u0119z\u0142\u00f3w) . {DisplayStyle sum _ {iin s, jnotin s} x_ {ij}+sum _ {inotin s, jin s} x_ {ij} geqslant 1, qquad forall ssubteq nquad {text {(vincolo nodi connessi)}. Table of ContentsWarunki optymalno\u015bci [[[ zmiana |. Modifica Wikitesto ] Algorytm og\u00f3lny [[[ zmiana |. Modifica Wikitesto ] Znajd\u017a odpowiedni \u0142uk [[[ zmiana |. Modifica Wikitesto ] Algorytmy u\u017cywane w praktyce [[[ zmiana |. Modifica Wikitesto ] Warunki optymalno\u015bci [[[ zmiana |. Modifica Wikitesto ] Minimalne drzewo pokrycia koszt\u00f3w T {DisplayStyle T} kt\u00f3ry jest uzyskiwany przez zastosowanie decyduj\u0105cego algorytmu, jest doskona\u0142e, je\u015bli szanuje nast\u0119puj\u0105ce warunki: Na cyklach: T {DisplayStyle T} Jest to minimalne drzewo pokrycia koszt\u00f3w \u21d4 \u2200 ( W W W ) \u2209 T C u,v\u2265 C i,jW  \u2200 ( I W J ) {DisplayStyle Quad Leftrightarrow Quad Forall (u, v) notin tquad c_ {u, v} geq c_ {i, j}, forall (i, j)} W podr\u00f3\u017cy z W {displayStyle u} A W {DisplayStyle v} W T {DisplayStyle T} ; Na ci\u0119ciach: T {DisplayStyle T} Jest to minimalne drzewo pokrycia koszt\u00f3w \u21d4 \u2200 ( W W W ) \u2208 T C u,v\u2264 C i,jW  \u2200 ( I W J ) {DisplayStyle Quad Leftrightarrow Quad Forall (u, v) w tquad c_ {u, v} leq c_ {i, j}, forall (i, j)} w formacie formatu poprzez eliminowanie \u0142uku ( W W W ) {displayStyle (u, v)} I T {DisplayStyle T} . Algorytm og\u00f3lny [[[ zmiana |. Modifica Wikitesto ] Algorytm og\u00f3lny do budowy minimalnego drzewa pokrycia jest chciwym typem. [Pierwszy] Bior\u0105c pod uwag\u0119 wykres G = ( W W I ) {DisplayStyle g = (v, e)} nie zorientowane, po\u0142\u0105czone i z funkcj\u0105 wagi w : I \u2192 R + {DisplayStyle Wcolon Erightarrow Mathbb {r} ^{+}} , algorytm dzia\u0142a na ca\u0142o\u015b\u0107 A \u2286 T {DisplayStyle Asubseteq t} (Syn T {DisplayStyle T} MST di G {DisplayStyle g} ) do kt\u00f3rego \u0142uk jest dodawany na ka\u017cdym etapie ( W W w ) {DisplayStyle (u, w)} co pozwala A {DisplayStyle A} Aby pozosta\u0107 podzbiorem fina\u0142u MST, taki \u0142uk zostanie wywo\u0142any bezpieczna kraw\u0119d\u017a . [2] A \u2190 \u2205 {DisplayStyle Aleftarrow varnothing} chwila  A \u2260 T {DisplayStyle aneq t}  Do  (u,v)\u2190{displayStyle (u, v) leftarrow} bezpieczna kraw\u0119d\u017a (A){DisplayStyle (a)} A\u2190A\u222a(u,v){DisplayStyle Aleftarrow ACUP (u, v)} zako\u0144czy\u0107 powr\u00f3t A Znajd\u017a odpowiedni \u0142uk [[[ zmiana |. Modifica Wikitesto ] Aby znale\u017a\u0107 prawid\u0142owy \u0142uk, nale\u017cy ucieka\u0107 si\u0119 do niekt\u00f3rych definicji. Przede wszystkim ( S W W – S ) {DisplayStyle (s, v-s)} dziecko S \u2286 W {DisplayStyle ssubseteq v} B\u0119dzie si\u0119 nazywa\u0107 ci\u0119cie, a my b\u0119dziemy to mie\u0107: \u0141uk np. w budowli ( W W W ) {displayStyle (u, v)} przekroczy\u0107 ci\u0119cie ( S W W – S ) {DisplayStyle (s, v-s)} wtedy i tylko wtedy gdy W \u2208 S \u2227 W \u2208 ( W – S ) {DisplayStyle Uin Sland Vin (V-S)} . drzewo A \u2286 I {DisplayStyle Asubseteq e} Szanuj ci\u0119cie ( S W W – S ) {DisplayStyle (s, v-s)} wtedy i tylko wtedy gdy \u2204 ( W W W ) \u2208 A {DisplayStyle nie istnieje (u, v) w} kt\u00f3ry przecina ci\u0119cie. \u0141uk np. w budowli ( W W W ) {displayStyle (u, v)} definiuje \u015bwiat\u0142o W por\u00f3wnaniu do ci\u0119cia ( S W W – S ) {DisplayStyle (s, v-s)} , je\u015bli jest to minimalna waga w\u015br\u00f3d wszystkich \u0142uk\u00f3w, kt\u00f3re przecinaj\u0105. Zakrztusi\u0142 ca\u0142o\u015b\u0107 A {DisplayStyle A} \u0142uk\u00f3w zawartych w minimalnym drzewie po\u0142\u0105czeniowym, oba ( S W W – S ) {DisplayStyle (s, v-s)} Ci\u0119cie, kt\u00f3re szanuje A {DisplayStyle A} I niech to b\u0119dzie A = ( W W W ) {DisplayStyle a = (u, v)} lekki \u0142uk, a potem \u0142uk A {DisplayStyle A} Jest bezpieczny (bezpieczny). Algorytmy u\u017cywane w praktyce [[[ zmiana |. Modifica Wikitesto ] Bior\u0105c pod uwag\u0119 wykres, istnieje kilka algorytm\u00f3w do identyfikacji jednego z jego MSS, w\u015br\u00f3d nich: W przypadku, gdy wykres nie jest pod\u0142\u0105czony, to znaczy jest wynikiem po\u0142\u0105czenia najbardziej pod\u0142\u0105czonych wykres\u00f3w, nadal mo\u017cna zdefiniowa\u0107 minimalny las zadaszony takich jak zwi\u0105zek drzew obj\u0119tych zidentyfikowanymi na poszczeg\u00f3lnych pod\u0142\u0105czonych wykresach. Na po\u0142\u0105czonych wykresach las i zadaszone drzewo pokrywaj\u0105 si\u0119. Minimalne drzewo obejmuj\u0105ce bezpo\u015brednie aplikacje w projektowaniu sieci, w tym sieci komputerowe, sieci telekomunikacyjne, sieci transportowe, sieci zaopatrzenia w wod\u0119 i sie\u0107 elektryczn\u0105. [4] Inne praktyczne zastosowania oparte na minimalnych os\u0142onach: Taksonomia. [5] Klastrowanie: grupowanie punkt\u00f3w w samolocie, [6] Budowa drzew do nadawania w sieciach komputerowych. [7] Wydobycie Curvilinea w wizji komputerowej. [8] Uznanie pisania dla wyra\u017ce\u0144 matematycznych. [9] Regionalizacja obszar\u00f3w spo\u0142eczno-geograficznych, czyli w grupach w obszarach jednorodnych i ci\u0105g\u0142ego. [dziesi\u0119\u0107] Minimalne zadaszone drzewa mo\u017cna u\u017cy\u0107 do opisania rynk\u00f3w finansowych. [11] [dwunasty] Macierz korelacji mo\u017cna utworzy\u0107 poprzez obliczenie wsp\u00f3\u0142czynnika korelacji mi\u0119dzy dwoma zapasami. Ta macierz mo\u017ce by\u0107 reprezentowana topologicznie jako z\u0142o\u017cona sie\u0107 i mo\u017cna zbudowa\u0107 minimalne zadaszone drzewo, aby zobaczy\u0107 jego relacje. ^  A B  Goodrich-Tamassia, s. 1 564 .  ^  A B  ( W ) Samuel J. Lomonaco, Jr., Minimalne drzewa ( PDF ), Czy cseese.umbc.edu , Maryland University – Wydzia\u0142 IT i in\u017cynieria elektryczna. URL skonsultowa\u0142 si\u0119 2 stycznia 2017 r. .  ^  G. Bigi, A. Calloni, Rare. Galladiles Pallottino, M. G. Stutelli: Notatki z bada\u0144 operacyjnych , SEU – PISA University Editorial Service  ^  R. L. Graham E Pavol Hell, O historii minimalnego problemu drzewa rozpinaj\u0105cego , W Annals of the History of Computing , tom. 7, n. 1, 1985, s. 43\u201357, doi: 10.1109\/mahc.1985.10011 , PAN 783327 .  ^  P. H. A. Sneath, Zastosowanie komputer\u00f3w do taksonomii , W Journal of General Microbiology , tom. 17, n. 1, 1 sierpnia 1957 r., S. 201\u2013226, doi: 10.1099\/00221287-17-1-201 , PMID 13475686 .  ^  T. Asano, B. Bhattacharya, M. Keil E F. Yao, Algorytmy grupowania na podstawie minimalnych i maksymalnych drzew rozpinaj\u0105cych W Czwarte doroczne sympozjum na temat geometrii obliczeniowej (SCG ’88) , vol. 1, 1988, s. 252\u2013257, dwa: 10.1145\/73393.73419 .  ^  Yogen K. Dalal E Robert M. Metcalfe, Odwrotna \u015bcie\u017cka przekazywania pakiet\u00f3w nadawczych , W Komunikacja ACM , tom. 21, n. 12, 1 grudnia 1978 r., S. 1040\u20131048, doi: 10.1145\/359657.359665 .  ^  Minsoo Suk E Ohyoung Song, Wydobycie cech krzywoliniowych przy u\u017cyciu minimalnych drzew sp\u0119dzaj\u0105cych , W Wizja komputerowa, grafika i przetwarzanie obrazu , tom. 26, n. 3, 1 czerwca 1984 r., S. 400\u2013411, doi: 10.1016\/0734-189x (84) 90221-4 .  ^  Ernesto tapia e ra\u00fal rojas, Rozpoznawanie odr\u0119cznych wyra\u017ce\u0144 matematycznych na linii przy u\u017cyciu minimalnej konstrukcji drzewa rozpinaj\u0105cego si\u0119 i dominacji symboli ( PDF ), W Rozpoznawanie grafiki. Ostatnie post\u0119py i perspektywy , Notatki z wyk\u0142adu w informatyce, t. 3088, Berlin Heidelberg, Springer-Verlag, 2004, s. 329\u2013340, ISBN 978-3-540-22478-5.  ^  R. M. Assun\u00e7\u00e3o, M. C. Neves, G. C\u00e2mara i C. da Costa Freitas, Skuteczne techniki regionalizacji dla spo\u0142eczno -ekonomicznych jednostek geograficznych z wykorzystaniem minimalnych drzew obejmuj\u0105cych , W International Journal of Geographical Information Science , tom. 20, n. 7, 2006, s. 797\u2013811, doi: 10 1080\/13658810600665111 .  ^  Mantegna, R. N. (1999). Hierarchiczna struktura na rynkach finansowych . Europejski dziennik fizyczny B-Condensed Matter and Complex Systems, 11 (1), 193\u2013197.  ^  Djauhari, M., i Gan, S. (2015). Problem optymalno\u015bci topologii sieci w analizie rynku akcji . Physica A: Mechanika statystyczna i jej zastosowania, 419, 108-114.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/minimalne-pokrycie-drzewa-wikipedia\/#breadcrumbitem","name":"Minimalne pokrycie drzewa – Wikipedia"}}]}]