Arborele minim de acoperire

În teoria graficelor , având în vedere un grafic cu arcuri cântărite, l 'acoperirea costului minim care acoperă arborele minim sau arborele ( arborele minim care se întinde, MST) ^[1] este un arbore care se întinde în care însumarea greutăților arcurilor se obține o valoare minimă.

Definiție formală

Având în vedere un grafic $G=(N,A)$ ${\ displaystyle G = (N, A)}$ ${\ displaystyle G = (N, A)}$ neorientat, conectat și cântărit și presupunând că $w(u,v)\in \mathbb {R} ^{+}$ ${\ displaystyle w (u, v) \ in \ mathbb {R} ^ {+}}$ ${\ displaystyle w (u, v) \ in \ mathbb {R} ^ {+}}$ este o greutate după funcție $G.$ ${\ displaystyle G}$ $G.$ .

Un MST pentru $G.$ ${\ displaystyle G}$ $G.$ este un set de arce astfel încât: ^[2]

w(MST)=\min _{MST\in S}\sum _{(u,v)\in MST}w(u,v)

{\ displaystyle w (MST) = \ min _ {MST \ in S} \ sum _ {(u, v) \ in MST} w (u, v)}

{\ displaystyle w (MST) = \ min _ {MST \ in S} \ sum _ {(u, v) \ in MST} w (u, v)}

.

Unde este $S.$ ${\ displaystyle S}$ $S.$ este ansamblul tuturor copacilor care se întind $T.$ ${\ displaystyle T}$ $T.$ din $G.$ ${\ displaystyle G}$ $G.$ , adică ansamblul tuturor subgrafelor sale care îndeplinesc următoarele condiții:

$T\subseteq A$ ${\ displaystyle T \ subseteq A}$ ${\ displaystyle T \ subseteq A}$ , asa de $T.$ ${\ displaystyle T}$ $T.$ conține doar o parte din arcurile originale, cel puțin toate, dar nu mai mult.
$(N,T)$ ${\ displaystyle (N, T)}$ ${\ displaystyle (N, T)}$ este conectat : nodurile sunt toate conectate între ele.

Model matematic

Având în vedere un grafic $G=(N,A)$ ${\ displaystyle G = (N, A)}$ ${\ displaystyle G = (N, A)}$ neorientate și asociate cu costurile $c_{i,j}$ ${\ displaystyle c_ {i, j}}$ ${\ displaystyle c_ {i, j}}$ asociat arcurilor și vectorului fluxurilor pe arcuri $x_{i,j}={\begin{cases}1&{\text{se l'albero contiene l'arco }}(i,j)\\0&{\text{altrimenti}}\end{cases}}$ ${\ displaystyle x_ {i, j} = {\ begin {cases} 1 & {\ text {dacă arborele conține arc}} (i, j) \\ 0 & {\ text {altfel}} \ end {case }}}$ ${\ displaystyle x_ {i, j} = {\ begin {cases} 1 & {\ text {dacă arborele conține arc}} (i, j) \\ 0 & {\ text {altfel}} \ end {case }}}$ .

Un arbore care acoperă costul minim (MST) este soluția următorului model matematic ^[3]

${\begin{aligned}&min\sum _{(i,j)\in A}c_{ij}x_{ij}\\&\sum _{(i,j)\in A}x_{ij}=n-1&{\text{(vincolo grafo connesso)}}\\&\sum _{i\in S,j\in S}x_{ij}\leqslant |S|-1\qquad \forall S\subseteq A,|S|\geqslant 3&{\text{(vincolo assenza di cicli nel grafo)}}\\\end{aligned}}$ ${\ displaystyle {\ begin {align} & min \ sum _ {(i, j) \ in A} c_ {ij} x_ {ij} \\ & \ sum _ {(i, j) \ in A} x_ { ij} = n-1 & {\ text {(constrângere grafic conectat)}} \\ & \ sum _ {i \ în S, j \ in S} x_ {ij} \ leqslant | S | -1 \ qquad \ forall S \ subseteq A, | S | \ geqslant 3 & {\ text {(constrângerea absenței ciclurilor în grafic)}} \\\ end {align}}}$ ${\ displaystyle {\ begin {align} & min \ sum _ {(i, j) \ in A} c_ {ij} x_ {ij} \\ & \ sum _ {(i, j) \ in A} x_ { ij} = n-1 & {\ text {(constrângere grafic conectat)}} \\ & \ sum _ {i \ în S, j \ in S} x_ {ij} \ leqslant | S | -1 \ qquad \ forall S \ subseteq A, | S | \ geqslant 3 & {\ text {(constrângerea absenței ciclurilor în grafic)}} \\\ end {align}}}$

