Крускалов алгоритам - изградња оптималног оквира

У раном геометар 19. века Акоб Штајнер из Берлина поставио задатак како да повеже три села, тако да је њихова дужина је најкраћа. Касније, он је укратко проблем: потребно је пронаћи тачку у равни, удаљеност од њега да н друге тачке биле су најниже. У 20. веку, она наставља да ради на овој теми. Одлучено је да се неколико тачака и спојите их на такав начин да је растојање између њих је био најкраћи. Ово све је посебан случај проблема се проучава.

"Похлепни" алгоритам

Крускалов алгоритам односи на "похлепни" алгоритам (назива градијент). Суштина оне - највиши победа на сваком кораку. Не увек, "похлепне" алгоритми дају најбоље решење за проблем. Постоји теорија, показује да је у њиховој примени на конкретне задатке дају оптимално решење. То је теорија матроидс. Крускалов алгоритам односи на такве проблеме.

Проналажење минималну масе трупова

Виевед алгоритам конструише оквира оптималну пребројавање. Проблем је у томе што следи. Дан ундирецтед график без паралелних ивица и петљама, а сет рубова даје функцију тежине в, која додељује број сваком ЕДГЕ Е - тежина ребро - В (е). Маса сваке подскуп већег броја ребара је збир пондера својих ивица. Обавези да пронађу костур мале тежине.

опис

Крускалов алгоритам ради. Прво, сви ивице почетног графа су распоређени у растућем редоследу од тежине. У почетку, оквир не садржи никакве ребра, али укључује све темена. Након следећем кораку алгоритма на већ изграђеном дијелу трупа, што је простире шума, додаје се једна ивица. Није изабран произвољно. Све ивице графа, не припадају кадру, може се назвати црвено и зелено. На врху сваке црвеним ивицама су у истој компоненти у изградњи шумског повезивање, као и зелени врхови - другачији. Стога, ако додате у црвеном ивицом, постоји циклус, а уколико зелена - као примљени након овог корака су дрвене компоненте повезане ће бити мањи од један. Према томе је конструкција не може додати ни црвени предност, али било зелено ивица може да се дода да се у шуму. И додаје зеленог ивицу са минималном тежином. Резултат представља оквир минималном тежином.

извршење

Означавају тренутни шуму Ф Она дели скуп темена у области повезивања (њихове синдикалне облике Ф, и они су раздвојени). На обе стране црвених темена леже у једном комаду. Парт (к) - функција која за сваког врха к враћа део имена, припада к. Уните (к, и) - процедура која гради нову партицију, која се састоји од комбиновања делова Кс и И и све остале делове. Нека је н - број ивица. Сви ови концепти су укључени у крускалов алгоритам. implementacija:

1. Распоред све ивице графа од 1. до н-тх растуће тегови. (Аи, би - и кроз теме бројем ивица).

2. фор и = 1 то н до.

3. к: = Парт (аи).

4. и: = Парт (би).

5. Ако к не једнака и затим Уните (к, и), укључити са ивице Ф И Број.

исправност

Лет Т - оквир оригиналног графикона конструисан коришћењем алгоритма и С Крускал - његова произвољна фраме. Морамо доказати да В (т) није већа од В (М).

Лет М - плурализам пераја С, П - Плурални пераја Т. Ако С није једнако Т, онда постоји оквир ребро ет Т, неприпадања С. С. ет граниче са циклус се зове Ц. Ц уклонити из било које ивице ЕС, припадност С добијамо нови оквир, јер су ивице и темена је исти. Његова тежина није већа од в (С), будући в (ет) не в (ес) у енергије Круска алгоритма. Ова операција (замена Т С ребра ребара) ће се понављати све док примају Т. тежину сваког накнадног примљених оквир није већа од претходне тежине, што подразумева да в (Т) није већа од в (С).

Чврстина крускалов алгоритам следи из теореме Радо-Едмондса на матроидс.

Примери апликација Крускал алгоритам

Дан графикон са чворова а, б, ц, д, е и ребрима (а, б), (а, е), (б, ц), (б, е), (ц, д), (ц, е) (д, е). Тежине ивица су приказани у табели и на слици. У почетку, изградња шумских П садржи све темена графа и не садржи никакве ребра. Алгоритхм Крускал фирст додати ребро (а, е), јер га тежински имао најниже, а темена А и Е су у различитим компонентама повезаност дрвне Ф (Риб (а, е) зелен), а затим је ребро (ц, д), јер да барем ивица тежина граф ивице не припадају Ф, и то је зелено, затим исти разлози акумулирати ивицу (а, б). Али ивице (Б, Е) је усвојен, иако је и минимална тежина преосталих ивица, јер је црвено: темена Б и Е припадају истој компоненти шума повезивање Ф, који је, ако се томе дода Ф ивице (Б, Е), формиран циклус. Затим дода зелену ивицу (Б, Ц), се преноси црвени ивицу (Ц, Е) и затим д, е. Тако, додају ивице секвенцијално (а, е), (ц, д), (а, б), (б, ц). Од нихера оптималан оквир и састоји се од оригиналног графикона. Дакле, у овом случају ради алгоритам Крускал. Пример је приказан.

Фигура приказује график, који се састоји од два спојена компоненте. Подебљане линије означавају оптималне ребра рама (зелено) конструирају користећи Крускал алгоритам.

На горњој слици је приказан оригинални графикон, и дно - скелет минималне тежине, изграђен за њега помоћу алгоритма.

Редослед додатих ребара (1.6); (0,3), (2,6) или (2,6), (0,3) - није важно; (3,4); (0,1), (1,6) или (1,6), (0,1), такође царе (5,6).

Крускалов алгоритам налази практичну примену, на пример, за оптимизацију заптивач комуникације, путеве у новим стамбеним насељима локалитета у свакој земљи, као иу другим случајевима.