Единое окно доступа к образовательным ресурсам

Дискретная математика: Основы теории графов и алгоритмизация задач: Учебное пособие

Голосов: 13

Рассмотрены основные определения и понятия теории графов, необходимые для решения некоторых прикладных задач дискретной математики (определение оптимальных расстояний между множеством объектов, поиск критического пути в задаче сетевого планирования и управления, выбор предпочтительных вариантов системы по множеству критериев). Обсуждаются подходы к разработке компьютерных алгоритмов задач па основе моделей теории графов.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
        ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ
                    Ñàíêò-Ïåòåðáóðãñêèé
ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ



                      Ë. À. Ïðîêóøåâ




           ÄÈÑÊÐÅÒÍÀß ÌÀÒÅÌÀÒÈÊÀ
     Îñíîâû òåîðèè ãðàôîâ è àëãîðèòìèçàöèè çàäà÷
                      Ó÷åáíîå ïîñîáèå




                      Ñàíêò-Ïåòåðáóðã
                           2000


ÓÄÊ 519.2
ÁÁÊ 22.174
    Ï80

    Ïðîêóøåâ Ë. À
Ï80 Äèñêðåòíàÿ ìàòåìàòèêà (îñíîâû òåîðèè ãðàôîâ è àëãîðèòìèçàöèè
çàäà÷): Ó÷åá. ïîñîáèå / ÑÏáÃÓÀÏ. ÑÏá., 2000. 82 ñ.: èë.

       Ðàññìîòðåíû îñíîâíûå îïðåäåëåíèÿ è ïîíÿòèÿ òåîðèè ãðàôîâ, íåîáõî-
    äèìûå äëÿ ðåøåíèÿ íåêîòîðûõ ïðèêëàäíûõ çàäà÷ äèñêðåòíîé ìàòåìàòèêè
    (îïðåäåëåíèå îïòèìàëüíûõ ðàññòîÿíèé ìåæäó ìíîæåñòâîì îáúåêòîâ, ïî-
    èñê êðèòè÷åñêîãî ïóòè â çàäà÷å ñåòåâîãî ïëàíèðîâàíèÿ è óïðàâëåíèÿ, âû-
    áîð ïðåäïî÷òèòåëüíûõ âàðèàíòîâ ñèñòåìû ïî ìíîæåñòâó êðèòåðèåâ). Îá-
    ñóæäàþòñÿ ïîäõîäû ê ðàçðàáîòêå êîìïüþòåðíûõ àëãîðèòìîâ çàäà÷ íà îñ-
    íîâå ìîäåëåé òåîðèè ãðàôîâ.
       Ó÷åáíîå ïîñîáèå ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ ñïåöèàëüíîñòè “Ñèñòå-
    ìû àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ”, à òàêæå äëÿ ñòóäåíòîâ äðóãèõ
    ñïåöèàëüíîñòåé, èñïîëüçóþùèõ òåîðèþ ãðàôîâ äëÿ ðåøåíèÿ çàäà÷.




                                  Ðåöåíçåíòû:
          êàôåäðà ïðîìûøëåííîãî ìåíåäæìåíòà Ñàíêò-Ïåòåðáóðãñêîãî
            Áàëòèéñêîãî ãîñóäàðñòâåííîãî òåõíè÷åñêîãî óíèâåðñèòåòà;
                 êàíäèäàò òåõíè÷åñêèõ íàóê äîöåíò Â.Ï. Ïîïîâ



                                Óòâåðæäåíî
               ðåäàêöèîííî-èçäàòåëüñêèì ñîâåòîì óíèâåðñèòåòà
                        â êà÷åñòâå ó÷åáíîãî ïîñîáèÿ




                                          ©   Ñàíêò-Ïåòåðáóðãñêèé
                                              ãîñóäàðñòâåííûé óíèâåðñèòåò
                                              àýðîêîñìè÷åñêîãî
                                              ïðèáîðîñòðîåíèÿ, 2000

                                          ©   Ë. À. Ïðîêóøåâ, 2000



2


                            ÂÂÅÄÅÍÈÅ
   Òåîðèÿ ãðàôîâ, ÿâëÿÿñü ðàçäåëîì äèñêðåòíîé ìàòåìàòèêè, èñïîëüçó-
