Coeden rhychwantu leiaf

Graff planar a'i goeden rhychwantu leiaf. Mae pob ymyl wedi'i labelu â'i bwysau.

Coeden rhychwantu leiaf yw is-set ymylon o graff gysylltiedig anghyfeiriedig gyda phwysau ymylon. Y goeden rhychwantu leiaf yw'r set ymylon sy'n cysylltu pob un o'r fertigau i'w gilydd, heb gylchredau, sydd â chyfanswm pwysau ymyl lleiaf posib. Mae gan bob graff (nid yn anghenrheidol yn gysylltiedig) anghyfeiriedig gyda phwysau ymylon goedwig rychwantu leiaf, hynny undeb y coed rhychwantu lleiaf pob un o'i gydrannau cysylltiedig.^[1]

Mae nifer o ddefnyddiau ar gyfer coed rhychwantu lleiaf. Un enghraifft fyddai cwmni telathrebu sy'n ceisio gosod cebl mewn cymdogaeth newydd. Os gall y cwmni ond gladdu'r cebl ar hyd rhai llwybrau yn unig (ee ffyrdd), yna mae gan ryw graff fertigau (ee tai) wedi'u cysylltu gan y llwybrau hynny. Efallai bydd gosod ceblau ar hyd rhai o'r llwybrau'n ddrytach, oherwydd eu bod yn hirach, neu'n mae angen eu claddu'n ddyfnach; byddai'r llwybrau hyn yn cael eu cynrychioli gan ymylon â phwysau mwy. Does dim gofyniad i hyd ymyl ufuddhau i reolau geometreg arferol megis yr anhafaledd triongl . Byddai coeden rhychwantu ar gyfer y graff hwn yn is-set o'r llwybrau hynny heb gylchredau sy'n cysylltu pob tŷ; efallai y bydd sawl coeden rychwantu yn bosibl. Y goeden rhychwantu leiaf yw'r un gyda'r cyfanswm cost isaf, sy'n cynrychioli'r llwybr lleiaf drud ar gyfer gosod y cebl.

Priodweddau

Mae'r ffigur hwn yn dangos y gallai fod mwy nag un goeden rychwantu leiaf mewn graff. Yn y ffigur, mae'r ddwy goeden o dan y graff yn ddau bosibilrwydd o isafswm coeden sy'n rhychwantu'r graff cyntaf.

• Os oes gan graff n fertig, yna mae gan bob coeden rhychwantu n − 1 ymyl.
• Efallai bod sawl coeden rhychwantu leiaf gyda'r un cyfanswm pwysau.
• Os oes gan bob ymyl pwys unigryw, yna ond un goeden rhychwantu leiaf sy'n bodoli.^[2]
• Os yw pwysau pob ymyl yn bositif, yna'r goeden rhychwantu leiaf yw'r is-graff cost leiaf.

Algorithm Kruskal

Demo o algorithm Kruskal ar gyfer graff lle mae pob fertig wedi ei gysylltu â phob fertig arall gyda phwysau yn hafal i'r pellter Ewclidaidd.

Un algorithm barus ar gyfer canfod coeden rhychwantu leiaf graff ${\displaystyle G}$ yw algorithm Kruskal.^[3] Camau'r algorithm yw:

1. Ystyriwch y set of fertigau'r graff fel graff ${\displaystyle {\tilde {G}}}$ sydd â dim ymylon, hynny yw cydran gysylltiedig wahanol ar gyfer pob fertig.
2. Rhestrwch yr ymylon yn nhrefn eu pwysau. Mae'r rhain yn aros mewn ciw gyda'r ymyl â'r pwysau lleiaf ar flaen y ciw.
3. Tra bod gan ${\displaystyle {\tilde {G}}}$ mwy nag un gydran gysylltiedig cymerwch yr ymyl ar flaen y ciw. Os yw ychwanegu'r ymyl hyn i ${\displaystyle {\tilde {G}}}$ yn cyfuno dwy gydran gysylltiedig (hynny yw ddim yn achosi cylchred), ychwanegwch yr ymyl hyn i ${\displaystyle {\tilde {G}}}$. Fel arall symudwch ymlaen i'r ymyl nesaf yn y ciw.

Algorithmau eraill gellir eu defnyddio yw algorithm Borůvka^[4], ac algorithm Prim^[5].

Cyfeiriadau

1. Bollobas, Bela (6 Rhagfyr 2012). Graph Theory: An Introductory Course (yn Saesneg). Springer Science & Business Media. ISBN 978-1-4612-9967-7.
2. "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. Cyrchwyd 4 Ebrill 2018.
3. "Kruskal's Algorithm". www-m9.ma.tum.de. Archifwyd o'r gwreiddiol ar 2019-10-02. Cyrchwyd 2019-12-08.
4. Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm", Journal of the Association for Computing Machinery 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431, https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf.
5. "Prim's Algorithm". www-m9.ma.tum.de. Archifwyd o'r gwreiddiol ar 2019-10-02. Cyrchwyd 8 Rhagfyr 2019.