Математические методы в экономике. Копылов Г.Н - 29 стр.

                  Óñëîâèå íàëè÷èÿ ðåøåíèÿ
     Ìîæíî ëè âûïîëíèòü êîìïëåêñ ðàáîò, çàäàííûé ïðîèçâîëü-
íîé òàáëèöåé èëè ãðàôîì? Åñëè, íàïðèìåð, ó êàæäîé ðàáîòû
åñòü õîòÿ áû îäèí ïðåäøåñòâåííèê, òî âåñü êîìïëåêñ íåâûïîë-
íèì. Ìû íå ìîæåì íà÷àòü íè îäíîé ðàáîòû. Åñëè, íàïðèìåð, ó
ðàáîòû 5 ïðåäøåñòâåííèê ðàáîòà 3, à ó ðàáîòû 3 ïðåäøåñòâåííèê
ðàáîòà 5, òî âåñü êîìïëåêñ íåâûïîëíèì. Ìû íå ìîæåì íà÷àòü
ðàáîòó 3, ïîêà íå çàêîí÷èì ðàáîòó 5, è íå ìîæåì íà÷àòü ðàáîòó
5, ïîêà íå çàêîí÷èì ðàáîòó 3. Îáû÷íî òàêèå ñèòóàöèè âîçíèêàþò
èç-çà îøèáîê â íà÷àëüíûõ äàííûõ. Ñåòåâîé ãðàôèê íå äîëæåí
ñîäåðæàòü îðèåíòèðîâàííûõ öèêëîâ, òî åñòü â íåì íå äîëæíî
áûòü òàêîãî ìíîæåñòâà âåðøèí, â êîòîðîì â êàæäóþ ïîñëåäóþ-
ùóþ âåðøèíó èäåò îðèåíòèðîâàííàÿ äóãà èç ïðåäûäóùåé.
     Òàêîãî ôðàãìåíòà íå äîëæíî áûòü â ñåòåâîì ãðàôèêå:




     Åñëè â ãðàôå èìååòñÿ òàêîé öèêë, òî íè îäíó èç ðàáîò,
ñîîòâåòñòâóþùèõ âåðøèíàì öèêëà, âûïîëíèòü íåâîçìîæíî, òàê
êàê äëÿ ýòîãî íóæíî âûïîëíèòü åå ïðåäøåñòâåííèêà.
     Êàê ïðîâåðèòü, åñòü ëè â îðèåíòèðîâàííîì ãðàôå öèêëû?
Òåîðåìà. Â ãðàôå íàâåðíÿêà íåò îðèåíòèðîâàííûõ öèêëîâ, åñëè
âåðøèíû çàíóìåðîâàíû òàê, ÷òî êàæäîå ðåáðî èäåò èç âåðøèíû ñ
ìåíüøèì íîìåðîì â âåðøèíó ñ áîëüøèì íîìåðîì.
     Äîêàçàòåëüñòâî î÷åâèäíî.
     Äëÿ ïðîâåðêè îòñóòñòâèÿ öèêëîâ è íàõîæäåíèÿ òàêîé
íóìåðàöèè âåðøèí ìîæíî âîñïîëüçîâàòüñÿ ñëåäóþùèì àëãî-
ðèòìîì:
     1) Íàéòè â ãðàôå âåðøèíó, â êîòîðóþ íå âõîäèò íè îäíà äóãà.
Ïðèñâîèòü åé íîìåð 1.
     2) Ñðåäè âåðøèí, íå èìåþùèõ íîìåðà, íàéòè òàêóþ, â êîòî-
ðóþ ëèáî íå âõîäèò íè îäíà äóãà, ëèáî âõîäÿò äóãè òîëüêî èç óæå
ïðîíóìåðîâàííûõ âåðøèí. Íàéäåííàÿ âåðøèíà ïîëó÷àåò ñëåäóþùèé
ñâîáîäíûé íîìåð.

                               29