åòñÿ äëÿ îïèñàíèÿ è èçó÷åíèÿ îòíîøåíèé ìåæäó äèñêðåòíûìè îáúåêòà-
ìè. Ãåîìåòðè÷åñêè îáúåêòû ìîæíî ïðåäñòàâèòü â âèäå ìíîæåñòâà òî-
÷åê, íàçûâàåìûõ âåðøèíàìè ãðàôà, à îòíîøåíèÿ ìåæäó íèìè – ëèíèÿ-
ìè, ñâÿçûâàþùèìè âåðøèíû. Åñëè ëèíèè íå îðèåíòèðîâàíû, òî èõ íà-
çûâàþò ðåáðàìè, à ñàì ãðàô – íåîðèåíòèðîâàííûì, à åñëè ëèíèè îðèåí-
òèðîâàíû, òî èõ íàçûâàþò äóãàìè, à ñàì ãðàô – îðèåíòèðîâàííûì, èëè
îðãðàôîì.
   Èìåÿ â ñâîåé îñíîâå ïðîñòåéøèå èäåè è ýëåìåíòû (òî÷êè, ñîåäèíåí-
íûå ëèíèÿìè), òåîðèÿ ãðàôîâ ñòðîèò èç íèõ îãðîìíîå ìíîãîîáðàçèå ôîðì,
íàäåëÿåò ýòè ôîðìû ðàçëè÷íûìè ñâîéñòâàìè è â ðåçóëüòàòå ñòàíîâèò-
ñÿ ïîëåçíûì èíñòðóìåíòîì ïðè èññëåäîâàíèè ñàìûõ ðàçíîîáðàçíûõ ñè-
ñòåì.
    ñàìîì ïîíÿòèè ãðàôà ñî÷åòàþòñÿ òåîðåòèêî-ìíîæåñòâåííûå, êîì-
áèíàòîðíûå è òîïîëîãè÷åñêèå àñïåêòû, ÷òî äåëàåò òåîðèþ ãðàôîâ óäîá-
íûì, ïðîñòûì ÿçûêîì äëÿ ôîðìóëèðîâêè è ïîñòðîåíèÿ ìîäåëåé, à òàê-
æå ýôôåêòèâíûì è ìîùíûì èíñòðóìåíòîì ðåøåíèÿ çàäà÷, îòíîñÿùèõ-
ñÿ ê øèðîêîìó êðóãó íàó÷íûõ è èíæåíåðíûõ ïðîáëåì. Ìîæíî óïîìÿ-
íóòü â ýòîé ñâÿçè âîïðîñû êîíñòðóèðîâàíèÿ ñècòåì àâòîìàòèçèðîâàí-
íîãî ïðîåêòèðîâàíèÿ, ñèñòåì ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ è ñîçäàíèÿ
îïåðàöèîííûõ ñèñòåì, èññëåäîâàíèÿ îïåðàöèé è óïðàâëåíèÿ, ìàòåìàòè-
÷åñêîé ëèíãâèñòèêè è ðàçðàáîòêè òðàíñëÿòîðîâ, êàëåíäàðíîå ïëàíèðî-
âàíèå ïðîìûøëåííîãî ïðîèçâîäñòâà, çàäà÷è ñåòåâîãî ïëàíèðîâàíèÿ è
óïðàâëåíèÿ (ÑÏÓ), òàêòè÷åñêèå è ëîãè÷åñêèå çàäà÷è âûáîðà ëó÷øèõ
îáúåêòîâ, áîëüøîé êðóã ýêîíîìè÷åñêèõ çàäà÷, èãðîâûå çàäà÷è.
   Âìåñòî ïîíÿòèÿ ãðàôà ÷àñòî èñïîëüçóåòñÿ ïîíÿòèå “ñåòü”, êîãäà êðî-
ìå îñíîâíûõ, ÷èñòî ñòðóêòóðíûõ, îòíîøåíèé â ãðàôå çàäàþòñÿ íåêîòî-
ðûå êîëè÷åñòâåííûå õàðàêòåðèñòèêè òî÷åê è ëèíèé. Ïðè ýòîì ìîæíî
ðåøàòü ïðîáëåìû ïîñòðîåíèÿ ýëåêòðè÷åñêèõ ñåòåé, ñèñòåì ñâÿçè è èñ-
ñëåäîâàíèÿ ïðîöåññîâ ïåðåäà÷è èíôîðìàöèè, âûáîðà îïòèìàëüíûõ ìàð-
øðóòîâ è ïîòîêîâ â ñåòÿõ, íàïðèìåð ïîñòðîåíèÿ ñåòè âûïîëíåíèÿ ðà-
                                                                    3


