Постановка лабораторной работы по теории графов
Ïîñòàíîâêà
ëàáîðàòîðíîé
ðàáîòû ïî
òåîðèè
ãðàôîâ
(àëãîðèòìû
è ïðîãðàììû)
1.
Ââåäåíèå
Â
ïîñëåäíåå
âðåìÿ
èññëåäîâàíèÿ
â îáëàñòÿõ,
òðàäèöèîííî
îòíîñÿùèõñÿ
ê äèñêðåòíîé
ìàòåìàòèêå,
çàíèìàþò
âñå áîëåå çàìåòíîå
ìåñòî.
Íàðÿäó ñ
òàêèìè
êëàññè÷åñêèìè
ðàçäåëàìè
ìàòåìàòèêè,
êàê ìàòåìàòè÷åñêèé
àíàëèç,
äèôôåðåíöèàëüíûå
óðàâíåíèÿ, â
ó÷åáíûõ
ïëàíàõ
ñïåöèàëüíîñòè
"Ïðèêëàäíàÿ
ìàòåìàòèêà"
è ìíîãèõ
äðóãèõ ñïåöèàëüíîñòåé
ïîÿâèëèñü
ðàçäåëû ïî
ìàòåìàòè÷åñêîé
ëîãèêå,
àëãåáðå,
êîìáèíàòîðèêå
è òåîðèè
ãðàôîâ.
Ïðè÷èíû
ýòîãî íåòðóäíî
ïîíÿòü,
ïðîñòî
îáîçíà÷èâ
êðóã çàäà÷, ðåøàåìûõ
íà áàçå
ýòîãî
ìàòåìàòè÷åñêîãî
àïïàðàòà (ñì.
ï.1.3 äàííîãî
ðàçäåëà).
1.1 Îñíîâíûå
ïîíÿòèÿ
òåîðèè
ãðàôîâ.
Äåòàëüíûå
îïðåäåëåíèÿ
òåîðèè
ãðàôîâ ìîæíî
íàéòè â
ðàáîòàõ [2, 3, 4, 5, 6].
Çäåñü ìû
ëèøü îãðàíè÷èìñÿ
ïåðå÷èñëåíèåì
íåêîòîðûõ
òåðìèíîâ,
êîòîðûå
áóäóò
âñòðå÷àòüñÿ
â äàëüíåéøåì,
è èõ êðàòêèì
îïèñàíèåì.
Ãðàô-
íåïóñòîå
ìíîæåñòâî V è
X- íåêîòîðûé
íàáîð ïàð
ýëåìåíòîâ
èç V. Ýëåìåíòû
ìíîæåñòâà V
íàçûâàþòñÿ
âåðøèíàìè, à
ýëåìåíòû
íàáîðà X- ðåáðàìè.
Ïîäãðàô-
ïîäãðàôîì
ãðàôà G
íàçûâàåòñÿ
ãðàô, âñå âåðøèíû
è ðåáðà
êîòîðîãî
ñîäåðæàòñÿ
ñðåäè âåðøèí
è ðåáåð ãðàôà
G. Îñòîâíûé
ïîäãðàô
ñîäåðæèò âñå
âåðøèíû
ãðàôà G.
Ñâÿçíûé
ãðàô- ãðàô, ó
êîòîðîãî äëÿ
ëþáûõ äâóõ
ðàçëè÷íûõ âåðøèí
ñóùåñòâóåò
öåïü
(ïîñëåäîâàòåëüíîñòü
ñìåæíûõ
âåðøèí),
ñîåäèíÿþùàÿ
èõ.
Âçâåøåííûé
ñâÿçíûé
ãðàô-
ñâÿçíûé
ãðàô, ñ
çàäàííîé
âåñîâîé
ôóíêöèåé
(êàæäîìó
ýëåìåíòó
íàáîðà X
ñòàâèòñÿ â ñîîòâåòñòâèå
íåêîòîðîå
÷èñëî - âåñ
ðåáðà).
Äåðåâî-
ñâÿçíûé
ãðàô, íå
ñîäåðæàùèé
öèêëîâ.
Îñòîâ-
îñòîâíûé
ïîäãðàô,
ÿâëÿþùèéñÿ
äåðåâîì.
1.2
Ñïîñîáû
çàäàíèÿ
ãðàôîâ.
Ñóùåñòâóåò
ðÿä ñïîñîáîâ
çàäàíèÿ
ãðàôîâ. Äëÿ
ðåøåíèÿ
êîíêðåòíîé
çàäà÷è
ìîæíî
âûáðàòü òîò
èëè èíîé ñïîñîá,
â
çàâèñèìîñòè
îò óäîáñòâà
åãî ïðèìåíåíèÿ.
Çäåñü ìû
ïåðå÷èñëèì
íåêîòîðûå,
íàèáîëåå
èçâåñòíûå
ñïîñîáû,
äàäèì èõ
êðàòêóþ
õàðàêòåðèñòèêó
ñ òî÷êè
çðåíèÿ óäîáñòâà
ââîäà è
îáðàáîòêè
íà ÝÂÌ.
Ìàòðèöà
èíöèäåíòíîñòè-
ìàòðèöà
ðàçìåðîì (n-
÷èñëî
âåðøèí, m-
÷èñëî ðåáåð),
ýëåìåíòû
êîòîðîé
ðàâíû 1, åñëè i-ÿ
âåðøèíà
èíöèäåíòíà
j-ìó ðåáðó, è 0 â
ïðîòèâíîì
ñëó÷àå.
Ìàòðèöà
èíöèäåíòíîñòè
íåóäîáíà äëÿ
ââîäà è
îáðàáîòêè
íà ÝÂÌ, êðîìå
òîãî îíà íå
íåñåò ïðÿìîé
èíôîðìàöèè
î ðåáðàõ.
Ìàòðèöà
ñìåæíîñòè-
ìàòðèöà
ðàçìåðîì ,
ýëåìåíòû
êîòîðîé
ðàâíû 1, åñëè i-ÿ
âåðøèíà ñìåæíà
ñ j-îé, è 0 â
ïðîòèâíîì
ñëó÷àå.
Ìàòðèöà
ñìåæíîñòè
ÿâëÿåòñÿ
ñèììåòðè÷íîé
è
äîñòàòî÷íî
ïðîñòî ìîæåò
èñïîëüçîâàòüñÿ
äëÿ ââîäà è
îáðàáîòêè
íà ÝÂÌ. Äëÿ
ñëó÷àÿ
âçâåøåííîãî
ãðàôà
âìåñòî 1
èñïîëüçóåòñÿ
çíà÷åíèå
âåñîâîé
ôóíêöèè è
òàêàÿ ìàòðèöà
íàçûâàåòñÿ ìàòðèöåé
âåñîâ.
Ñïèñêè
ñìåæíîñòè-
êàæäûé i-é
ñïèñîê
ñîäåðæèò
íîìåðà
âåðøèí, ñìåæíûõ
i-îé âåðøèíå.
Ñïèñêè
ñìåæíîñòè
óäîáíû äëÿ
ââîäà â ÝÂÌ,
ýêîíîìÿò
ïàìÿòü, íî íå
ìîãóò èñïîëüçîâàòüñÿ
â ñëó÷àå
âçâåøåííîãî
ãðàôà.
1.3
Îáçîð çàäà÷
òåîðèè
ãðàôîâ.
Ðàçâèòèå
òåîðèè
ãðàôîâ â
îñíîâíîì
îáÿçàíî
áîëüøîìó
÷èñëó
âñåâîçìîæíûõ
ïðèëîæåíèé.
Ïî-âèäèìîìó,
èç âñåõ
ìàòåìàòè÷åñêèõ
îáúåêòîâ
ãðàôû
çàíèìàþò
îäíî èç ïåðâûõ
ìåñò â
êà÷åñòâå
ôîðìàëüíûõ
ìîäåëåé ðåàëüíûõ
ñèñòåì.
Ãðàôû
íàøëè
ïðèìåíåíèå
ïðàêòè÷åñêè
âî âñåõ
îòðàñëÿõ
íàó÷íûõ
çíàíèé:
ôèçèêå, áèîëîãèè,
õèìèè,
ìàòåìàòèêå,
èñòîðèè,
ëèíãâèñòèêå,
ñîöèàëüíûõ
íàóêàõ,
òåõíèêå è ò.ï.
Íàèáîëüøåé
ïîïóëÿðíîñòüþ
òåîðåòèêî-ãðàôîâûå
ìîäåëè èñïîëüçóþòñÿ
ïðè
èññëåäîâàíèè
êîììóíèêàöèîííûõ
ñåòåé,
ñèñòåì
èíôîðìàòèêè,
õèìè÷åñêèõ
è
ãåíåòè÷åñêèõ
ñòðóêòóð,
ýëåêòðè÷åñêèõ
öåïåé è
äðóãèõ
ñèñòåì
ñåòåâîé ñòðóêòóðû.
Äàëåå
ïåðå÷èñëèì
íåêîòîðûå
òèïîâûå
çàäà÷è
òåîðèè
ãðàôîâ è èõ
ïðèëîæåíèÿ:
- Çàäà÷à
î
êðàò÷àéøåé
öåïè
çàìåíà
îáîðóäîâàíèÿ
ñîñòàâëåíèå
ðàñïèñàíèÿ
äâèæåíèÿ
òðàíñïîðòíûõ
ñðåäñòâ
ðàçìåùåíèå
ïóíêòîâ ñêîðîé
ïîìîùè
ðàçìåùåíèå
òåëåôîííûõ
ñòàíöèé
- Çàäà÷à
î
ìàêñèìàëüíîì
ïîòîêå
àíàëèç
ïðîïóñêíîé
ñïîñîáíîñòè
êîììóíèêàöèîííîé
ñåòè
îðãàíèçàöèÿ
äâèæåíèÿ â
äèíàìè÷åñêîé
ñåòè
îïòèìàëüíûé
ïîäáîð
èíòåíñèâíîñòåé
âûïîëíåíèÿ
ðàáîò
ñèíòåç
äâóõïîëþñíîé
ñåòè ñ
çàäàííîé ñòðóêòóðíîé
íàäåæíîñòüþ
çàäà÷à î
ðàñïðåäåëåíèè
ðàáîò
- Çàäà÷à
îá
óïàêîâêàõ è
ïîêðûòèÿõ
îïòèìèçàöèÿ
ñòðóêòóðû
ÏÇÓ
ðàçìåùåíèå
äèñïåò÷åðñêèõ
ïóíêòîâ ãîðîäñêîé
òðàíñïîðòíîé
ñåòè
-
Ðàñêðàñêà â
ãðàôàõ
ðàñïðåäåëåíèå
ïàìÿòè â ÝÂÌ
ïðîåêòèðîâàíèå
ñåòåé
òåëåâèçèîííîãî
âåùàíèÿ
-
Ñâÿçíîñòü
ãðàôîâ è
ñåòåé
ïðîåêòèðîâàíèå
êðàò÷àéøåé
êîììóíèêàöèîííîé
ñåòè
ñèíòåç
ñòðóêòóðíî-íàäåæíîé
ñåòè öèðêóëÿöèîííîé
ñâÿçè
àíàëèç
íàäåæíîñòè
ñòîõàñòè÷åñêèõ
ñåòåé ñâÿçè
-
Èçîìîðôèçì
ãðàôîâ è
ñåòåé
ñòðóêòóðíûé
ñèíòåç
ëèíåéíûõ
èçáèðàòåëüíûõ
öåïåé
àâòîìàòèçàöèÿ
êîíòðîëÿ ïðè
ïðîåêòèðîâàíèè
ÁÈÑ
-
Èçîìîðôíîå
âõîæäåíèå è
ïåðåñå÷åíèå
ãðàôîâ
ëîêàëèçàöèÿ
íåèñïðàâíîñòè
ñ ïîìîùüþ àëãîðèòìîâ
ïîèñêà ÌÈÏÃ
ïîêðûòèå
ñõåìû
çàäàííûì
íàáîðîì
òèïîâûõ
ïîäñõåì
-
Àâòîìîðôèçì
ãðàôîâ
êîíñòðóêòèâíîå
ïåðå÷èñëåíèå
ñòðóêòóðíûõ
èçîìåðîâ äëÿ
ïðîèçâîäíûõ
îðãàíè÷åñêèõ
ñîåäèíåíèé
ñèíòåç
òåñòîâ
öèôðîâûõ
óñòðîéñòâ
2.
Ïîñòàíîâêà
çàäà÷è
2.1
Àëãîðèòì
ïîèñêà
îñòîâà
ìèíèìàëüíîãî
âåñà.
Âî
âçâåøåííîì
ñâÿçíîì
ãðàôå (G,f)
íàéòè îñòîâ
ìèíèìàëüíîãî
âåñà. Òàêàÿ
çàäà÷à ìîæåò
èìåòü,
íàïðèìåð,
ñëåäóþùóþ
èíòåðïðåòàöèþ.
Èñõîäíûé
ãðàô G åñòü
ïðîåêòèðóåìàÿ
ñèñòåìà
äîðîã (ðåáðà
ãðàôà),
ñâÿçûâàþùèõ
ãîðîäà íåêîòîðîé
îáëàñòè
(âåðøèíû
ãðàôà). Ïóñòü
âåñ ðåáðà f(x)-
ñòîèìîñòü
ñòðîèòåëüñòâà
äîðîãè,
ñîåäèíÿþùåé
äâà ãîðîäà.
Òðåáóåòñÿ
ïîñòðîèòü
ñèñòåìó
äîðîã
ìèíèìàëüíîé
ñòîèìîñòè,
÷òîáû èç
ëþáîãî
ãîðîäà ìîæíî
áûëî ïðîåõàòü
â ëþáîé ãîðîä
(èñêîìûé
îñòîâíûé ïîäãðàô
- ñâÿçíûé).
Î÷åâèäíî,
ðåøåíèå
çàäà÷è ñóùåñòâóåò,
è èñêîìûé
îñòîâíûé
ïîäãðàô ÿâëÿåòñÿ
äåðåâîì.
Îïèøåì îäèí
èç âîçìîæíûõ
àëãîðèòìîâ
ðåøåíèÿ (Ð.
Ïðèì 1957 ã.).
Äàí
ñâÿçíûé ãðàô
è
âåñîâàÿ
ôóíêöèÿ .
Àëãîðèòì
ñîñòîèò èç n-1
øàãà. íà
êàæäîì øàãå
ñòðîèòñÿ
äåðåâî . Äåðåâî ÿâëÿåòñÿ
îñòîâîì
ìèíèìàëüíîãî
âåñà.
1.
Âûáèðàåì
ðåáðî ìèíèìàëüíîãî
âåñà èç
ìíîæåñòâà
âñåõ ðåáåð X è
ñòðîèì
äåðåâî ,
ïîëàãàÿ åãî
ñîñòîÿùèì
èç ðåáðà è
äâóõ
èíöèäåíòíûõ
ðåáðó âåðøèí.
2.
Åñëè äåðåâî ïîðÿäêà
óæå
ïîñòðîåíî, òî
ñðåäè ðåáåð,
ñîåäèíÿþùèõ
âåðøèíû
ýòîãî äåðåâà
ñ âåðøèíàìè
ãðàôà G, íå
âõîäÿùèìè â ,
âûáåðåì
ðåáðî ìèíèìàëüíîãî
âåñà. Ñòðîèì
äåðåâî ïðèñîåäèíÿÿ
ê ðåáðî
âìåñòå
ñ åãî íå
âõîäÿùèì â êîíöîì.
3.
Åñëè i=n-1 , òî
îñòîâ
ìèíèìàëüíîãî
âåñà ïîñòðîåí,
êîíåö. Èíà÷å
ïåðåéòè ê ï.2.
2.2
Àëãîðèòì
ïîèñêà
äåðåâà
êðàò÷àéøèõ
ïóòåé.
Ðàññìîòðèì
çàäà÷ó î
êðàò÷àéøåì
ïóòè. Ïóñòü (G,f) -
âçâåøåííûé
ñâÿçíûé
ãðàô. Âåñ f(x)
ðåáðà x èíòåðïðåòèðóåì
êàê
ðàññòîÿíèå
ìåæäó
âåðøèíàìè,
ñìåæíûìè
äàííîìó
ðåáðó. Äëÿ
çàäàííîé
íà÷àëüíîé
âåðøèíû s è
êîíå÷íîé
âåðøèíû t èùåòñÿ
ïðîñòàÿ öåïü,
ñîåäèíÿþùàÿ
s è t ìèíèìàëüíîãî
âåñà. (s,t) - öåïü
ìèíèìàëüíîãî
âåñà íàçûâàþò
êðàò÷àéøèì
(s,t) - ïóòåì.
Î÷åâèäíî, ðåøåíèå
çàäà÷è
ñóùåñòâóåò.
Îïèøåì îäèí èç
âîçìîæíûõ
àëãîðèòìîâ
ðåøåíèÿ (Å.
Äåéêñòðà, 1959 ã.).
Äàí
ñâÿçíûé
ãðàô è
âåñîâàÿ
ôóíêöèÿ f(x).
Íà
êàæäîé
èòåðàöèè
àëãîðèòìà
ëþáàÿ âåðøèíà
v ãðàôà G èìååò
íåîòðèöàòåëüíóþ
ìåòêó l(v),
êîòîðàÿ ìîæåò
áûòü
âðåìåííîé
èëè
ïîñòîÿííîé
(ïîñòîÿííóþ
ìåòêó
ïîìå÷àåì l(v)+).
Ïåðåä
íà÷àëîì ïåðâîé
èòåðàöèè
âåðøèíà s
èìååò
ïîñòîÿííóþ ìåòêó
l(s)+=0, à ìåòêè
âñåõ
îñòàëüíûõ
âåðøèí ðàâíû
è ýòè ìåòêè
âðåìåííûå.
Ïîñòîÿííàÿ
ìåòêà l(v)+ -
íàéäåííûé
âåñ
êðàò÷àéøåãî
(s,v) - ïóòè. Âðåìåííàÿ
ìåòêà l(v) - âåñ
êðàò÷àéøåãî
(s,v) - ïóòè, ïðîõîäÿùåãî
÷åðåç
âåðøèíû ñ
ïîñòîÿííûìè
ìåòêàìè.
Íà
êàæäîé
èòåðàöèè
àëãîðèòìà
âðåìåííàÿ ìåòêà
îäíîé èç
âåðøèí
ïåðåõîäèò â
ïîñòîÿííóþ;
òàêèì
îáðàçîì, äëÿ
íàõîæäåíèÿ
êðàò÷àéøèõ
(s,v) - ïóòåé äëÿ
âñåõ âåðøèí v
ãðàôà G
òðåáóåòñÿ n-1
èòåðàöèÿ
àëãîðèòìà.
Òàêæå
ñ êàæäîé
âåðøèíîé v
ãðàôà G (êðîìå s)
ñâÿçûâàåòñÿ
âðåìåííàÿ
èëè
ïîñòîÿííàÿ
ìåòêà (u)
(ïîñòîÿííóþ
ìåòêó
ïîìå÷àåì (u)+). (u) ÿâëÿåòñÿ
íîìåðîì
âåðøèíû,
ïðåäøåñòâóþùåé
v â (s,v) - ïóòè,
èìåþùèì
ìèíèìàëüíûé
âåñ ñðåäè
âñåõ (s,v) - ïóòåé,
ïðîõîäÿùèõ
÷åðåç
âåðøèíû, ïîëó÷èâøèõ
ê äàííîìó
ìîìåíòó
ïîñòîÿííûå
ìåòêè. Ïîñëå
ïîëó÷åíèÿ
âåðøèíîé
ïîñòîÿííîé
ìåòêè (u)+, ñ
ïîìîùüþ
ïîñòîÿííûõ -ìåòîê
óêàçûâàåòñÿ
ïîñëåäîâàòåëüíîñòü
âåðøèí,
ñîñòàâëÿþùàÿ
êðàò÷àéøèé
(s,v) - ïóòü.
1.
Ïîëîæèòü l(s)+=0,
ò.å. ñ÷èòàòü
ýòó ìåòêó
ïîñòîÿíîé, è
l(v)= äëÿ âñåõ ,
ñ÷èòàÿ ýòè
ìåòêè
âðåìåííûìè.
Ïðèíÿòü u=s.
3.
Ïóñü V' -
ìíîæåñòâî
âåðøèí ñ
âðåìåííûìè
ìåòêàìè l.
Íàéòè
âåðøèíó v*,
òàêóþ, ÷òî
Ñ÷èòàòü
ìåòêó l(v*)+
ïîñòîÿííîé
ìåòêîé âåðøèíû
v*; (v*)+.
4. u=v*.
Åñëè u=t, òî
ïåðåéòè ê ï.5 (l(t)+ -
âåñ
êðàò÷àéøåãî
(s,t) - ïóòè).
针֌
ïåðåéòè ê ï.2.
5. Ïî
ïîñòîÿííûì - ìåòêàì
óêàçûâàåòñÿ
êðàò÷àéøèé
(s,t) - ïóòü. Êîíåö.
Ïóíêò
4 ìîæíî
ìîäèôèöèðîâàòü
òàê, ÷òîáû àëãîðèòì
çàêàí÷èâàë
ðàáîòó ïîñëå
ïîëó÷åíèÿ
âñåìè
âåðøèíàìè
ãðàôà G ïîñòîÿííûõ
ìåòîê, ò.å.
íàõîäÿòñÿ
êðàò÷àéøèå
ïóòè èç s âî
âñå âåðøèíû
ãðàôà.
Àëãîðèòì îïðåäåëèò
îñòîâíîå
äåðåâî D
êðàò÷àéøèõ
ïóòåé èç
âåðøèíû s. Äëÿ
ëþáîé
âåðøèíû v
åäèíñòâåííûé
(s,v) - ïóòü â
äåðåâå D áóäåò
êðàò÷àéøèì
(s,v) - ïóòåì â
ãðàôå G.
4.
Ñïèñîê
ëèòåpàòópû
1
Èñìàãèëîâ
Ð.Ñ., Êàëèíêèí
À.Â. Ìàòåpèàëû
ê ïpàêòè÷åñêèì
çàíÿòèÿì ïî
êópñó:
Äèñêpåòíàÿ ìàòåìàòèêà
ïî òåìå:
Àëãîpèòìû íà
ãpàôàõ. - Ì.:
ÌÃÒÓ, 1995, 24 ñ.
2
Ãàâpèëîâ Ã.Ï.,
Ñàïîæåíêî
À.À. Çàäà÷è è
óïpàæíåíèÿ
ïî êópñó
äèñêpåòíîé
ìàòåìàòèêè.
- Ì.: Hàóêà, 1992, 408 ñ.
3
Ñìîëüÿêîâ Ý.Ð.
Ââåäåíèå â
òåîpèþ ãpàôîâ.
Ì.: ÌÃÒÓ, 1992, 32 ñ.
4
Hå÷åïópåíêî
Ì.È.
Àëãîpèòìû è
ïpîãpàììû
påøåíèÿ
çàäà÷ íà
ãpàôàõ è
ñåòÿõ. -
Hîâîñèáèpñê:
Hàóêà, 1990, 515 ñ.
5
Ðîìàíîâñêèé
È.Â. Àëãîpèòìû
påøåíèÿ
ýêñòpåìàëüíûõ
çàäà÷. - Ì.:
Hàóêà, 1977, 352 ñ.
6
Håôåäîâ Â.H.,
Îñèïîâà Â.À.
Êópñ
äèñêpåòíîé
ìàòåìàòèêè.
- Ì.: ÌÀÈ, 1992, 264 ñ.
7 Ïèññàíåöêè
Ñ.
Òåõíîëîãèÿ
ðàçðåæåííûõ
ìàòðèö. - Ì.:
Ìèð, 1988, 412 ñ.
8 Ãíåäåíêî
Á.Â. Êóðñ
òåîðèè
âåðîÿòíîñòåé.
- Ì.: Íàóêà, 1988, 448 ñ.
9
Âåíòöåëü Å.Ñ.,
Îâ÷àðîâ Ë.À.
Òåîðèÿ
âåðîÿòíîñòåé.
- Ì.: Íàóêà, 1969, 367 ñ.
10
Çóáêîâ À.Ì.,
Ñåâàñòüÿíîâ
Á.À., ×èñòÿêîâ
Â.Ï. - Ñáîðíèê
çàäà÷ ïî
òåîðèè
âåðîÿòíîñòåé.
- Ì.: Íàóêà, 1989, 320 ñ.
11 Ñåâàñòüÿíîâ
Á.À.
Âåðîÿòíîñòíûå
ìîäåëè. - Ì.:
Íàóêà, 1992, 176 ñ.
12 Áî÷àðîâ
Ï.Ï., Ïå÷èíêèí
À.Â. Òåîðèÿ
âåðîÿòíîñòåé.
- Ì.: Èçä-âî ÐÓÄÍ,
1994, 172 ñ.
13 Áî÷àðîâ
Ï.Ï., Ïå÷èíêèí
À.Â.
Ìàòåìàòè÷åñêàÿ
ñòàòèñòèêà.
- Ì.: Èçä-âî ÐÓÄÍ,
1994, 164 ñ.
14
Êîëìîãîðîâ
À.Í., Ôîìèí Ñ.Â.
Ýëåìåíòû
òåîðèè
ôóíêöèé è
ôóíêöèîíàëüíîãî
àíàëèçà. - Ì.: Íàóêà,
1989, 624 ñ.
5.
Ïpèëîæåíèå:
Òåêñòû
ïpîãpàìì íà
ÿçûêå Ñ
/* File prim.c Òåîpèÿ
ãpàôîâ ÐÊ6
Ðåäíèêèí À.H.
1996ã. */
/* Àëãîpèòì
ïîèñêà
îñòîâà
ìèíèìàëüíîãî
âåñà âî
âçâåøåííîì
ãpàôå */
/*
Ð.Ïpèì, 1957 ã. */
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n,
double* weigh); /* Ââîä
ìàòpèöû
âåñîâ */
int prim(int n, double*
weigh); /*
Àëãîpèòì
ïîèñêà */
void print(int n, double*
weigh); /* Âûâîä
påçóëüòàòà */
void main(void){
int n=0,ret=0;
double *weigh;
printf("\nÀëãîpèòì
ïîèñêà
îñòîâà
ìèíèìàëüíîãî
âåñà âî
âçâåøåííîì
ãpàôå.\n");
printf("Ð.Ïpèì,
1957 ã.\n");
printf("\nÂâåäèòå
êîëè÷åñòâî
âåpøèí..");
scanf("%d",&n);
if (n <= 1){
printf("\nÊîëè÷åñòâî
âåpøèí
äîëæíî áûòü
áîëüøå åäèíèöû!\n");
exit(1);
}
weigh=malloc(sizeof(double)*n*n);
if (weigh == NULL){
printf("\nHåäîñòàòî÷íî
ïàìÿòè äëÿ
çàãpóçêè
ìàññèâà!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nÎøèáêà
ââîäà
äàííûõ!\n");
exit(5);
}
ret=prim(n,weigh);
if (ret != 0){
switch (ret){
case 1 :
printf("\nÃpàô
íå ÿâëÿåòñÿ
ñâÿçàííûì!\n");
exit(3);
case 2 :
printf("\nHåäîñòàòî÷íî
ïàìÿòè äëÿ
pàáîòû!\n");
exit(4);
}
}
print(n,weigh);
free(weigh);
}
int load_matrix(int n,
double* weigh){
int i,j,k;
double tmp;
for (i=0; i < n;
i++){
weigh[n*i+j]=(-1);
}
}
printf("\nÂâåäèòå
ïîñëåäîâàòåëüíî
âåñà påáåp äëÿ
óêàçàííûõ
âåpøèí èëè -1
äëÿ
íåñìåæíûõ.");
for (i=0; i < n;
i++){
for (j=i+1; j
< n; j++){
printf("\nÂåpøèíû
%d è %d ",i+1,j+1);
k=scanf("%lf",&tmp);
if (k !=
1){return(1);}
weigh[i*n+j]=tmp;
}
}
return(0);
}
int prim(int n, double*
weigh){
int i,j,k,l,m,flag;
int* index;
double tmp;
index=calloc(sizeof(int),n);
if (index ==
NULL){return(2);}
index[0]=1;
for (k=0; k < (n-1);
k++){
for
(i=0,flag=0,tmp=DBL_MAX; i < n; i++){
for
(j=i+1; j < n; j++){
if ((weigh[i*n+j]
< tmp)&&
(weigh[i*n+j]
>= 0)&&
(weigh[j*n+i]
== (-1))&&
(index[i]*index[j]
== 0)&&
(index[i]+index[j]
== 1)){
flag=1;
tmp=weigh[i*n+j];
l=i;
m=j;
}
}
}
if (flag == 1){
weigh[m*n+l]=tmp;
index[m]=1;
index[l]=1;
}
}
for (i=0; i < n;
i++){
if (index[i] ==
0)
return(1);
}
free(index);
return(0);
}
void print(int n, double*
weigh){
int i,j;
double tmp=0.0;
printf("\nÎñòîâ
ìèíèìàëüíîãî
âåñà:");
for (i=0; i < n;
i++){
printf("\n");
for (j=(i+1); j
< n; j++){
if
(weigh[j*n+i] != (-1)){
printf("
weigh[%d,%d]=%6.2f",i+1,j+1,weigh[j*n+i]);
tmp+=weigh[j*n+i];
}
}
}
printf("\nÂåñ
íàéäåííîãî
äåpåâà: %6.2f\n",tmp);
}
Òåñòîâûé
ïðèìåð èç
ðàáîòû [1] (ðèñ.6
íà ñòð. 9).
Àëãîpèòì
ïîèñêà
îñòîâà
ìèíèìàëüíîãî
âåñà âî
âçâåøåííîì
ãpàôå.
Ð.Ïpèì, 1957 ã.
Ââåäèòå
êîëè÷åñòâî
âåpøèí.. 6
Ââåäèòå
ïîñëåäîâàòåëüíî
âåñà påáåp äëÿ
óêàçàííûõ
âåpøèí èëè -1
äëÿ
íåñìåæíûõ.
Âåpøèíû 1 è
2 3
Âåpøèíû 1 è 4
-1
Âåpøèíû 1 è 5
-1
Âåpøèíû 1 è
6 1
Âåpøèíû 2 è
3 1
Âåpøèíû 2 è 4
-1
Âåpøèíû 2 è
5 1
Âåpøèíû 2 è 6
2
Âåpøèíû 3 è
4 4
Âåpøèíû 3 è 5
-1
Âåpøèíû 3 è 6
-1
Âåpøèíû 4 è
5 6
Âåpøèíû 4 è 6
-1
Âåpøèíû 5 è
6 2
Îñòîâ
ìèíèìàëüíîãî
âåñà:
weigh[1,6]= 1.00
weigh[2,3]= 1.00 weigh[2,5]= 1.00 weigh[2,6]= 2.00
weigh[3,4]= 4.00
Âåñ
íàéäåííîãî
äåpåâà: 9.00
/* File deik.c
Òåîpèÿ
ãpàôîâ ÐÊ6
Ðåäíèêèí À.H.
1996ã. */
/*
Àëãîpèòì
ïîèñêà
äåpåâà
êpàò÷àéøèõ
ïóòåé âî
âçâåøåííîì
ãpàôå */
/*
Å.Äåéêñòpà 1959
ã. */
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
int load_matrix(int n,
double* weigh); /*
Ââîä ìàòpèöû
âåñîâ */
int deik(int n, int s,
double* weigh, int* Q, double* L); /*
Àëãîpèòì
ïîèñêà */
void print(int n, int* Q,
double* L); /*
Âûâîä
påçóëüòàòà */
void main(void){
int n=0,s=0,ret=0;
double *weigh;
int* Q; /*
Ìàññèâ
ìåòîê
óêàçàòåëåé
íà
ïpåäûäóùóþ âåpøèíó */
double* L; /*
Ìàññèâ
íàéäåíûõ
âåñîâ ïóòè
äî âåpøèíû */
printf("\nÀëãîpèòì
ïîèñêà
äåpåâà
êpàò÷àéøèõ
ïóòåé âî
âçâåøåííîì
ãpàôå.\n");
printf("Å.Äåéêñòpà,
1959 ã.\n");
printf("\nÂâåäèòå
êîëè÷åñòâî
âåpøèí..");
scanf("%d",&n);
if (n <= 1){
printf("\nÊîëè÷åñòâî
âåpøèí
äîëæíî áûòü
áîëüøå åäèíèöû!\n");
exit(1);
}
printf("\nÂâåäèòå
íà÷àëüíóþ
âåpøèíó..");
scanf("%d",&s);
s--;
if ((s < 0)||(s >
(n-1))){
printf("\nHà÷àëüíàÿ
âåpøèíà
óêàçàíà
íåïpàâèëüíî!\n");
exit(1);
}
Q=malloc(n*sizeof(int));
L=malloc(n*sizeof(double));
weigh=malloc(sizeof(double)*n*n);
if ((weigh == NULL)||(Q
== NULL)||(L == NULL)){
printf("\nHåäîñòàòî÷íî
ïàìÿòè äëÿ
çàãpóçêè
ìàññèâà!\n");
exit(2);
}
ret=load_matrix(n,weigh);
if (ret != 0){
printf("\nÎøèáêà
ââîäà
äàííûõ!\n");
exit(5);
}
ret=deik(n,s,weigh,Q,L);
if (ret != 0){
switch (ret){
case 1 :
printf("\nÃpàô
íå ÿâëÿåòñÿ
ñâÿçàííûì!\n");
exit(3);
case 2 :
printf("\nHåäîñòàòî÷íî
ïàìÿòè äëÿ
pàáîòû!\n");
exit(4);
}
}
free(weigh);
free(Q);
free(L);
}
int load_matrix(int n,
double* weigh){
int i,j,k;
double tmp;
for (i=0; i < n;
i++){
for (j=0; j <
n; j++){
weigh[n*i+j]=(-1);
}
}
printf("\nÂâåäèòå
ïîñëåäîâàòåëüíî
âåñà påáåp äëÿ
óêàçàííûõ
âåpøèí èëè -1
äëÿ
íåñìåæíûõ.");
for (i=0; i < n;
i++){
for (j=i+1; j
< n; j++){
printf("\nÂåpøèíû
%d è %d ",i+1,j+1);
k=scanf("%lf",&tmp);
if (k !=
1){return(1);}
weigh[i*n+j]=tmp;
}
}
return(0);
}
int deik(int n,int s, double*
weigh, int* Q, double* L){
int i,j,k;
int* QI; /*
Ìàññèâ
èíäèêàòîpîâ
ïîñòîÿíñòâà
ìåòîê
óêàçàòåëåé */
double tmp;
QI=calloc(n,sizeof(int));
if (QI ==
NULL){return(2);}
QI[s]=1;
for (i=0; i < n;
i++){
Q[i]=(-1);
L[i]=DBL_MAX;
}
Q[s]=s;
L[s]=0;
weigh[n*(n-1)+s]=0;
for (k=0; k < n;
k++){ /*
Îñíîâíîé
öèêë ïî
âåpøèíàì */
for (i=0; i <
n; i++){ /* Öèêë ïî
ñòpîêàì
ìàòpèöû
âåñîâ */
for
(j=i+1; j < n; j++){ /* Öèêë ïî
ñòîëáöàì
ìàòpèöû
âåñîâ */
if ((QI[i]+QI[j]
== 1)&&
(QI[i]*QI[j]
== 0)&&
(weigh[i*n+j]
!= (-1.0))&&
(((QI[i]
== 1)&&((L[i]+weigh[i*n+j]) < L[j]))||
((QI[j] ==
1)&&((L[j]+weigh[i*n+j]) < L[i])))){
if
(QI[i] == 1){
L[j]=L[i]+weigh[i*n+j];
Q[j]=i;
}
else{
L[i]=L[j]+weigh[i*n+j];
Q[i]=j;
}
}
}
}
for (tmp=DBL_MAX,i=0; i
< n; i++){
if ((tmp >
L[i])&&(QI[i] == 0)){
tmp=L[i];
j=i;
}
}
QI[j]=1;
}
free(QI);
return(0);
}
void print(int n, int* Q,
double* L){
int i;
printf("\n\nÄåpåâî
êpàò÷àéøèõ
ïóòåé:");
printf("\nÂåpøèíà:
%d Ïpåäîê: %d Âåñ:
%5.2lf",i+1,Q[i]+1,L[i]);
}
}
Òåñòîâûé
ïðèìåð èç
ðàáîòû [1] (ðèñ.8
íà ñòð. 12).
Àëãîpèòì
ïîèñêà
äåpåâà
êpàò÷àéøèõ
ïóòåé âî
âçâåøåííîì
ãpàôå.
Å.Äåéêñòpà,
1959 ã.
Ââåäèòå
êîëè÷åñòâî
âåpøèí.. 6
Ââåäèòå
íà÷àëüíóþ
âåpøèíó.. 6
Ââåäèòå
ïîñëåäîâàòåëüíî
âåñà påáåp äëÿ
óêàçàííûõ
âåpøèí èëè -1
äëÿ
íåñìåæíûõ.
Âåpøèíû 1 è
2 2
Âåpøèíû 1 è 3
-1
Âåpøèíû 1 è
4 2
Âåpøèíû 1 è 5
-1
Âåpøèíû 1 è
6 5
Âåpøèíû 2 è
3 2
Âåpøèíû 2 è 4
-1
Âåpøèíû 2 è
5 2
Âåpøèíû 2 è 6
-1
Âåpøèíû 3 è 4
-1
Âåpøèíû 3 è 5
-1
Âåpøèíû 3 è
6 12
Âåpøèíû 4 è
5 1
Âåpøèíû 4 è
6 2
Âåpøèíû 5 è
6 5
Äåpåâî
êpàò÷àéøèõ
ïóòåé:
Âåpøèíà: 1
Ïpåäîê: 4 Âåñ: 4.00
Âåpøèíà: 2
Ïpåäîê: 5 Âåñ: 5.00
Âåpøèíà: 3
Ïpåäîê: 2 Âåñ: 7.00
Âåpøèíà: 4
Ïpåäîê: 6 Âåñ: 2.00
Âåpøèíà: 5
Ïpåäîê: 4 Âåñ: 3.00
Âåpøèíà: 6
Ïpåäîê: 6 Âåñ: 0.00
Òåñòîâûå
ïðèìåðû: