Ãëàâíàÿ » Êàòàëîã    
ðåôåðàòû Ðàçäåëû ðåôåðàòû
ðåôåðàòû
ðåôåðàòûÃëàâíàÿ

ðåôåðàòûÁèîëîãèÿ

ðåôåðàòûÁóõãàëòåðñêèé ó÷åò è àóäèò

ðåôåðàòûÂîåííàÿ êàôåäðà

ðåôåðàòûÃåîãðàôèÿ

ðåôåðàòûÃåîëîãèÿ

ðåôåðàòûÃðàôîëîãèÿ

ðåôåðàòûÄåíüãè è êðåäèò

ðåôåðàòûÅñòåñòâîçíàíèå

ðåôåðàòûÇîîëîãèÿ

ðåôåðàòûÈíâåñòèöèè

ðåôåðàòûÈíîñòðàííûå ÿçûêè

ðåôåðàòûÈñêóññòâî

ðåôåðàòûÈñòîðèÿ

ðåôåðàòûÊàðòîãðàôèÿ

ðåôåðàòûÊîìïüþòåðíûå ñåòè

ðåôåðàòûÊîìïüþòåðû ÝÂÌ

ðåôåðàòûÊîñìåòîëîãèÿ

ðåôåðàòûÊóëüòóðîëîãèÿ

ðåôåðàòûËèòåðàòóðà

ðåôåðàòûÌàðêåòèíã

ðåôåðàòûÌàòåìàòèêà

ðåôåðàòûÌàøèíîñòðîåíèå

ðåôåðàòûÌåäèöèíà

ðåôåðàòûÌåíåäæìåíò

ðåôåðàòûÌóçûêà

ðåôåðàòûÍàóêà è òåõíèêà

ðåôåðàòûÏåäàãîãèêà

ðåôåðàòûÏðàâî

ðåôåðàòûÏðîìûøëåííîñòü ïðîèçâîäñòâî

ðåôåðàòûÐàäèîýëåêòðîíèêà

ðåôåðàòûÐåêëàìà

ðåôåðàòûÐåôåðàòû ïî ãåîëîãèè

ðåôåðàòûÌåäèöèíñêèå íàóêàì

ðåôåðàòûÓïðàâëåíèå

ðåôåðàòûÔèçèêà

ðåôåðàòûÔèëîñîôèÿ

ðåôåðàòûÔèíàíñû

ðåôåðàòûÔîòîãðàôèÿ

ðåôåðàòûÕèìèÿ

ðåôåðàòûÝêîíîìèêà

ðåôåðàòû
ðåôåðàòû Èíôîðìàöèÿ ðåôåðàòû
ðåôåðàòû
ðåôåðàòû

Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ àëãîðèòìû è ïðîãðàììû


Ïîñòàíîâêà
ëàáîðàòîðíîé
ðàáîòû ïî
òåîðèè
ãðàôîâ
(àëãîðèòìû
è ïðîãðàììû)
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);
}
ðåôåðàòû Ðåêîìåíäóåì ðåôåðàòûðåôåðàòû

     
Ðåôåðàòû @2011