áîò ïðè ïðîåêòèðîâàíèè èçäåëèÿ. Ïðè ýòîì ðåáðàì èëè (è) äóãàì ñåòè
ñòàâÿòñÿ â ñîîòâåòñòâèå îïðåäåëåííûå êîëè÷åñòâåííûå õàðàêòåðèñòè-
êè ýíåðãèè, çàòðàò è ïîòîêà.
   Öåëü äàííîãî êóðñà ñîñòîèò â òîì, ÷òîáû îçíàêîìèòü ñòóäåíòîâ ñ
îñíîâíûìè ïîíÿòèÿìè òåîðèè ãðàôîâ è ïåðâûìè ïðåäñòàâëåíèÿìè î
ìîäåëÿõ òåîðèè ãðàôîâ, èõ ïðèëîæåíèÿõ ê ðåøåíèþ íåêîòîðûõ ïðè-
êëàäíûõ çàäà÷ ñ èñïîëüçîâàíèåì àëãîðèòìè÷åñêîãî ïîäõîäà è ñ âîçìîæ-
íîñòüþ ïðèìåíåíèÿ ÝÂÌ.




4


         1. ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß È ÏÎÍßÒÈß


                 1.1. Ýëåìåíòû òåîðèè ìíîæåñòâ
   Äëÿ îïðåäåëåíèÿ îñíîâíûõ ïîíÿòèé òåîðèè ãðàôîâ áóäóò èñïîëü-
çîâàíû íåêîòîðûå ñâåäåíèÿ èç òåîðèè ìíîæåñòâ. Ìíîæåñòâî îáðàçó-
åòñÿ ñîâîêóïíîñòüþ äèñêðåòíûõ îáúåêòîâ, ÿâëÿþùèõñÿ ýëåìåíòàìè
ìíîæåñòâà, è îáîçíà÷àþòñÿ A = {a, b, c }, ãäå a, b, c – ýëåìåíòû
ìíîæåñòâà A.
   Ïðåäïîëàãàåòñÿ, ÷òî äëÿ êîíêðåòíûõ ýëåìåíòà à è ìíîæåñòâà À
âñåãäà ìîæíî îïðåäåëèòü, ïðèíàäëåæèò ýëåìåíò à ìíîæåñòâó À (îáî-
çíà÷àåòñÿ à∈À) èëè íå ïðèíàäëåæèò (a∉A ).
   Ìíîæåñòâî À íàçûâàåòñÿ êîíå÷íûì, åñëè â íåì ñîäåðæèòñÿ êî-
íå÷íîå ÷èñëî ýëåìåíòîâ, íàïðèìåð, À={à1, a2, …, an}. ×èñëî n íàçû-
âàåòñÿ êîëè÷åñòâîì ýëåìåíòîâ À è îáîçíà÷àåòñÿ ÷åðåç |A|. Ìíîæå-
ñòâî, ñîñòîÿùåå èç îäíîãî ýëåìåíòà, îáîçíà÷àåòñÿ ÷åðåç {a}. Ìíîæå-
ñòâî, íå ñîäåðæàùåå ýëåìåíòîâ, íàçûâàåòñÿ ïóñòûì è îáîçíà÷àåòñÿ
∅, íàïðèìåð À=∅ îçíà÷àåò, ÷òî À – ïóñòîå ìíîæåñòâî.
                1.1.1. Îïåðàöèè íàä ìíîæåñòâàìè
   Âëîæåííîñòü ìíîæåñòâ (ïîäìíîæåñòâî) – îïåðàöèÿ ⊆.
   Åñëè èç x∈A (ãäå x – ëþáîé ýëåìåíò) ñëåäóåò x∈B, òî À íàçûâàþò
ïîäìíîæåñòâîì Â (À⊆Â) è ãîâîðÿò, ÷òî À âëîæåíî â Â (À ñîäåðæèòñÿ â
Â, Â ñîäåðæèò À). Íàïðèìåð, åñëè À={à,b} è B={a, b, c}, òî À⊆Â.
   Äîïîëíåíèå ìíîæåñò⠖ îïåðàöèÿ ∪ (ñóììà).
   Ìíîæåñòâî À∪ âêëþ÷àåò âñå ýëåìåíòû ìíîæåñòâ À è  áåç ïî-
âòîðåíèÿ ýëåìåíòîâ, íàïðèìåð ïóñòü À={a, b}, B={b, c}, òîãäà À∪Â=
={a, b, c}.
   Ïåðåñå÷åíèå ìíîæåñò⠖ îïåðàöèÿ ∩.
   Ìíîæåñòâî À∩ âêëþ÷àåò ýëåìåíòû îáùèå äëÿ ìíîæåñòâ À è Â,
