Элементы теории графов. Домнин Л.Н. - 3 стр.

   Ïðåäèñëîâèå
   Òåîðèÿ ãðàôîâ  ðàçäåë äèñêðåòíîé ìàòåìàòèêè, ðàññìàò-
ðèâþùèé ìíîæåñòâà ñ çàäàííûìè íà íèõ îòíîøåíèÿìè ìåæäó
ýëåìåíòàìè. Îáúåêòû òàêîãî ðîäà ìîãóò áûòü íàãëÿäíî ïðåä-
ñòàâëåíû ââèäå ðèñóíêîâ, ñîñòîÿùèõ èç òî÷åê, êðóæî÷êîâ èëè
èíûõ ôèãóð, ñîåäèíåííûõ ëèíèÿìè. Ïðè ýòîì òî÷êè ñîîòâåò-
ñòâóþò ýëåìåíòàì ìíîæåñòâà, à ëèíèè îòðàæàþò ñâÿçè (îòíî-
øåíèÿ) ìåæäó íèìè. Ïîäîáíûå ðèñóíêè îáû÷íî è íàçûâàþò
ãðàôàìè, õîòÿ ñîîòâåòñòâóþùåå ïîíÿòèå øèðå, à ðèñóíîê 
ëèøü îäíà èç ôîðì ïðåäñòàâëåíèÿ ãðàôà.
   Cõåìû ðàçëè÷íûõ êîììóíèêàöèé, ýëåêòðè÷åñêèõ öåïåé, õè-
ìè÷åñêèõ ñîåäèíåíèé, áëîê-ñõåìû êîìïüþòåðíûõ ïðîãðàìì,
ñõåìû ñâÿçåé ìåæäó ëþäüìè è ãðóïïàìè ëþäåé ôàêòè÷åñêè
ÿâëÿþòñÿ ãðàôàìè. Ñ ïîìîùüþ ãðàôîâ ëåãêî è ïðîñòî ôîð-
ìóëèðóåòñÿ áîëüøèíñòâî çàäà÷, â êîòîðûõ ôèãóðèðóþò äèñ-
êðåòíûå îáúåêòû è ïðîöåññû.
   Ââåäåíèå òåðìèíà "ãðàô" ïðèïèñûâàåòñÿ èçâåñòíîìó âåí-
ãåðñêîìó ìàòåìàòèêó Ä. Êåíèãó (18841944) àâòîðó îäíîé èç
ïåðâûõ êíèã ïî òåîðèè ãðàôîâ (1936 ã.). Îäíàêî èìåþòñÿ è
áîëåå ðàííèå ðàáîòû (ñòàòüè êàê ñàìîãî Êåíèãà, òàê è äðóãèõ
àâòîðîâ), ãäå èñïîëüçóåòñÿ ýòî íàçâàíèå.
   Ïîÿâëåíèå ÝÂÌ, ðàçâèòèå ìàòåìàòè÷åñêîé ëîãèêè, ìàøèí-
íîé ìàòåìàòèêè, òåîðèè èíôîðìàöèè, èññëåäîâàíèÿ îïåðàöèé,
áèîëîãèè, ìàòåìàòè÷åñêîé ëèíãâèñòèêè è äðóãèõ äèñöèïëèí,
ïðèâåëî ê ðîñòó ÷èñëà çàäà÷, ãäå, â îòëè÷èå îò êëàññè÷åñêîãî
àíàëèçà íåïðåðûâíûõ âåëè÷èí, íà ïåðâûé ïëàí âûõîäÿò ðàñ-
ñóæäåíèÿ è ïîñòðîåíèÿ äèñêðåòíî-êîìáèíàòîðíîãî õàðàêòåðà.
Êàê ðåçóëüòàò òåîðèÿ ãðàôîâ ñòàëà îäíîé èç ñóùåñòâåííûõ
÷àñòåé ìàòåìàòè÷åñêîãî àïïàðàòà ìíîãèõ íàó÷íûõ äèñöèïëèí
è âîøëà â ó÷åáíûå ïðîãðàììû âóçîâ.
   Â íåáîëüøîé ïî îáúåìó êíèãå íåâîçìîæíî îõâàòèòü âñþ
ïðîáëåìàòèêó òåîðèè. Â ðåçóëüòàòå æåñòêîãî îòáîðà áûëè âû-
áðàíû òåìû, êàñàþùèåñÿ ñâÿçíîñòè, ïîèñêà ïóòåé è öèêëîâ â
ãðàôàõ, à òàêæå äåðåâüåâ  îäíîãî èç íàèáîëåå ÷àñòî âñòðå-
÷àþùèõñÿ â ïðèëîæåíèÿõ âèäîâ ãðàôîâ.



                            3