Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ àëãîðèòìû è ïðîãðàììû
Ïîñòàíîâêà
ëàáîðàòîðíîé
ðàáîòû ïî
òåîðèè
ãðàôîâ
(àëãîðèòìû
è ïðîãðàììû)
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.
2. Äëÿ
âñåõ ñ
âðåìåííûìè
ìåòêàìè
âûïîëíèòü: åñëè
l(v)>l(u)+f(x) è (v)=u. Èíà÷å l(v) è (v)
íå ìåíÿòü.
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++){
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 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 è 3 -1
Âå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);
}
}
print(n,Q,L);
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àò÷àéøèõ
ïóòåé:");
for (i=0; i < n; i++){
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
Òåñòîâûå
ïðèìåðû:
Äàííàÿ ðàáîòà íàçûâàåòñÿ: Ïîñòàíîâêà
ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ (àëãîðèòìû è ïðîãðàììû).
Ðàáîòà áûëà âûïîëíåíà ïîä ðóêîâîäñòâîì äîö.
Êàëèíêèíà À.Â. è äîëîæåíà íà
åæåãîäíîé ñòóäåíò÷åñêîé êîíôåðåíöèè êàôåäðû
"Âûñøàÿ ìàòåìàòèêà" ÌÃÒÓ èì.
Í.Ý. Áàóìàíà (12 àïðåëÿ 1996
ã.). Ëàáîðàòîðíàÿ ðàáîòà ðàñ÷èòàíà íà ñòóäåíòîâ 2-4 ñåìåñòðà îáó÷åíèÿ,
ïðîõîäÿùèõ êóðñ äèñêðåòíîé ìàòåìàòèêè. Ïðèâîäèòñÿ ïîñòàíîâêà äâóõ çàäà÷ ïî
òåîðèè ãðàôîâ: ïîèñê îñòîâà ìèíèìàëüíîãî
âåñà è ïîèñê äåðåâà êðàò÷àéøèõ
ïóòåé âî âçâåøåííîì ñâÿçíîì ãðàôå.
Ïðèâîäèòñÿ è èõ ðåàëèçàöèÿ íà ÿçûêå Ñ (àëãîðèòìû Ïðèìà è Äåéêñòðà).
 ðàáîòå
ïðèâîäèòñÿ ñïèñîê òèïîâûõ çàäà÷ òåîðèè ãðàôîâ è íåêîòîðûå îïðåäåëåíèÿ
òåîðèè ãðàôîâ, íåîáõîäèìûå äëÿ ïîíèìàíèÿ ïîñòàâëåííîé çàäà÷è.
Ðàáîòà
(graf.doc) âûïîëíåíà â WinWord 2.0, èñïîëüçîâàíû øðèôòû "Áàëòèêà" è
"System".
Çàìå÷àíèÿ ê ñïèñêó ëèòåðàòóðû:
Ðàáîòû [1,3]- ðàçðàáîòêè êàôåäðû âûñøåé
ìàòåìàòèêè ÌÃÒÓ èì. Í.Ý. Áàóìàíà. Òåñòîâûå ïðèìåðû èç [1], íà êîòîðûå
åñòü ññûëêè â òåêñòå, ïðèâåäåíû íà ïîñëåäíåé ñòðàíèöå.
Íåïîñðåäñòâåííî òåîðèÿ ãðàôîâ èçëàãàåòñÿ â ðàáîòàõ [2,
4, 5,
6]. Ðàáîòà [2]- îñíîâíîå ó÷åáíîå
ïîñîáèå ïî êóðñó äèñêðåòíîé ìàòåìàòèêè â ÌÃÒÓ. Ðàáîòà [4] ñîäåðæèò ðÿä ñòàíäàðòíûõ àëãîðèòìîâ (îêîëî 140) ïî
òåîðèè ãðàôîâ íà ÿçûêàõ
ïðîãðàììèðîâàíèÿ ÏË-1 è Ôîðòðàí. Ðàáîòû
[4, 5] ñîäåðæàò áîãàòûé ñïèñîê ëèòåðàòóðû, ãäå ìîæíî íàéòè óêàçàíèÿ íà èíòåðåñóþùèå
Âàñ ïðîáëåìû.
Ïðàêòè÷åñêîå ïðèìåíåíèå òåîðèè ãðàôîâ êàê
ïðàâèëî çàòðàãèâàåò ðÿä äðóãèõ
ðàçäåëîâ ìàòåìàòèêè, òàêèå, êàê òåîðèÿ âåðîÿòíîñòåé è ìàòåìàòè÷åñêàÿ
ñòàòèñòèêà, òåîðèÿ ìíîæåñòâ è ò.ï.
Èç ýòèõ ñîîáðàæåíèé â ñïèñêå ëèòåðàòóðû
ïðèâîäÿòñÿ íåêîòîðûå ðàáîòû ïî òåîðèè âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêå [8 - 13]. Òåîðèÿ ìíîæåñòâ íàèáîëåå ïîëíî èçëîæåíà â
[14] (ýòî êóðñ ëåêöèé À.Í. Êîëìîãîðîâà
- ëó÷øåå, ÷òî ìíå êîãäà-ëèáî
ïðèõîäèëîñü äåðæàòü â ðóêàõ).
Ðàáîòà [7] ìîæåò ïðèãîäèòüñÿ â ñëó÷àå
ïðèìåíåíèÿ òåîðèè ãðàôîâ
â îáëàñòè ýëåêòðè÷åñêèõ öåïåé (ò.å.
êîãäà ãðàô ñîäåðæèò îòíîñèòåëüíî ìàëî ðåáåð è ìàòðèöà, åãî îïèñûâàþùàÿ, ïîëó÷àåòñÿ ðàçðÿæåííîé).
Æåëàþ
âñåãî õîðîøåãî, áóäó ðàä, åñëè ìîÿ ñêðîìíàÿ ðàáîòà ïîìîæåò Âàì ïîëþáèòü
ìàòåìàòèêó èëè õîòÿ áû çàèíòåðåñîâàòüñÿ åé.
Ñ óâàæåíèåì,
Ðåäíèêèí Àíäðåé.
6
6
2
-1
2
-1
5
2
-1
2
-1
-1
-1
12
1
2
5
6
3
-1
-1
-1
1
1
-1
1
2
4
-1
-1
6
-1
2
/* 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);
}
}
print(n,Q,L);
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àò÷àéøèõ
ïóòåé:");
for (i=0; i < n; i++){
printf("\nÂåpøèíà: %d Ïpåäîê: %d
Âåñ: %5.2lf",i+1,Q[i]+1,L[i]);
}
}
/* 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++){
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
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);
}
|