íàïðèìåð:
   1. Ïóñòü À={a, b}, B={b, c}, òîãäà A∩B={b}.
                                                                 5


    2. Ïóñòü A={a, b}, B={c, d}, òîãäà A∩B=∅.
    Äîïîëíåíèå ìíîæåñò⠖ îïåðàöèÿ \ (âû÷èòàíèå).
    Ìíîæåñòâî À\ âêëþ÷àåò âñå ýëåìåíòû ìíîæåñòâà À, íå ïðèíàäëå-
æàùèå Â, ò. å. èç À âû÷èòàþòñÿ ýëåìåíòû îáùèå ñ Â. Íàïðèìåð, ïóñòü
A={a, b}, B={b, c}, òîãäà A\Â={a}.
    Òåîðåòèêî-ìíîæåñòâåííîå ïðîèçâåäåíèå – îïåðàöèÿ ×.
    Ïóñòü À è  – äâà ìíîæåñòâà. ×åðåç À× îáîçíà÷èì ìíîæåñòâî,
ñîñòîÿùåå èç óïîðÿäî÷åííûõ ïàð (a,b), òàêèõ, ÷òî à∈À, b∈Â. Èíà÷å ãî-
âîðÿ, ñ∈À× òîãäà è òîëüêî òîãäà, êîãäà ñ åñòü ïàðà (a, b), ïðè÷åì à∈À,
b∈B.
    Íàïðèìåð, ïóñòü A={a, b}, B={c, d}, òîãäà À×Â={(a, c), (a, d), (b, c),
(b, d)}.
    Äëÿ îáëåã÷åíèÿ îáùåãî îïðåäåëåíèÿ ââåäåì ïîíÿòèå ïðîèçâåäåíèÿ
ìíîæåñòâà ñàìîãî íà ñåáÿ.
    Óïîðÿäî÷åííûì, èëè äåêàðòîâûì (ïðÿìûì), ïðîèçâåäåíèåì ìíî-
æåñòâà V ñàìîãî íà ñåáÿ (êîòîðîå îáîçíà÷àåòñÿ V×V) íàçûâàåòñÿ
ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð (s, t), ãäå s∈V è t∈V. Çäåñü (s, t) è (t,
s) ðàññìàòðèâàþòñÿ êàê ðàçëè÷íûå ýëåìåíòû, èñêëþ÷àÿ ñëó÷àé s=t.
Åñëè ÷èñëî ýëåìåíòîâ |V|=n, òî V×V ñîñòîèò èç n2 óïîðÿäî÷åííûõ
ïàð. Íàïðèìåð, ïóñòü V={v1, v2, v3}, òîãäà V×V={(v1, v1), (v1, v2), (v1,
v3), (v2, v1), (v2, v2), (v2, v3), (v3, v1), (v3, v2), (v3, v3)}.
    Íåóïîðÿäî÷åííûì ïðîèçâåäåíèåì ìíîæåñòâà V ñàìîãî íà ñåáÿ
(îáîçíà÷èì êàê V&V) íàçûâàåòñÿ ìíîæåñòâî âñåõ ðàçëè÷íûõ íå-
óïîðÿäî÷åííûõ ïàð [s, t], ïðè ýòîì ïàðû [s, t] è [t, s] ýêâèâàëåíò-
íû è òàê æå, êàê ïðè äåêàðòîâîì ïðîèçâåäåíèè, äîïóñêàåòñÿ ñî-
âïàäåíèå ýëåìåíòîâ ïàðû, ò. å. s=t. Ïðè |V|=n ìíîæåñòâî V&V
ñîñòîèò èç n(n+1)/2 ðàçëè÷íûõ íåóïîðÿäî÷åííûõ ïàð. Íàïðèìåð,
ïóñòü V={v 1, v 2, v 3}, òîãäà V&V={[v 1, v 1], [v 1, v 2], [v 1, v 3], [v 2, v 2],
[v 2, v 3], [v 3, v 3]}.
    Ñïðàâåäëèâû îòíîøåíèÿ: A∩B⊆A, A∩B⊆B, A⊆A∪B, B⊆A∪B.
    Íàïðèìåð, åñëè A⊆B, B⊆C, òî A⊆C, ïîýòîìó èç ïðèâåäåííûõ âûøå
