Составители:
Рубрика:
3
ÂÂÅÄÅÍÈÅ
Òåîðèÿ ãðàôîâ, ÿâëÿÿñü ðàçäåëîì äèñêðåòíîé ìàòåìàòèêè, èñïîëüçó-
åòñÿ äëÿ îïèñàíèÿ è èçó÷åíèÿ îòíîøåíèé ìåæäó äèñêðåòíûìè îáúåêòà-
ìè. Ãåîìåòðè÷åñêè îáúåêòû ìîæíî ïðåäñòàâèòü â âèäå ìíîæåñòâà òî-
÷åê, íàçûâàåìûõ âåðøèíàìè ãðàôà, à îòíîøåíèÿ ìåæäó íèìè ëèíèÿ-
ìè, ñâÿçûâàþùèìè âåðøèíû. Åñëè ëèíèè íå îðèåíòèðîâàíû, òî èõ íà-
çûâàþò ðåáðàìè, à ñàì ãðàô íåîðèåíòèðîâàííûì, à åñëè ëèíèè îðèåí-
òèðîâàíû, òî èõ íàçûâàþò äóãàìè, à ñàì ãðàô îðèåíòèðîâàííûì, èëè
îðãðàôîì.
Èìåÿ â ñâîåé îñíîâå ïðîñòåéøèå èäåè è ýëåìåíòû (òî÷êè, ñîåäèíåí-
íûå ëèíèÿìè), òåîðèÿ ãðàôîâ ñòðîèò èç íèõ îãðîìíîå ìíîãîîáðàçèå ôîðì,
íàäåëÿåò ýòè ôîðìû ðàçëè÷íûìè ñâîéñòâàìè è â ðåçóëüòàòå ñòàíîâèò-
ñÿ ïîëåçíûì èíñòðóìåíòîì ïðè èññëåäîâàíèè ñàìûõ ðàçíîîáðàçíûõ ñè-
ñòåì.
 ñàìîì ïîíÿòèè ãðàôà ñî÷åòàþòñÿ òåîðåòèêî-ìíîæåñòâåííûå, êîì-
áèíàòîðíûå è òîïîëîãè÷åñêèå àñïåêòû, ÷òî äåëàåò òåîðèþ ãðàôîâ óäîá-
íûì, ïðîñòûì ÿçûêîì äëÿ ôîðìóëèðîâêè è ïîñòðîåíèÿ ìîäåëåé, à òàê-
æå ýôôåêòèâíûì è ìîùíûì èíñòðóìåíòîì ðåøåíèÿ çàäà÷, îòíîñÿùèõ-
ñÿ ê øèðîêîìó êðóãó íàó÷íûõ è èíæåíåðíûõ ïðîáëåì. Ìîæíî óïîìÿ-
íóòü â ýòîé ñâÿçè âîïðîñû êîíñòðóèðîâàíèÿ ñècòåì àâòîìàòèçèðîâàí-
íîãî ïðîåêòèðîâàíèÿ, ñèñòåì ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ è ñîçäàíèÿ
îïåðàöèîííûõ ñèñòåì, èññëåäîâàíèÿ îïåðàöèé è óïðàâëåíèÿ, ìàòåìàòè-
÷åñêîé ëèíãâèñòèêè è ðàçðàáîòêè òðàíñëÿòîðîâ, êàëåíäàðíîå ïëàíèðî-
âàíèå ïðîìûøëåííîãî ïðîèçâîäñòâà, çàäà÷è ñåòåâîãî ïëàíèðîâàíèÿ è
óïðàâëåíèÿ (ÑÏÓ), òàêòè÷åñêèå è ëîãè÷åñêèå çàäà÷è âûáîðà ëó÷øèõ
îáúåêòîâ, áîëüøîé êðóã ýêîíîìè÷åñêèõ çàäà÷, èãðîâûå çàäà÷è.
Âìåñòî ïîíÿòèÿ ãðàôà ÷àñòî èñïîëüçóåòñÿ ïîíÿòèå ñåòü, êîãäà êðî-
ìå îñíîâíûõ, ÷èñòî ñòðóêòóðíûõ, îòíîøåíèé â ãðàôå çàäàþòñÿ íåêîòî-
ðûå êîëè÷åñòâåííûå õàðàêòåðèñòèêè òî÷åê è ëèíèé. Ïðè ýòîì ìîæíî
ðåøàòü ïðîáëåìû ïîñòðîåíèÿ ýëåêòðè÷åñêèõ ñåòåé, ñèñòåì ñâÿçè è èñ-
ñëåäîâàíèÿ ïðîöåññîâ ïåðåäà÷è èíôîðìàöèè, âûáîðà îïòèìàëüíûõ ìàð-
øðóòîâ è ïîòîêîâ â ñåòÿõ, íàïðèìåð ïîñòðîåíèÿ ñåòè âûïîëíåíèÿ ðà-
