задачата за намиране на минималната обхваща дърво графиката

Приложни проблеми на теория графика

Този проблем възниква при проектирането на електропроводи, газопроводи, пътища и т.н. когато е необходимо да се свърже определен система централен канал (връзки), така че всеки два центрове са свързани директно или чрез други канали, и че общата дължина (себестойност) на комуникационни канали е минимална.

Определение. Графиката се нарича балансиран ако ръбове или дъги се дължат на определени номера (тегло).

Определение. Опорна обхваща дърво или графика е свързан подграф на цикъла, без да съдържа всички върхове на оригиналния графиката. Подграф съдържа част или всички ръбове на оригиналната графиката.

В една колона може да се изолира от много ядра (фигура 5.1.).

Фигура 5.1 Различни скелети графика K3.3

Проблемът на минималната обхваща дървото е формулиран, както следва: в суспендира свързан графика да намерите скелет на минимално тегло, т.е. скелета, общото тегло на чиито краища е минимална.

Помислете за Kruskal алгоритъм за построяване на минималната обхваща дървото на графиката. Скелетът е изградена постепенно се добавя един ръб на всяка стъпка. Алгоритъмът използва две правила.

1) първият край на сърцевината - минимум ръба на тегло в оригиналната графиката.

2) Ако на скелета вече е добавен аз (и имат минимален ръб тегло между ръбовете, които все още не са включени в рамката
и не образуват цикли вече добавени ръбове.

Фигура 5.2 Минимална скелет

Пример 5.1. Виж минималната обхваща дърво в графика (Фигура 5.2.).

Изграждане на ядрото ще започне с ръбовете (v1, VJ), тъй като тя е най-малко тегло (можете да започнете с ребрата (V2, v5)). Как да се присъедините към ребрата на ядрото:

Имайте предвид, че ребрата (v2, v3), (v1, v5) са не са включени в рамката, въпреки че те са имали по-малко тегло от реброто (v4, v5), тъй като те образуват вериги вече са включени ребра.

Друг пример за прилагане на този проблем. Да предположим, че са дадени много летища, и трябва да се определи минималния (сумата от разстоянията), набор от полети, които биха позволили да летят от всяко летище и да е. Решението на този проблем ще бъде минималната обхваща дървото на пълен граф на разстоянията между летищата

След това, ние ще изброим само задачи, които се появяват в теорията на графите и в практиката. Алгоритми за тяхното решаване са извън обхвата на този курс.