ñîîòíîøåíèé ñëåäóåò, ÷òî A∩B⊆A∪B.
    Ñïðàâåäëèâû òàêæå ôîðìóëû äèñòðèáóòèâíîñòè:
           (A∪B)∩C=(A∩B)∪(B∩C), (A∩B)∪C=(A∪C)∩(B∪C).
    Ðàâåíñòâî ìíîæåñò⠖ îïåðàöèÿ =.
    A=B ñïðàâåäëèâî òîãäà è òîëüêî òîãäà, êîãäà A⊆B è A⊆B.

6


                                   1.1.2. Îòíîøåíèå
   Ââåäåì ïîíÿòèå îòíîøåíèÿ. Ãîâîðÿò, ÷òî íà A çàäàíî îòíîøåíèå R,
åñëè çàäàíî ïîäìíîæåñòâî R äåêàðòîâà ïðîèçâåäåíèÿ À×À (R⊆A×A).
Ýëåìåíò à∈À íàõîäèòñÿ â îòíîøåíèè R ê ýëåìåíòó b∈A (çàïèñûâàåòñÿ
êàê aRb) òîãäà è òîëüêî òîãäà, êîãäà (a,b)∈R. Ïðè ýòîì ñóùåñòâåí ïîðÿ-
äîê ýëåìåíòîâ: ìîæåò áûòü, ÷òî à íàõîäèòñÿ â îòíîøåíèè R ê ýëåìåíòó
b, íî b íå íàõîäèòñÿ â îòíîøåíèè R ê à.
   Îòíîøåíèå íàçûâàåòñÿ: à) ñèììåòðè÷íûì, åñëè aRb òîãäà è òîëüêî
òîãäà, êîãäà bRa; á) ðåôëåêñèâíûì, åñëè äëÿ ëþáîãî a∈A aRa; â) òðàí-
çèòèâíûì, åñëè èç aRb è bRc ñëåäóåò aRc; ã) àíòèñèììåòðè÷íûì, åñëè
èç aRb è bRa ñëåäóåò a=b.
   Èç ìíîæåñòâà âñåõ îòíîøåíèé âûäåëÿåòñÿ êëàññ îòíîøåíèé, îäíî-
âðåìåííî ñèììåòðè÷íûõ, òðàíçèòèâíûõ è ðåôëåêñèâíûõ. Òàêèå îòíî-
øåíèÿ íàçûâàþòñÿ îòíîøåíèÿìè ýêâèâàëåíòíîñòè.
                                  1.1.3. Îòîáðàæåíèå
    Òåðìèíû îòîáðàæåíèå (êàê ïîíÿòèå îäíîçíà÷íîãî ñîîòâåòñòâèÿ) è
ôóíêöèÿ áóäóò ðàññìàòðèâàòüñÿ êàê ñèíîíèìû. Ñ÷èòàåì, ÷òî çàäàíî îòî-
áðàæåíèå f : X→Y, åñëè êàæäîìó ýëåìåíòó x∈X ñîïîñòàâëåí ýëåìåíò
f(x)∈Y.
    Ïóñòü f: X→Y – íåêîòîðîå îòîáðàæåíèå. Åñëè A⊂X, òî îáðàçîì À
ïðè îòîáðàæåíèè f íàçûâàåòñÿ ìíîæåñòâî ýëåìåíòîâ B⊂Y òàêîå, ÷òî
y∈B òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò x∈A òàêîé, ÷òî y=f(x). Ïðî-
îáðàçîì C⊂Y ïðè îòîáðàæåíèè f íàçûâàåòñÿ ìíîæåñòâî D⊂X òàêîå, ÷òî
x∈D òîãäà è òîëüêî òîãäà, êîãäà f(x)∈C. Îáðàç è ïðîîáðàç îáîçíà÷èì
ñîîòâåòñòâåííî f(A) è f –1(C). Îïåðàöèÿ âçÿòèÿ îáðàçà èëè ïðîîáðàçà
ìíîæåñòâà óäîâëåòâîðÿþò ñîîòíîøåíèÿì:
        f    –1
                  (A∪B) = f –1(A) ∪ f –1(B), f (A∪B) = f (A) ∪ f (B);
         f   –1
                  (A∩B) = f –1(A) ∩ f –1(B), f (A∩B) ⊂ f(A) ∩ f(B);
              f   –1
                       (Y \ A) = X \ f –1(A), f (X \ A) ⊃ f (X) \ f (A).
    Îäíàêî íåëüçÿ óòâåðæäàòü, ÷òî f(A∩B)=f(A)∩f(B) è f(X\A)=f(X)\f(A).