Unde este $S.$ ${\ displaystyle S}$ $S.$ este setul de arcuri care alcătuiesc arborele care se întinde $T.$ ${\ displaystyle T}$ $T.$ și are următoarele proprietăți:

este un subset de $LA$ ${\ displaystyle A}$ $LA$ (set de arce ale graficului)
cardinalitatea acestui set trebuie să fie cel puțin egală cu 3 (deoarece un ciclu nu poate fi creat cu mai puțin de 3 elemente într-un set)

Constrângerea asupra absenței ciclurilor în grafic poate fi exprimată, de asemenea, utilizând conceptul de tăiere într-un grafic. A doua constrângere a modelului va deveni apoi:

${\begin{aligned}&\sum _{i\in S,j\notin S}x_{ij}+\sum _{i\notin S,j\in S}x_{ij}\geqslant 1\qquad \forall S\subseteq N&{\text{(vincolo nodi connessi)}}\\\end{aligned}}$ ${\ displaystyle {\ begin {align} & \ sum _ {i \ in S, j \ notin S} x_ {ij} + \ sum _ {i \ notin S, j \ in S} x_ {ij} \ geqslant 1 \ qquad \ forall S \ subseteq N & {\ text {(constrângere nod conectat)}} \\\ end {align}}}$ ${\ displaystyle {\ begin {align} & \ sum _ {i \ in S, j \ notin S} x_ {ij} + \ sum _ {i \ notin S, j \ in S} x_ {ij} \ geqslant 1 \ qquad \ forall S \ subseteq N & {\ text {(constrângere nod conectat)}} \\\ end {align}}}$

Condiții de optimitate

Arborele cu cel mai mic cost $T.$ ${\ displaystyle T}$ $T.$ obținut prin aplicarea unui algoritm de soluție este excelent dacă respectă următoarele condiții:

pe cicluri: $T{\text{ e' un albero di copertura di costo minimo}}\qquad \Leftrightarrow \qquad \forall {\text{(u,v)}}\notin T\qquad c_{u,v}\geq c_{i,j}\ \forall (i,j)\in {\text{cammino da u a v in T}}$ ${\ displaystyle T {\ text {este un arbore de cost minim}} \ qquad \ Leftrightarrow \ qquad \ forall {\ text {(u, v)}} \ notin T \ qquad c_ {u, v} \ geq c_ { i, j} \ \ forall (i, j) \ in {\ text {Merg de la u la v în T}}}$ ${\ displaystyle T {\ text {este un arbore de cost minim}} \ qquad \ Leftrightarrow \ qquad \ forall {\ text {(u, v)}} \ notin T \ qquad c_ {u, v} \ geq c_ { i, j} \ \ forall (i, j) \ in {\ text {Merg de la u la v în T}}}$
pe tăieturi: $T{\text{ e' un albero di copertura di costo minimo}}\qquad \Leftrightarrow \qquad \forall {\text{(u,v)}}\in T\qquad c_{u,v}\leq c_{i,j}\ \forall (i,j)\in {\text{taglio formato eliminando l'arco (u,v) da T}}$ ${\ displaystyle T {\ text {este un arbore de cost minim}} \ qquad \ Leftrightarrow \ qquad \ forall {\ text {(u, v)}} \ in T \ qquad c_ {u, v} \ leq c_ { i, j} \ \ forall (i, j) \ in {\ text {cut format prin eliminarea arcului (u, v) din T}}}$ ${\ displaystyle T {\ text {este un arbore de cost minim}} \ qquad \ Leftrightarrow \ qquad \ forall {\ text {(u, v)}} \ in T \ qquad c_ {u, v} \ leq c_ { i, j} \ \ forall (i, j) \ in {\ text {cut format prin eliminarea arcului (u, v) din T}}}$

Algoritmi pentru calcularea unui MST

Algoritm generic

Algoritmul generic pentru construirea unui copac minim care se întinde este de tip lacom . ^[1] Dat un grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ neorientat, conectat și cu funcție de greutate $w:E\rightarrow \mathbb {R} ^{+}$ ${\ displaystyle w: E \ rightarrow \ mathbb {R} ^ {+}}$ ${\ displaystyle w: E \ rightarrow \ mathbb {R} ^ {+}}$ , algoritmul acționează asupra unui set $A\subseteq T$ ${\ displaystyle A \ subseteq T}$ ${\ displaystyle A \ subseteq T}$ (cu $T.$ ${\ displaystyle T}$ $T.$ MST din $G.$ ${\ displaystyle G}$ $G.$ ) la care se adaugă un arc la fiecare pas $(u,w)$ ${\ displaystyle (u, w)}$ ${\ displaystyle (u, w)}$ ceea ce permite $LA$ ${\ displaystyle A}$ $LA$ pentru a rămâne un subset al MST final, un astfel de arc se va numi safe-edge . ^[2]

$A\leftarrow \emptyset$ ${\ displaystyle A \ leftarrow \ emptyset}$ ${\ displaystyle A \ leftarrow \ emptyset}$
in timp ce $LA$ $\neq$ $T.$ {\ displaystyle A \ neq T} ${\ displaystyle A \ neq T}$ do
1. $(u,v)\leftarrow$ ${\ displaystyle (u, v) \ leftarrow}$ ${\ displaystyle (u, v) \ leftarrow}$ sigur-margine $(A)$ ${\ displaystyle (A)}$ ${\ displaystyle (A)}$
2. $A\leftarrow A\cup (u,v)$ ${\ displaystyle A \ leftarrow A \ cup (u, v)}$ ${\ displaystyle A \ leftarrow A \ cup (u, v)}$
incheie in timp ce
întoarcere A

Găsiți arcul corect

Pentru a găsi arcul corect este necesar să folosiți câteva definiții:

Pentru inceput $(S,V-S)$ ${\ displaystyle (S, VS)}$ ${\ displaystyle (S, V-S)}$ cu $S\subseteq V$ ${\ displaystyle S \ subseteq V}$ $S \ subseteq V$ va fi numit tăiat și vom avea asta:

un arc $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ traversează o tăietură $(S,V-S)$ ${\ displaystyle (S, VS)}$ ${\ displaystyle (S, V-S)}$ dacă și numai dacă $u\in S\land v\in (V-S)$ ${\ displaystyle u \ in S \ land v \ in (VS)}$ ${\ displaystyle u \ in S \ land v \ in (V-S)}$ .
un copac $A\subseteq E$ ${\ displaystyle A \ subseteq E}$ ${\ displaystyle A \ subseteq E}$ respectă o tăietură $(S,V-S)$ ${\ displaystyle (S, VS)}$ ${\ displaystyle (S, V-S)}$ dacă și numai dacă $\not \exists (u,v)\in A$ ${\ displaystyle \ not \ există (u, v) \ în A}$ ${\ displaystyle \ not \ există (u, v) \ în A}$ alergând prin tăietură.

Un arc $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ este definit ca lumină în comparație cu o tăietură $(S,V-S)$ ${\ displaystyle (S, VS)}$ ${\ displaystyle (S, V-S)}$ , dacă are o greutate minimă între toate arcele care trec prin acea tăietură.

Am un grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ nu este orientat și conectat, o funcție de greutate $w:E\rightarrow R^{+}$ ${\ displaystyle w: E \ rightarrow R ^ {+}}$ ${\ displaystyle w: E \ rightarrow R ^ {+}}$ , un copac $A\subseteq T$ ${\ displaystyle A \ subseteq T}$ ${\ displaystyle A \ subseteq T}$ cu $T.$ ${\ displaystyle T}$ $T.$ MST pentru $G.$ ${\ displaystyle G}$ $G.$ și în cele din urmă o tăietură $(S,V-S)$ ${\ displaystyle (S, VS)}$ ${\ displaystyle (S, V-S)}$ din $G.$ ${\ displaystyle G}$ $G.$ și $LA$ ${\ displaystyle A}$ $LA$ .

Atunci $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ este o siguranță pentru $LA$ ${\ displaystyle A}$ $LA$ .

Algoritmi folosiți în practică

Având în vedere un grafic, există mai mulți algoritmi pentru a identifica MST-ul acestuia, printre aceștia:

Pădurea minimă de acoperire

În cazul în care graficul nu este conectat , adică este rezultatul unirii mai multor grafice conectate, putem defini totuși o pădure de întindere minimă ca uniune a copacilor de întindere identificate pe graficele unice conectate. În graficele conectate, pădurea și arborele întins coincid.

Aplicații

Arborii minimi au aplicații directe în proiectarea rețelelor, inclusiv rețele de calculatoare , rețele de telecomunicații , rețele de transport , rețele de alimentare cu apă și rețele de alimentare . ^[4]

Alte aplicații practice bazate pe copaci minimi de acoperire:

Taxonomie . ^[5]
Clustering : gruparea punctelor din plan, ^[6]
Construirea arborilor pentru difuzare în rețele de calculatoare. ^[7]
Extragerea caracteristicilor curvilinee în viziunea computerizată . ^[8]
Recunoașterea scrisului de mână pentru expresii matematice. ^[9]
Regionalizarea zonelor socio-geografice sau gruparea zonelor în regiuni omogene și adiacente. ^[10]
Minii Spanning Trees pot fi folosiți pentru a descrie piețele financiare. ^[11] ^[12] O matrice de corelație poate fi creată prin calcularea unui coeficient de corelație între oricare două stocuri. Această matrice poate fi reprezentată topologic ca o rețea complexă și se poate construi un copac minim care vizualizează relațiile.

Notă

^ ^a ^b Goodrich-Tamassia , p. 564 .
^ ^A ^b (EN) Lomonaco Samuel J., Jr., Minimal-Spanning-Trees (PDF), pe csee.umbc.edu, Universitatea din Maryland - Departamentul de Informatică și Inginerie Electrică. Adus pe 2 ianuarie 2017 .
^ G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, MG Scutellà, Note privind cercetarea operațională , SEU - Serviciul de editare universitar din Pisa
^ RL Graham și Pavol Hell , Despre istoria problemei arborelui minim , în Annals of the History of Computing , vol. 7, nr. 1, 1985, pp. 43-57, DOI : 10.1109 / MAHC.1985.10011 , MR 783327 .
^ PHA Sneath, The Application of Computers to Taxonomy , în Journal of General Microbiology , vol. 17, n. 1, 1 august 1957, pp. 201–226, DOI : 10.1099 / 00221287-17-1-201 , PMID 13475686 .
^ T. Asano , B. Bhattacharya, M. Keil și F. Yao , Algoritmi de grupare bazate pe copacii care se întind pe minim și maxim , al patrulea simpozion anual de geometrie computațională (SCG '88) , vol. 1, 1988, pp. 252-257, DOI : 10.1145 / 73393.73419 .
^ Yogen K. Dalal și Robert M. Metcalfe, Redirecționarea inversă a pachetelor de difuzare , în Communications of the ACM , vol. 21, n. 12, 1 decembrie 1978, pp. 1040-1048, DOI : 10.1145 / 359657.359665 .
^ Minsoo Suk și Ohyoung Song, extragerea caracteristicilor curvilinee folosind copaci minimi , în Computer Vision, Graphics și Image Processing , vol. 26, n. 3, 1 iunie 1984, pp. 400–411, DOI : 10.1016 / 0734-189X (84) 90221-4 .
^ Ernesto Tapia și Raúl Rojas, Recunoașterea expresiilor matematice scrise de mână on-line folosind o construcție minimă a arborelui și dominarea simbolurilor ( PDF ), în Recunoaștere grafică. Progrese și perspective recente , Note de curs în informatică, vol. 3088, Berlin Heidelberg, Springer-Verlag, 2004, pp. 329-340, ISBN 978-3-540-22478-5 .
^ RM AssunÇão, MC Neves, G. Câmara și C. Da Costa Freitas, Tehnici de regionalizare eficiente pentru unități geografice socio-economice folosind copaci cu întindere minimă , în International Journal of Geographic Information Science , vol. 20, nr. 7, 2006, pp. 797–811, DOI : 10.1080 / 13658810600665111 .
^ Mantegna, RN (1999). Structura ierarhică pe piețele financiare . European Physical Journal B-Condensed Matter and Complex Systems, 11 (1), 193-197.
^ Djauhari, M. și Gan, S. (2015). Problema de optimitate a topologiei rețelei în analiza pieței acțiunilor . Physica A: Mecanica statistică și aplicațiile sale, 419, 108-114.

Bibliografie

Michael T. Goodrich, Roberto Tamassia, Structuri de date și algoritmi în Java , Bologna, Zanichelli Editore , 2007, pp. 562-565, ISBN 978-88-08-07037-1 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un copac minim

Portal IT

Portalul de matematică

[Goodrich-Tamassia-564-1] Goodrich-Tamassia , p. 564 .

[umbc-2] A ^b (EN) Lomonaco Samuel J., Jr., Minimal-Spanning-Trees (PDF), pe csee.umbc.edu, Universitatea din Maryland - Departamentul de Informatică și Inginerie Electrică. Adus pe 2 ianuarie 2017 .

[3] G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, MG Scutellà, Note privind cercetarea operațională , SEU - Serviciul de editare universitar din Pisa

[4] RL Graham și Pavol Hell , Despre istoria problemei arborelui minim , în Annals of the History of Computing , vol. 7, nr. 1, 1985, pp. 43-57, DOI : 10.1109 / MAHC.1985.10011 , MR 783327 .

[5] PHA Sneath, The Application of Computers to Taxonomy , în Journal of General Microbiology , vol. 17, n. 1, 1 august 1957, pp. 201–226, DOI : 10.1099 / 00221287-17-1-201 , PMID 13475686 .

[6] T. Asano , B. Bhattacharya, M. Keil și F. Yao , Algoritmi de grupare bazate pe copacii care se întind pe minim și maxim , al patrulea simpozion anual de geometrie computațională (SCG '88) , vol. 1, 1988, pp. 252-257, DOI : 10.1145 / 73393.73419 .

[7] Yogen K. Dalal și Robert M. Metcalfe, Redirecționarea inversă a pachetelor de difuzare , în Communications of the ACM , vol. 21, n. 12, 1 decembrie 1978, pp. 1040-1048, DOI : 10.1145 / 359657.359665 .

[8] Minsoo Suk și Ohyoung Song, extragerea caracteristicilor curvilinee folosind copaci minimi , în Computer Vision, Graphics și Image Processing , vol. 26, n. 3, 1 iunie 1984, pp. 400–411, DOI : 10.1016 / 0734-189X (84) 90221-4 .

[9] Ernesto Tapia și Raúl Rojas, Recunoașterea expresiilor matematice scrise de mână on-line folosind o construcție minimă a arborelui și dominarea simbolurilor ( PDF ), în Recunoaștere grafică. Progrese și perspective recente , Note de curs în informatică, vol. 3088, Berlin Heidelberg, Springer-Verlag, 2004, pp. 329-340, ISBN 978-3-540-22478-5 .

[10] RM AssunÇão, MC Neves, G. Câmara și C. Da Costa Freitas, Tehnici de regionalizare eficiente pentru unități geografice socio-economice folosind copaci cu întindere minimă , în International Journal of Geographic Information Science , vol. 20, nr. 7, 2006, pp. 797–811, DOI : 10.1080 / 13658810600665111 .

[11] Mantegna, RN (1999). Structura ierarhică pe piețele financiare . European Physical Journal B-Condensed Matter and Complex Systems, 11 (1), 193-197.

[12] Djauhari, M. și Gan, S. (2015). Problema de optimitate a topologiei rețelei în analiza pieței acțiunilor . Physica A: Mecanica statistică și aplicațiile sale, 419, 108-114.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]