Основы теории графов

✶✷ ➹ëàâà ✶✳ Ðåêóððåíòíûå ñîîòíîøåíèÿ è ïðîèçâîäÿùèå ôóíêöèè ✶✳✸✳ ❒åòîä õàðàêòåðèñòè÷åñêèõ ôóíêöèé Ýòîò ìåòîä ïðàêòè÷åñêè ïîëíîñòüþ àíàëîãè÷åí ìåòîäó ðåøåíèÿ ëè✲ íåéíûõ íåîäíîðîäíûõ äèôôåðåíöèàëüíûõ óðàâíåíèé ñ ïîñòîÿííûìè êî✲ ýôôèöèåíòàìè✱ êðàòêî àëãîðèòì âûãëÿäèò òàê✿ ✶✮ ➬àïèñàòü ñîîòâåòñòâóþùåå îäíîðîäíîå ðåêóððåíòíîå óðàâíåíèå ✭ÐÓ✮✿ pn+k an+k + pn+k−1 an+k−1 + · · · + pn an = f ⇒ pn+k an+k + pn+k−1 an+k−1 + · · · + pn an = 0. ✷✮ ➶ûïèñàòü äëÿ íåãî õàðàêòåðèñòè÷åñêîå óðàâíåíèå è íàéòè åãî êîð✲ íè λi pn+k λn+k + pn+k−1 λn+k−1 + · · · + pn+1 λn+1 + pn λn = 0 /: λn ⇒ pn+k λk + pn+k−1 λk−1 + · · · + pn+1 λ + pn = 0. ✸✮ ➶ûïèñàòü ñîãëàñíî ïîëó÷åííûì êîðíÿì λ1 , λ2 , . . . , λk îáùåå ðåøå✲ íèå îäíîðîäíîãî ðåêóððåíòíîãî ñîîòíîøåíèÿ✳ C1 λn1 + · · · + Ck λnk , äëÿ ñëó÷àÿ ðàçëè÷íûõ ïðîñòûõ êîðíåé, C1 λn1 + C2 nλn1 + · · · + Cm nm−1 λn1 + · · · + Ck λnk , äëÿ ñëó÷àÿ êîðíÿ λ1 êðàòíîñòè m. ✹✮ Ïîäîáðàòü ÷àñòíîå ðåøåíèå íåîäíîðîäíîãî ðåêóððåíòíîãî ñîîòíî✲ øåíèÿ ïî âèäó ïðàâîé ÷àñòè ✭îñîáåííî óäîáíî äëÿ ïðàâûõ ÷àñòåé âèäà µn · P (n)✱ P (n) ✕ ìíîãî÷ëåí îò n✮✳ ✺✮ Ïðåäñòàâèòü îáùåå ðåøåíèå íåîäíîðîäíîãî ÐÓ êàê ñóììó îáùåãî ðåøåíèÿ ñîîòâåòñòâóþùåãî îäíîðîäíîãî ÐÓ è ÷àñòíîãî ðåøåíèÿ íåîäíîðîäíîãî ÐÓ✳ ✻✮ Ïîäñòàâèòü íà÷àëüíûå óñëîâèÿ a0 , a1 , ..., ak−1 è ïîëó÷èòü çíà÷åíèÿ êîíñòàíò C1 , ..., Ck ✳ ✶✳✸✳✶✳ Ïðèìåð ðåøåíèÿ Ðàññìîòðèì óæå èçâåñòíûé íàì ïðèìåð a0 a1 an = = = 0, 1, 5an−1 − 6an−2 , n ≥ 2. ✶✳✹✳ ✶✸ Ñïèñîê ëèòåðàòóðû Ïåðåïèøåì óðàâíåíèå èç ðåêóððåíòíîãî ñîîòíîøåíèÿ an+2 = 5an+1 − 6an , òîãäà åãî õàðàêòåðèñòè÷åñêîå óðàâíåíèå λ2 − 5λ + 6 = 0. Ðåøåíèåì óðàâíåíèÿ ÿâëÿþòñÿ λ1 = 2 è λ2 = 3✳ ➚ ðåøåíèå ðåêóððåíòíîãî ñîîòíîøåíèÿ çàïèøåòñÿ ñ íåîïðåäåëåííûìè êîýôôèöèåíòàìè✿ an = C1 · 2n + C2 · 3n . ➘ëÿ îïðåäåëåíèÿ íåèçâåñòíûõ ïîñòîÿííûõ íåîáõîäèìî âîñïîëüçîâàòüñÿ íà÷àëüíûìè óñëîâèÿìè✿ a0 = 0 ⇒ C1 + C2 = 0, a1 = 1 ⇒ 2C1 + 3C2 = 1, îòêóäà C1 = −C2 ⇒ −2C2 + 3C2 = 1 ⇒ C2 = 1, C1 = −1. Òàêèì îáðàçîì✱ íàøëè ðåøåíèå ðåêóððåíòíîãî ñîîòíîøåíèÿ an = 3n − 2n ïðè âñåõ n > 0✳ ✶✳✹✳ Ñïèñîê ëèòåðàòóðû ✶✮ ➚íäåðñîí ➘æ✳ ➚✳ ➘èñêðåòíàÿ ìàòåìàòèêà è êîìáèíàòîðèêà ✿ Ïåð✳ ñ àíãë✳ ✕ ❒✳ ✿ ➮çäàòåëüñêèé äîì ➽➶èëüÿìñ➾✱ ✷✵✵✹✳ ✕ ✾✻✵ ñ✳ ✿ èë✳ ✷✮ Ôóäçèñàâà Ò✳✱ ✃àñàìè Ò✳ ❒àòåìàòèêà äëÿ ðàäèîèíæåíåðîâ✿ Òåî✲ ðèÿ äèñêðåòíûõ ñòðóêòóð✿ Ïåð✳ ñ ÿïîí✳ ✕ ✷✹✵ ñ✳✱ èë✳ ✕ ❒✳ ✿ Ðàäèî è ñâÿçü✱ ✶✾✽✹✳ ✸✮ ❘♦s❡♥ ❑✳ ❉✐s❝r❡t❡ ▼❛t❤❡♠❛t✐❝s ❛♥❞ ■ts ❆♣♣❧✐❝❛t✐♦♥s ✕ ◆❡✇ ❨♦r❦✳ ✿ ❚❤❡ ▼❝●r❛✇✲❍✐❧❧ ❈♦♠♣❛♥✐❡s✱ ■♥❝✳✱ ✷✵✶✷✳ ✕ ✶✵✼✶ ñ✳ ✿ èë✳ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ãðàôîâ ✷✳✶✳ ❰ñíîâíûå îïðåäåëåíèÿ ❞❡❢ ➹ðàôîì G íàçûâàåòñÿ ñîâîêóïíîñòü âåðøèí V è ðåáåð E ✱ ò✳å✳ G = G(V, E)✳ ✃îëè÷åñòâî âåðøèí ãðàôà áóäåì îáîçíà÷àòü ÷èñëîì n✱ ò✳å✳ |V | = n✱ à êîëè÷åñòâî ðåáåð ✕ m✱ ò✳å✳ |E| = m✳ ➹ðàôû áûâàþò îðèåíòèðîâàííûìè ✭îðãðàôû✮ è íåîðèåíòèðîâàííû✲ ìè ✭íåîðãðàôû✮✳ ❮åîðãðàô ❰ðãðàô ➶ íåîðèåíòèðîâàííîì ãðàôå ðåáðî✱ ➶ îðèåíòèðîâàííîì ãðàôå ðåáðî✱ ñîåäèíÿþùåå âåðøèíû vi è vj (i 6= j) ñîåäèíÿþùåå âåðøèíû vi è vj (i 6= j) íå çàâèñèò îò ïîðÿäêà ïåðå÷èñëåíèÿ çàâèñèò îò ïîðÿäêà ïåðå÷èñëåíèÿ âåðøèí✱ ò✳å✳ {vi , vj } = {vj , vi }. âåðøèí✱ ò✳å✳ (vi , vj ) 6= (vj , vi ) è íàçûâàåòñÿ äóãîé✳ ❞❡❢ ➴ñëè â ãðàôå âåðøèíû vi è vj ñîåäèíåíû îáùèì ðåáðîì✱ òî ýòè âåðøèíû íàçûâàþò ñìåæíûìè✱ à ðåáðî è âåðøèíó íàçûâàþò èíöèäåíò✲ íûìè äðóã äðóãó✳ ❞❡❢ ✃îëè÷åñòâî ðåáåð✱ èíöèäåíòíûõ âåðøèíå v íåîðãðàôà íàçûâàåòñÿ ñòåïåíüþ ýòîé âåðøèíû è îáîçíà÷àåòñÿ d(v)✳ ➹ðàô✱ â êîòîðîì ñòåïåíè âñåõ âåðøèí ðàâíû ìåæäó ñîáîé✱ íàçûâàåòñÿ ðåãóëÿðíûì✳ ❐åììà✿ ➶ íåîðãðàôå X d(v) = 2|E|. v∈V ✃îëè÷åñòâî âåðøèí íå÷åòíîé ñòåïåíè â ãðàôå ÷åòíî✳ ➘ëÿ îðèåíòèðîâàííûõ ãðàôîâ îïðåäåëÿþò ïîëóñòåïåíü èñõîäà âåðøèíû d+ (v) = |e : beg(e) = v| è ïîëóñòåïåíü çàõîäà âåðøèíû d− (v) = |e : end(e) = v|✳ Ñëåäñòâèå✿ ❞❡❢ ✶✺ ✶✻ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ãðàôîâ Ðèñ✳ ✷✳✶✳ Ïðèìåðû íåîðãðàôà è îðãðàôà✳ ❐åììà✿ ➶ îðãðàôå X v d− (v) = X d+ (v). v ❞❡❢ ✃îíå÷íûì ãðàôîì G íàçûâàåòñÿ ãðàô✱ â êîòîðîì ìíîæåñòâà V è E ✕ êîíå÷íû✳ Ñëåäóåò çàìåòèòü✱ ÷òî áîëüøèíñòâî ðàññìàòðèâàåâûõ íàìè ãðàôîâ ✕ êîíå÷íû✳ ❞❡❢ Ïðîñòûì ãðàôîì G íàçûâàåòñÿ ãðàô✱ â êîòîðîì íåò ïåòåëü è êðàòíûõ ð➻áåð✳ ➚ ãðàô✱ ñîäåðæàùèé ïåòëè è êðàòíûå ð➻áðà✱ íàçûâàåòñÿ ìóëüòèãðàôîì✳ ❞❡❢ ➮çîëèðîâàííîé âåðøèíîé â íåîðèåíòèðîâàííîì ãðàôå íàçûâàþò âåðøèíó ñòåïåíè ✵✳ ❞❡❢ Ïîëíûé ãðàô ✕ ãðàô✱ â êîòîðîì êàæäàÿ ïàðà ðàçëè÷íûõ âåðøèí ñìåæíà✳ Ïîëíûé ãðàô ñ n âåðøèíàìè èìååò n(n − 1)/2 ð➻áåð è îáîçíà✲ ÷àåòñÿ Kn ✳ ❞❡❢ ➘âóäîëüíûé ãðàô ✕ ãðàô✱ ìíîæåñòâî âåðøèí êîòîðîãî ìîæíî ðàçáèòü íà äâå ÷àñòè òàêèì îáðàçîì✱ ÷òî êàæäîå ðåáðî ãðàôà ñîåäèíÿåò êàêóþ✲òî âåðøèíó èç îäíîé ÷àñòè ñ êàêîé✲òî âåðøèíîé äðóãîé ÷àñòè✱ òî åñòü íå ñóùåñòâóåò ðåáðà✱ ñîåäèíÿþùåãî äâå âåðøèíû èç îäíîé è òîé æå ÷àñòè✳ ➘âóäîëüíûé ãðàô ñ n âåðøèíàìè â îäíîé äîëå è m âî âòîðîé îáîçíà÷àåòñÿ Kn,m ✳ ❞❡❢ ➹ðàô✱ â êîòîðîì êàæäîìó ðåáðó ïðèïèñàíî ïîëîæèòåëüíîå âå✲ ùåñòâåííîå ÷èñëî✱ íàçûâàåòñÿ âçâåøåííûì✳ ❞❡❢ ➹ðàô íàçûâàåòñÿ ïëàíàðíûì✱ åñëè åãî ìîæíî èçîáðàçèòü íà ïëîñ✲ êîñòè áåç ïåðåñå÷åíèé ðåáåð✳ ✷✳✶✳ ❰ñíîâíûå îïðåäåëåíèÿ ✶✼ Ðèñ✳ ✷✳✷✳ Ïðèìåð âçâåøåííîãî ãðàôà✳ ✷✳✶✳✶✳ ➮çîìîðôèçì ãðàôîâ ❞❡❢ ➹ðàôû G1 (V1 , E1 ) G2 (V2 , E2 ) íàçûâàþòñÿ èçîìîðôíûìè✱ åñëè π : V1 → V2 ✱ êîòîðàÿ ïåðåâîäèò ìíîæåñòâî ðåáåð ïåðâîãî ãðàôà âî ìíîæåñòâî ðåáåð âòîðîãî ãðàôà✱ ò✳å✳ {u, v} ∈ E1 ðàâíîñèëüíî {π(u), π(v)} ∈ E2 ✳ è ñóùåñòâóåò òàêàÿ áèåêöèÿ ➮çîìîðôèçì ñîõðàíÿåò âñå ñâîéñòâà ãðàôîâ✱ êîòîðûå âûðàæàþòñÿ â òåðìèíàõ âåðøèí è ðåáåð è íå èñïîëüçóþò äîïîëíèòåëüíîé èíôîðìàöèè î ìíîæåñòâå âåðøèí✳ Òàêèå ñâîéñòâà íàçûâàþòñÿ èíâàðèàíòíûìè✳ ✷✳✶✳✷✳ Ïîäãðàôû ❞❡❢ ðîì Ïîäãðàôîì ãðàôà E ⊂E ′ è V ⊂ V✳ ′ G(V, E) íàçûâàåòñÿ ãðàô Ò✳å✳ ëþáàÿ ÷àñòü ãðàôà G✱ G′ (V ′ , E ′ ) ✱ â êîòî✲ ÿâëÿþùàÿñÿ ãðàôîì✱ íàçûâàåòñÿ ïîäãðàôîì ýòîãî ãðàôà✳ ❞❡❢ ➮íäóöèðîâàííûì ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ïîäãðàô✱ ïî✲ ñòðîåííûé íà ïîäìíîæåñòâå âåðøèí è âñåõ ðåáðàõ ãðàôà G ìåæäó ýòèìè âåðøèíàìè✳ ❞❡❢ ❰ñòîâíûì ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ïîäãðàô✱ ïîñòðîåí✲ íûé íà ìíîæåñòâå âñåõ âåðøèí è íåêîòîðîãî êîëè÷åñòâà ðåáåð èñõîäíîãî ãðàôà ❞❡❢ G✳ ➘îïîëíèòåëüíûì ãðàôîì ùèé âñå âåðøèíû ãðàôà ãðàôå G✳ G Ḡ ãðàôà G íàçûâàåòñÿ ãðàô✱ ñîäåðæà✲ è âñå ðåáðà✱ êîòîðûõ íå áûëî â èñõîäíîì ✶✽ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ãðàôîâ ✷✳✶✳✸✳ Öèêëû â ãðàôå ❞❡❢ Ïîñëåäîâàòåëüíîñòü äóã (vi1 , vi2 ), (vi2 , vi3 ), . . . , (vik−1 , vik )✱ òàêèõ✱ ÷òî êîíåö ëþáîé äóãè êðîìå ïîñëåäíåé ñîâïàäàåò ñ íà÷àëîì ñëåäóþ✲ ùåé äóãè✱ íàçûâàåòñÿ ïóòåì â ãðàôå✳ Ïðè ýòîì áóäåì ïðåäïîëàãàòü✱ ÷òî âñå âåðøèíû äóã ïóòè✱ êðîìå✱ âîçìîæíî✱ ïåðâîé è ïîñëåäíåé✱ ðàçëè÷íû✳ ×èñëî äóã ïóòè íàçûâàåòñÿ åãî äëèíîé✳ Ïóòü îáîçíà÷àåòñÿ L(vi1 , vik )✱ ãäå âåðøèíû vi1 è vik íàçûâàþòñÿ íà÷àëîì è êîíöîì ïóòè✱ à îñòàëüíûå âåð✲ øèíû ✕ ïðîìåæóòî÷íûìè✳ ➴ñëè ïóòü â ãðàôå èìååò ñîâïàäàþùèå íà÷àëî è êîíåö✱ òî îí íàçûâàåòñÿ öèêëîì✳ Ýéëåðîâ öèêë ➴ñëè ãðàô èìååò öèêë ✭íå îáÿçàòåëüíî ïðîñòîé✮✱ ñîäåðæàùèé âñå ðåáðà ãðàôà ïî îäíîìó ðàçó✱ òî òàêîé öèêë íàçûâàåòñÿ ýéëåðîâûì öèêëîì✱ à ãðàô íàçûâàåòñÿ ýéëåðîâûì ãðàôîì✳ ➴ñëè ãðàô èìååò öåïü ✭íå îáÿçàòåëüíî ïðîñòóþ✮✱ ñîäåðæàùóþ âñå ðåáðà ïî îäíîìó ðàçó✱ òî òàêàÿ öåïü íàçûâàåòñÿ ýéëåðîâîé öåïüþ✱ à ãðàô íàçûâàåòñÿ ïîëóýéëåðîâûì ãðàôîì✳ Ýéëåðîâ öèêë ñîäåðæèò íå òîëüêî âñå ðåáðà ✭ïî îäíîìó ðàçó✮✱ íî è âñå âåðøèíû ãðàôà ✭âîçìîæíî ïî íåñêîëüêî ðàç✮✳ ßñíî✱ ÷òî ýéëåðîâûì ìîæåò áûòü òîëüêî ñâÿçíûé ãðàô✳ ❰÷åâèäíî✱ ÷òî íå âñå äàæå ñâÿçíûå ãðàôû ýéëåðîâû✳ Ýéëåðîâ ãðàô ìîæíî íàðèñîâàòü íà áóìàãå✱ íå îòðû✲ âàÿ îò íåå êàðàíäàøà✳ ➶ûøåîïðåäåëåííûå ïîíÿòèÿ ðàñïðîñòðàíÿþòñÿ àíàëîãè÷íî íà ìóëüòèãðàôû✳ ❐åîíàðä Ýéëåð ✭✶✼✵✼ ✕ ✶✼✽✸✮ ïåðâûì â ñâîåé çíàìåíèòîé çàäà÷å î ✃➻✲ íèãñáåðãñêèõ ìîñòàõ ðàññìîòðåë âîïðîñ î ñóùåñòâîâàíèè òàêèõ öèêëîâ â ãðàôàõ✳ Óòâåðæäåíèå✿ ➹ðàô✱ â êîòîðîì ëþáàÿ ïàðà âåðøèí ñâÿçàíà íåêî✲ òîðîé ïîñëåäîâàòåëüíîñòüþ ðåáåð✱ ÿëÿåòñÿ ýéëåðîâûì òîãäà è òîëüêî òîãäà✱ êîãäà âñå åãî âåðøèíû èìåþò ÷åòíóþ ñòåïåíü✳ Ïðèìåð✿ ❮àðèñóéòå ãðàô G(V, E) ñ ìíîæåñòâîì âåðøèí V = {a, b, c, d, e} è ìíîæåñòâîì ðåáåð E = {ab, ae, bc, bd, ce, de}✳ ➶ûïèøèòå åãî ìàòðèöó ñìåæíîñòè✳ ❞❡❢ ➹àìèëüòîíîâ öèêë ➴ñëè ãðàô èìååò öèêë✱ ïðîõîäÿùèé ÷åðåç êàæäóþ âåðøèíó ãðà✲ ôà ðîâíî îäèí ðàç✱ òî òàêîé öèêë íàçûâàåòñÿ ãàìèëüòîíîâûì öèêëîì✱ à ãðàô íàçûâàåòñÿ ãàìèëüòîíîâûì ãðàôîì✳ ➹àìèëüòîíîâû ãðàôû ñëóæàò ìîäåëüþ ïðè ñîñòàâëåíèè ðàñïèñàíèÿ äâèæåíèÿ ïîåçäîâ✱ äëÿ òåëåêîììóíèêàöèîííûõ ñåòåé è ò✳ä✳ ➶ îòëè÷èå îò ❞❡❢ ✷✳✷✳ ✶✾ Ñïîñîáû çàäàíèÿ ãðàôîâ çàäà÷è Ýéëåðà✱ ïðîñòîãî êðèòåðèÿ ãàìèëüòîíîâîñòè ãðàôà ïîêà íå èç✲ âåñòíî✳ Òåì íå ìåíåå✱ ìíîãèå ãðàôû ÿâëÿþòñÿ ãàìèëüòîâûìè✳ ❮àïðèìåð✱ ïîëíûå ãðàôû Kn ✱ ãäå n ✕ ÷èñëî âåðøèí✱ â êîòîðûõ ëþáàÿ ïàðà âåðøèí ñîåäèíåíà ðåáðîì✳ ✷✳✶✳✹✳ Ñâÿçíîñòü ãðàôà ❮åîðãðàô G íàçûâàåòñÿ ñâÿçíûì✱ åñëè èç ëþáîé åãî âåðøèíû✱ äâèãàÿñü ïî ðåáðàì✱ ìîæíî ïîïàñòü â ëþáóþ äðóãóþ✳ ❞❡❢ ✃îìïîíåíòà ñâÿçíîñòè íåîãðàôà G ✕ ìàêñèìàëüíûé ñâÿçíûé ïîä✲ ãðàô ãðàôà G✳ Òåîðåìà✿ ➶ ñâÿçíîì íåîðãðàôå ñ n âåðøèíàìè íå ìåíüøå (n − 1) ðåáåð✳ ❞❡❢ ❰ðãðàô G íàçûâàåòñÿ ñèëüíî ñâÿçíûì✱ åñëè èç ëþáîé åãî âåð✲ øèíû✱ äâèãàÿñü ïî ðåáðàì â ïðàâèëüíîì íàïðàâëåíèè✱ ìîæíî ïîïàñòü â ëþáóþ äðóãóþ✳ ❞❡❢ ❰ðãðàô G íàçûâàåòñÿ ñëàáî ñâÿçíûì✱ åñëè ñâÿçåí íåîðãðàô✱ ïî✲ ëó÷àåìûé èç îðãðàôà óäàëåíèåì îðèåíòàöèè ðåáåð✳ ❞❡❢ ✷✳✶✳✺✳ ➘åðåâüÿ ❞❡❢ ÷àòü T ✳ ➘åðåâî ✕ ñâÿçíûé àöèêëè÷åñêèé ãðàô✳ ➘åðåâî ïðèíÿòî îáîçíà✲ ➶åðøèíà ãðàôà✱ èìåþùàÿ ñòåïåíü ✶✱ íàçûâàåòñÿ âèñÿ÷åé✳ ➮íîãäà â ãðàôå âûäåëÿþò îñîáóþ âåðøèíó ✕ êîðåíü✱ òîãäà âèñÿ÷èå âåðøèíû✱ îòëè÷íûå îò êîðíÿ íàçûâàþòñÿ ëèñòüÿìè✳ ❞❡❢ ❐åñ ✕ ýòî ãðàô✱ êàæäàÿ êîìïîíåíòà ñâÿçíîñòè êîòîðîãî ÿâëÿåòñÿ äåðåâîì✳ ❞❡❢ ✷✳✷✳ Ñïîñîáû çàäàíèÿ ãðàôîâ ❮à ïðàêòèêå ãðàôû ÷àñòî óäîáíî çàäàâàòü ïðè ïîìîùè ìàòðèö✳ ✶✮ ìàòðèöà ñìåæíîñòè A = (aij ) , 1 6 i, j 6 n✱ ãäå aij = ( 0, ∄(vi , vj ), 1, ∃(vi , vj ). ✷✵ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ãðàôîâ ✷✮ ìàòðèöà èíöèäåíòíîñòè B = (bij ) , 1 6 i 6 n, 1 6 j 6 m✱ ãäå ❮åîðãðàô ❰ðãðàô  (  0, vi íå èíöèäåíòíà ej , 0, vi íå èíöèäåíòíà ej , bij = bij = 1, vi íà÷àëî ej ,  1, vi èíöèäåíòíà ej .  −1, vi êîíåö ej . ✸✮ ìàòðèöà âåñîâ C = (cij ) , 1 6 i, j 6 n✱ ãäå ( âåñ (vi , vj ), ∃(vi , vj ), cij = 0, ∄(vi , vj ). ✹✮ ìàòðèöà ðàññòîÿíèé D = (dij ) , 1 6 i, j 6 n✱ ãäå ( äëèíà (vi , vj ), ∃(vi , vj ), dij = ∞, ∄(vi , vj ). ✷✳✸✳ ❒èíèìàëüíîå îñòîâíîå äåðåâî ❞❡❢ ❰ñòîâíîå äåðåâî ✕ àöèêëè÷åñêèé ñâÿçíûé îñòîâíûé ïîäãðàô äàí✲ íîãî ñâÿçíîãî íåîðèåíòèðîâàííîãî ãðàôà✳ ❞❡❢ ❒èíèìàëüíîå îñòîâíîå äåðåâî ãðàôà G = (V, E) ✕ ýòî åãî àöèê✲ ëè÷åñêèé ñâÿçíûé ïîäãðàô✱ â êîòîðûé âõîäÿò âñå åãî âåðøèíû✱ îáëàäà✲ þùèé ìèíèìàëüíûì ñóììàðíûì âåñîì ðåáåð✳ ➬àìåòèì✱ ÷òî ãðàô ìîæåò ñîäåðæàòü íåñêîëüêî ìèíèìàëüíûõ îñòîâíûõ äåðåâüåâ✳ ✷✳✸✳✶✳ ➚ëãîðèòì ✃ðàñêàëà íàõîæäåíèÿ ìèíèìàëüíîãî îñòîâíîãî äåðåâà âçâåøåííîãî íåîðãðàôà ✶✮ ➶êëþ÷èòü â ìèíèìàëüíîå îñòîâíîå äåðåâî âñå âåðøèíû èñõîäíîãî ãðàôà✳ ✷✮ ➶êëþ÷èòü ðåáðî ñ íàèìåíüøèì âåñîì â ìèíèìàëüíîå îñòîâíîå äå✲ ðåâî✳ ✸✮ Ñðåäè îñòàâøèõñÿ ðåáåð íàéòè ðåáðî ñ íàèìåíüøèì âåñîì è✱ åñëè åãî äîáàâëåíèå â äåðåâî íå ïðèâîäèò ê îáðàçîâàíèþ öèêëà✱ âêëþ✲ ÷èòü åãî â äåðåâî✳ ✹✮ Ïîâòîðÿòü øàã ✸✱ ïîêà ãðàô íå ñòàíåò ñâÿçíûì✳ ✷✳✸✳ ✷✶ ❒èíèìàëüíîå îñòîâíîå äåðåâî Ðèñ✳ ✷✳✸✳ Ïðèìåð âçâåøåííîãî ãðàôà✳ ✷✳✸✳✷✳ ➚ëãîðèòì Ïðèìà íàõîæäåíèÿ ìèíèìàëüíîãî îñòîâ✲ íîãî äåðåâà âçâåøåííîãî íåîðãðàôà ✶✮ ➶ûïèñàòü ìàòðèöó ðàññòîÿíèé✳ ✷✮ ❮àéòè â ìàòðèöå ìèíèìàëüíûé ýëåìåíò dlk ✱ âêëþ÷èòü â äåðåâî ðåá✲ ðî {vl , vk }✳ ➶û÷åðêíóòü l✲óþ è k ✲óþ ñòðîêè✱ ïîìåòèòü l✲ûé è k ✲ûé ñòîëáöû✳ ✸✮ ➶ ïîìå÷åííûõ ñòîëáöàõ ñðåäè íåâû÷åðêíóòûõ ýëåìåíòîâ íàéòè ìè✲ íèìàëüíûé ýëåìåíò íóòü p✲óþ dpq ✳ ➶êëþ÷èòü â äåðåâî ðåáðî ñòðîêó è ïîìåòèòü p✲ûé {vp , vq }❀ âû÷åðê✲ ñòîëáåö✳ ✹✮ Ïîâòîðÿòü øàã ✸✱ ïîêà íå áóäóò âû÷åðêíóòû âñå ñòðîêè ✭ïîìå÷åíû âñå ñòîëáöû✮✳ ✷✷ ➹ëàâà ✷✳ ❰ñíîâû òåîðèè ãðàôîâ ✷✳✹✳ ✃ðàò÷àéøåå ðàññòîÿíèå ìåæäó âåðøèíà✲ ìè â îðãðàôå ✷✳✹✳✶✳ ✃ðàò÷àéøåå ðàññòîÿíèå ìåæäó çàäàííûìè ïà✲ ðàìè âåðøèí✳ ➚ëãîðèòì ➘åéêñòðû ➘ëÿ íàõîæäåíèÿ êðàò÷àéøåãî ðàññòîÿíèÿ îò âåðøèíû p äî âåðøèíû q â îðãðàôå ïðèìåíÿåòñÿ àëãîðèòì ➘åéêñòðû✱ êîòîðûé çàêëþ÷àåòñÿ â ñëåäóþùåì✿ ✶✮ Ïðèñâîèòü âðåìåííûå ìåòêè âåðøèíàì ✕ íà÷àëüíîé âåðøèíå ìåòêó 0✱ à âñåì îñòàëüíûì ìåòêó ∞✿ ( 0, åñëè v = p, l(v) := ∞, åñëè v 6= p, ✭ò✳å✳ ðàññòîÿíèå îò âåðøèíû äî ñàìîé ñåáÿ ðàâíî 0✱ à äî âñåõ îñòàëü✲ íûõ âåðøèí ïîêà íåèçâåñòíî è ïðèíèìàåòñÿ ðàâíûì ∞✮✳ ❒åòêó âåðøèíû p ñ÷èòàòü ïîñòîÿííîé❀ â êà÷åñòâå ðàáî÷åé âåðøèíû s ïðèíÿòü âåðøèíó p✿ s := p. ✷✮ ➶ûïèñàòü ìíîæåñòâî Γ+ (s) ✕ ìíîæåñòâî âåðøèí✱ â êîòîðûå âåäóò äóãè èç âåðøèíû s✳ ➘ëÿ êàæäîé âåðøèíû èç ýòîãî ìíîæåñòâà îá✲ íîâèòü âðåìåííûå ìåòêè✿ l(v) := min {l(v); l(s) + csv }. + v∈Γ (s) ➮ç âåðøèí ñ âðåìåííûìè ìåòêàìè âûáðàòü òó✱ ìåòêà êîòîðîé íàè✲ ìåíüøàÿ✱ ò✳å✳ t | l(t) = min{l(v)}; v∈V ìåòêó ýòîé âåðøèíû ñäåëàòü ïîñòîÿíííîé✱ âûáðàòü åå â êà÷åñòâå ðàáî÷åé âåðøèíû s := t✳ ✸✮ ➴ñëè s = q çàêîí÷èòü àëãîðèòì✱ ò✳ê✳ íàéäåíî êðàò÷àéøåå ðàññòî✲ ÿíèå äî êîíå÷íîé âåðøèíû❀ â ïðîòèâíîì ñëó÷àå ïåðåéòè ê øàãó ✷✳ ➬àìå÷àíèå✿ Ýòîò àëãîðèòì òàêæå ïîçâîëÿåò íàõîäèòü êðàò÷àéøåå ðàññòîÿíèå îò çàäàííîé âåðøèíû äî âñåõ îñòàëüíûõ✳ ➶ ýòîì ñëó÷àå àë✲ ãîðèòì ñëåäóåò ïðîäîëæàòü äî òåõ ïîð✱ ïîêà âñå âåðøèíû îðãðàôà íå ïîëó÷àò ïîñòîÿííûå ìåòêè✳ ✷✳✹✳ ✃ðàò÷àéøåå ðàññòîÿíèå ìåæäó âåðøèíàìè â îðãðàôå Ðèñ✳ ✷✳✹✳ Ïðèìåð âçâåøåííîãî ãðàôà✳ ✷✸