Äîñòàòî÷íî ðàññìîòðåòü ïîñòîÿííîå îòîáðàæåíèå f : X→Y (òàêîå, ÷òî
f(x)=y0∈X äëÿ ëþáîãî x∈X).
    Îòîáðàæåíèå íàçûâàåòñÿ âçàèìíî-îäíîçíà÷íûì, åñëè f(x)=Y è äëÿ
ëþáîãî y∈Y ìíîæåñòâî f–1({y}) ñîñòîèò èç îäíîãî ýëåìåíòà. Íåòðóäíî
                                                                           7


âèäåòü, ÷òî îïðåäåëåíî îòîáðàæåíèå f –1: Y→X. Èìåííî, f –1(y)=a òîãäà
è òîëüêî òîãäà, êîãäà f –1({y})={a}.

                          1.2. Îñíîâíûå ïîíÿòèÿ äëÿ ãðàôîâ
                   1.2.1. Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ
   Ïðåæäå ÷åì îïðåäåëèòü ïîíÿòèå ãðàôà â íàèáîëåå îáùåé ôîðìå, ïî-
ëåçíî ðàññìîòðåòü ãåîìåòðè÷åñêóþ ôîðìó ãðàôîâ. Ýòî ïîçâîëèò ñ ñà-
ìîãî íà÷àëà ïîëó÷èòü óäîáíîå, íàãëÿäíîå ïðåäñòàâëåíèå ðàçëè÷íûõ ïî-
íÿòèé è ñòðóêòóð, êîòîðûå áóäóò ðàññìàòðèâàòüñÿ â äàëüíåéøåì. Ëþ-
áîé ãðàô â àáñòðàêòíîì ñìûñëå ýêâèâàëåíòåí (ïî îòíîøåíèþ ê ñâîé-
ñòâàì, èçó÷àåìûì â òåîðèè ãðàôîâ) íåêîòîðîìó ãåîìåòðè÷åñêîìó ãðà-
ôó. Ïðè íåêîòîðîé èäåàëèçàöèè ìíîãèå èçâåñòíûå ñòðóêòóðû ìîæíî
ðàññìàòðèâàòü êàê ãåîìåòðè÷åñêèå ãðàôû è èçó÷àòü ñ ïîìîùüþ ìåòî-
äîâ òåîðèè ãðàôîâ. Íàïðèìåð, â âèäå ãðàôà ìîæíî ïðåäñòàâèòü ñèñòå-
ìó èëè ñåòü óëèö â ãîðîäå, åñëè ïðåíåáðå÷ü øèðèíîé ïîñëåäíèõ, à ïåðå-
ñå÷åíèÿ ñ÷èòàòü òî÷êàìè.
   Ãåîìåòðè÷åñêèé ãðàô åñòü ãåîìåòðè÷åñêàÿ êîíôèãóðàöèÿ èëè ñòðóê-
òóðà â ïðîñòðàíñòâå, ñîñòîÿùàÿ èç ìíîæåñòâà òî÷åê, âçàèìîñâÿçàííûõ
ìíîæåñòâîì íåïðåðûâíûõ, ñàìîíåïåðåñåêàþùèõñÿ êðèâûõ.
   Íà ðèñ. 1.1 ïîêàçàíî îáû÷íîå ïðåäñòàâëåíèå ãåîìåòðè÷åñêîãî ãðàôà,
ñ ïîìîùüþ êîòîðîãî ìîæíî ïðîèëëþñòðèðîâàòü íåêîòîðûå òåðìèíû
òåîðèè ãðàôîâ.
   Ñ ïîçèöèè òåîðèè ãðàôîâ ýëåìåíòû v íàçûâàþòñÿ âåðøèíàìè ãðàôà,
à ñîåäèíÿþùèå èõ íåîðèåíòèðîâàííûå ëèíèè (u) ðåáðàìè èëè äóãàìè,
åñëè ëèíèè ñíàáæåíû ñòðåëêàìè, è òîãäà ðàçëè÷àþò íåîðèåíòèðîâàí-
íûé ãðàô (ðèñ.1.1,à) èëè îðèåíòèðîâàííûé ãðàô (ñîêðàùåííî îðãðàô)
(ðèñ.1.1,á). Åñëè ìíîæåñòâî âåðøèí (V) è ðåáåð (äóã) (U) êîíå÷íî, òî ãðàô
íàçûâàåòñÿ êîíå÷íûì. Ìû áóäåì ðàññìàòðèâàòü òîëüêî êîíå÷íûå ãðàôû.

    a)        v!             v"             v$   á              v         u$
                                                                                 v!
                     u                                    u                         u%
                                        u#            v
         u!    u"             v v #                            u!
                                                                      u"
                                                                            u#
                      u                u$              u
         v                                                           v!

                   Ðèñ. 1.1. Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ:
              à – íåîðèåíòèðîâàííûé ãðàô; á – îðèåíòèðîâàííûé ãðàô
8


    Âåðøèíû, ñâÿçàííûå ðåáðîì èëè äóãîé, íàçûâàþòñÿ ñìåæíûìè. Åñëè
ñìåæíûå âåðøèíû ñâÿçàíû áîëåå ÷åì îäíèì ðåáðîì èëè äóãîé, òî òà-
êèå ðåáðà (äóãè) íàçûâàþòñÿ êðàòíûìè, èëè ïàðàëëåëüíûìè (u3, u4 íà
ðèñ. 1.1,à; u2, u3 – íà ðèñ. 1.1,á), à ñàì ãðàô íàçûâàåòñÿ ìóëüòèãðàôîì, ò.
å. ãðàôû íà ðèñ. 1.1 ÿâëÿþòñÿ ìóëüòèãðàôàìè. Âåðøèíû, íåñâÿçàííûå ñ
äðóãèìè, íàçûâàþòñÿ èçîëèðîâàííûìè, íàïðèìåð, v4 íà ðèñ. 1.1,à. Ðåá-
ðî (äóãà), íà÷èíàþùååñÿ è çàêàí÷èâàþùååñÿ â îäíîé òî÷êå, íàçûâàåòñÿ
ïåòëåé (ïåòëè u6 – íà ðèñ. 1.1,à è u7 – íà ðèñ. 1.1,á). Ãîâîðÿò, ÷òî ðåáðî
(äóãà) è åãî ãðàíè÷íûå òî÷êè èíöèäåíòíû äðóã äðóãó, èíà÷å ãîâîðÿ,
âåðøèíû, èíöèäåíòíûå ðåáðó (äóãå), ÿâëÿþòñÿ åãî êîíöåâûìè òî÷êà-
ìè, íàïðèìåð, íà ðèñ. 1.1,à ðåáðó u1 èíöèäåíòíû âåðøèíû v1 è v3, à
âåðøèíå v3 èíöèäåíòíû ðåáðà u1, u3, u4.
    Âîîáùå ãîâîðÿ, ìíîæåñòâî äóã U (íî íå âåðøèí V) ìîæåò áûòü ïóñ-
òûì, òîãäà ãîâîðÿò, ÷òî ãðàô âûðîæäåííûé.
                      1.2.2. Àáñòðàêòíûå ãðàôû
   Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ, ÿâëÿÿñü íàãëÿäíûì, òðóäíî
ïîääàåòñÿ ìàòåìàòè÷åñêîé îáðàáîòêå, ïîýòîìó íåîáõîäèìî åãî ôîðìà-
ëèçîâàòü è ïðåäñòàâèòü îïðåäåëåíèå ãðàôà â áîëåå îáùåì àáñòðàêòíîì
âèäå. Õîòÿ ìíîãèå ãðàôû, ïðåäñòàâëÿþùèå ðåàëüíûå îáúåêòû (ïîñëå èõ
èäåàëèçàöèè), ÿâëÿþòñÿ ãåîìåòðè÷åñêèìè ãðàôàìè, ñ òî÷êè çðåíèÿ òåî-
ðèè ãðàôîâ, èõ åäèíñòâåííàÿ ñòðóêòóðíàÿ îñîáåííîñòü ñîñòîèò â òîì,
÷òî ñ êàæäûì ðåáðîì ñâÿçàíû äâå (âîçìîæíî ñîâïàäàþùèå) âåðøèíû.
Òàêèå ðåáðà (äóãè) è âåðøèíû áûëè îïðåäåëåíû âûøå êàê âçàèìíî
èíöèäåíòíûå. Ïîíÿòèå èíöèäåíòíîñòè ðåáåð (äóã) è èõ êîíöåâûõ âåð-
øèí ÿâëÿåòñÿ ôóíäàìåíòàëüíûì â òåîðèè ãðàôîâ, êîòîðàÿ ïîñòðîåíà ñ
ó÷åòîì èìåííî ýòîé îñîáåííîñòè è íå ó÷èòûâàåò ðåàëüíîé ïðèðîäû
âåðøèí è ðåáåð (äóã).
   Ââåäåíèå ïîíÿòèÿ àáñòðàêòíîãî ãðàôà ïîçâîëÿåò, âî-ïåðâûõ, èçáà-
âèòüñÿ îò ñëó÷àéíûõ ãåîìåòðè÷åñêèõ õàðàêòåðèñòèê, ñîõðàíèâ íàèáî-
ëåå ñóùåñòâåííûå êîìáèíàòîðíûå ñâîéñòâà ãðàôà, âî-âòîðûõ, ðàñøè-
ðèòü âîçìîæíîñòè ïðèëîæåíèÿ òåîðèè, òàê êàê ìíîãèå ðåàëüíûå ñòðóê-
òóðû èìåþò êîìáèíàòîðíûå ñâîéñòâà, êîòîðûå ïîëåçíî èññëåäîâàòü ñ
ïîìîùüþ ìàòåìàòè÷åñêîãî àïïàðàòà òåîðèè ãðàôîâ. Íàïðèìåð, ïðè ïðî-
åêòèðîâàíèè ñëîæíîãî èçäåëèÿ (òåõíè÷åñêîãî èëè ïðîãðàììíîãî) â âèäå
ãðàôà ìîæíî çàäàòü ñîîòíîøåíèå ìåæäó îòäåëüíûìè ðàáîòàìè, êîòî-
ðûå ñîñòàâëÿþò ñëîæíûå ïðîåêòû.  ýòîì ñëó÷àå âåðøèíû ïðåäñòàâëÿ-
                                                                          9


þò îòäåëüíûå ðàáîòû, à îòíîøåíèÿ èíöèäåíòíîñòè ãðàôà îòðàæàþò ïîñ-
ëåäîâàòåëüíîñòü âûïîëíåíèÿ îïðåäåëåííûõ ðàáîò.
   Ôîðìàëèçàöèÿ ãðàôà ìîæåò ïðèíèìàòü ðàçíûå ôîðìû, êîòîðûå ìû
ðàññìîòðèì äàëåå. Íàïðèìåð, íèæåñëåäóþùàÿ òàáëèöà ñîäåðæèò
âñþ èíôîðìàöèþ, íåîáõîäèìóþ äëÿ îïèñàíèÿ ãåîìåòðè÷åñêîãî ãðà-
ôà (ðèñ. 1.1,à):

                                      Âåðøèíû, ñîîòâåòñòâóþùèå,
                   Ðåáðà
                                       ò. å. èíöèäåíòíûå, ðåáðàì
                     u1                         v 1, v 3
                     u2                         v 1, v 2
                     u3                         v 1, v 3
                     u4                         v 2, v 3
                     u5                         v 5, v 6
                     u6                           v5
                                                  v4


   Ïîñêîëüêó ôîðìàëèçàöèÿ è îïåðàöèè äëÿ íåîðèåíòèðîâàííûõ è îðè-
åíòèðîâàííûõ ãðàôîâ èìåþò îòëè÷èÿ, ïðèâåäåì èõ àáñòðàêòíûå îïèñà-
íèÿ îòäåëüíî.
                       1.3. Îñíîâíûå ïîíÿòèÿ
                   äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ

     1.3.1. Àáñòðàêòíûå îïèñàíèÿ íåîðèåíòèðîâàííûõ ãðàôîâ
  Ïóñòü V – íåïóñòîå ìíîæåñòâî âåðøèí ãðàôà v∈V. Ðåáðîì, ñîåäèíÿ-
þùèì äâå âåðøèíû vi è vj, íàçûâàåòñÿ íåóïîðÿäî÷åííàÿ ïàðà [vi, vj] èëè

                                  (       )
[vj, vi]. Ðåáðî îáîçíà÷àåòñÿ u = vi , v j èëè u =  v j , vi  , à ìíîæåñòâî
                                                            
ðåáåð ãðàôà îáîçíà÷àåòñÿ U .
   Ìíîæåñòâî ðåáåð U ÿâëÿåòñÿ êîíå÷íûì ïîäìíîæåñòâîì íåóïîðÿäî-
÷åííîãî ïðîèçâåäåíèÿ V&V ñ ýëåìåíòàìè âèäà [v, w], ãäå v, w∈V è äîïó-
ñòèìî ñîâïàäåíèå ýëåìåíòîâ ïàðû v = w.
   Òîãäà ãðàô G ìîæíî îïðåäåëèòü êàê ñîâîêóïíîñòü íåïóñòîãî êîíå÷-
íîãî ìíîæåñòâà âåðøèí V è ìíîæåñòâà ðåáåð U (âîçìîæíî ïóñòîãî) è

10



    
Яндекс цитирования Яндекс.Метрика