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

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

Голосов: 13

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    òåëüíîé íóìåðàöèåé ðåáåð è âåðøèí âíóòðè êàæäîé êîìïîíåíòû è ìåæäó
êîìïîíåíòàìè, êàê ïîêàçàíî â ïðèìåðå, èëè íåïîñðåäñòâåííî ñ ïîìî-
ùüþ ïîäñòàíîâêè ñòðîê è ñòîëáöîâ ìàòðèöû èíöèäåíöèé.
   Ìîæíî óòâåðæäàòü, ÷òî äâà ãðàôà èçîìîðôíû, åñëè îíè èìåþò îäíè
è òå æå ìàòðèöû èíöèäåíöèé ñ òî÷íîñòüþ äî ïåðåñòàíîâîê ñòðîê è ñòîë-
áöîâ. Òàêèì îáðàçîì, ìàòðèöà èíöèäåíöèé îáåñïå÷èâàåò ïîëíîå îïèñà-
íèå ãðàôà (åñëè ïåòëè èñêëþ÷åíû).
                    Ìàòðèöà ñìåæíîñòè âåðøèí
   Äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ ìîæíî îïðåäåëèòü ìàòðèöó ñìåæ-
íîñòè âåðøèí (èëè ïðîñòî ìàòðèöó ñìåæíîñòè). Ýòî êâàäðàòíàÿ ìàòðè-
öà S-ðàçìåðà n×n, ãäå ñòðîêè è ñòîëáöû ñîîòâåòñòâóþò âåðøèíàì ãðàôà,
à ýëåìåíò si j ðàâåí ÷èñëó ðåáåð, èíöèäåíòíûõ îäíîâðåìåííî i-é è j-é
âåðøèíàì. Òàêèì îáðàçîì, äëÿ ãðàôà íà ðèñ. 1.11 èìååì ìàòðèöó ñìåæ-
íîñòè
                             L1 L2 L3 L4 L5 L6 L7
                        L1   1 1 0 0 0 0 0
                        L2   1 0 1 1 0 0 0
                        L    0 1 0 1 0 0 0
                  S7×7= 3
                        L4   0 1 1 0 0 0 0 .
                        L5   0 0 0 0 0 2 1
                        L6   0 0 0 0 2 0 1
                        L7   0 0 0 0 1 1 0

   Ìàòðèöà ñìåæíîñòè íåîðèåíòèðîâàííîãî ãðàôà (áåç ïåòåëü) ñèììåò-
ðè÷íà îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, ïîñêîëüêó ïàðå âåðøèí (vi, vj)
èíöèäåíòíû îäèíàêîâûå ðåáðà [vi, vj]=[vj, vi], ò. å. äîñòàòî÷íî ðàññìàò-
ðèâàòü òîëüêî ïîëîâèíó ìàòðèöû âûøå ãëàâíîé äèàãîíàëè. Î÷åâèäíî,
÷òî ìàòðèöà ñìåæíîñòè îáûêíîâåííîãî ãðàôà (áåç ïåòåëü è êðàòíûõ
ðåáåð) ÿâëÿåòñÿ áóëåâîé ìàòðèöåé.
             1.3.10. Èçîìîðôèçì ãðàôîâ. Ïëîñêèé ãðàô
   Âåðíåìñÿ ê ïîíÿòèþ ãåîìåòðè÷åñêîãî ãðàôà, ðàñøèðèâ åãî. Îáîçíà-
÷èì n-ìåðíîå åâêëèäîâî ïðîñòðàíñòâî εn. Åâêëèäîâî n-ìåðíîå ïðî-
ñòðàíñòâî åñòü ìíîæåñòâî ïîñëåäîâàòåëüíîñòåé èç n äåéñòâèòåëü-
íûõ ÷èñåë x = (x1, … , xn), â êîòîðîì ðàññòîÿíèå ìåæäó ëþáûìè äâóìÿ
òî÷êàìè x = (x1, … ,xn) è y = (y1, … , yn) îïðåäåëåíî ñëåäóþùèì îáðàçîì:
                                                                     21


                                         n
                         d ( x, y ) =   ∑ ( xi − yi )2    .
                                        i =1

    Ïðîñòîé íåçàìêíóòîé êðèâîé â ïðîñòðàíñòâå εn íàçûâàåòñÿ íåïðåðûâ-
íàÿ, ñàìîíåïåðåñåêàþùàÿñÿ êðèâàÿ, ñîåäèíÿþùàÿ äâå ðàçëè÷íûå òî÷êè â
εn (ò. å. êðèâàÿ, ïîëó÷åííàÿ íåïðåðûâíîé äåôîðìàöèåé ïðÿìîëèíåéíîãî
îòðåçêà). Àíàëîãè÷íî ïðîñòîé çàìêíóòîé êðèâîé íàçûâàåòñÿ íåïðåðûâíàÿ
ñàìîíåïåðåñåêàþùàÿñÿ êðèâàÿ, êîíå÷íûå òî÷êè êîòîðîé ñîâïàäàþò.
    Ãåîìåòðè÷åñêèé ãðàô â ïðîñòðàíñòâå εn åñòü ìíîæåñòâî V={vi} òî÷åê
ïðîñòðàíñòâà εn è ìíîæåñòâî U={ui} ïðîñòûõ êðèâûõ, óäîâëåòâîðÿþùèõ
ñëåäóþùèì óñëîâèÿì:
    1. Êàæäàÿ çàìêíóòàÿ êðèâàÿ â U ñîäåðæèò òîëüêî îäíó òî÷êó v∈V.
    2. Êàæäàÿ íåçàìêíóòàÿ êðèâàÿ â U ñîäåðæèò ðîâíî äâå òî÷êè ìíîæåñòâà
V, êîòîðûå ÿâëÿþòñÿ åå ãðàíè÷íûìè òî÷êàìè.
    3. Êðèâûå â U íå èìåþò îáùèõ òî÷åê, çà èñêëþ÷åíèåì òî÷åê èç ìíîæå-
ñòâà V.
    Ðàíåå áûëî îòìå÷åíî, ÷òî ëþáîé ãðàô â àáñòðàêòíîì ñìûñëå èäåíòè-
÷åí, èëè, èñïîëüçóÿ áîëåå ïðèíÿòûé òåðìèí, èçîìîðôåí íåêîòîðîìó ãåî-
ìåòðè÷åñêîìó ãðàôó.
    Ãîâîðÿò, ÷òî ãðàôû G=(V, U ) è G'=(V', U ') èçîìîðôíû äðóã äðóãó, åñëè
ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòíîøåíèå ìåæäó V è V' è ìåæäó U è
U ', ñîõðàíÿþùåå îòíîøåíèå èíöèäåíòíîñòè. Èíà÷å ãîâîðÿ, ðåáðî u èí-
öèäåíòíî âåðøèíå v ãðàôà G òîãäà è òîëüêî òîãäà, êîãäà èíöèäåíòíû ñîîò-
âåòñòâóþùèå ýëåìåíòû u ' è v' â ãðàôå G'. Åñëè ãðàô G èçîìîðôåí ãåî-
ìåòðè÷åñêîìó ãðàôó G', òî G' íàçûâàåòñÿ ãåîìåòðè÷åñêîé ðåàëèçàöèåé ãðàôà G.
    Ãðàô íàçûâàåòñÿ ïëîñêèì òîãäà è òîëüêî òîãäà, êîãäà îí èìååò ãåîìåòðè-
÷åñêóþ ðåàëèçàöèþ â ïðîñòðàíñòâå ε2, ò. å. íà ïëîñêîñòè. Íàïðèìåð, ãðàô
G íà ðèñ. 1.12,à – ïëîñêèé, òàê êàê îí èçîìîðôåí ãðàôó G', èçîáðàæåí-
íîìó ðÿäîì.

 à    G:                                      á)        G’:
        v                  v


                                               v             v   v!   v"
         v!                v"
                     Ðèñ. 1.12. Ïëîñêèé ãðàô
22


   Ðèñ. 1.12 èëëþñòðèðóåò î÷åâèäíûé, íî âàæíûé ôàêò: ãåîìåòðè÷åñ-
êèé ãðàô ìîæåò áûòü ïëîñêèì, äàæå åñëè åãî íåëüçÿ ïðåîáðàçîâàòü â
ïëîñêèé ãðàô ñ ïîìîùüþ íåïðåðûâíîé äåôîðìàöèè. Õîòÿ G è G' èìåþò
ñóùåñòâåííûå îòëè÷èÿ ñ òî÷êè çðåíèÿ òîïîëîãèè, ñ òî÷êè çðåíèÿ òåî-
ðèè ãðàôîâ îíè ýêâèâàëåíòíû.
   Îáûêíîâåííûé ïîëíûé ãðàô, êîòîðûé                    v
èìååò íàèìåíüøåå ÷èñëî âåðøèí è íå
ÿâëÿåòñÿ ïëîñêèì, åñòü ïîëíûé ãðàô èç
                                           v#                     v
ïÿòè âåðøèí (ðèñ. 1.13).
   Åñëè â ïðîñòðàíñòâå ε2 òîëüêî îãðà-
íè÷åííûé êëàññ êîíå÷íûõ ãðàôîâ èìååò
ãåîìåòðè÷åñêóþ ðåàëèçàöèþ, òî äëÿ ïðî-
ñòðàíñòâà ε3 ñïðàâåäëèâî ñëåäóþùåå óò-
                                               v"             v!
âåðæäåíèå: ëþáîé êîíå÷íûé ãðàô G èìå-
åò ãåîìåòðè÷åñêóþ ðåàëèçàöèþ â ε3.         Ðèñ. 1.13. Íåïëîñêèé ãðàô
   Î÷åâèäíî, ÷òî åñëè ëþáîé ãðàô ñîäåð-
æèò òàêîé ïÿòèâåðøèííûé ãðàô (èëè, âîîáùå, ëþáîé íåïëîñêèé ãðàô)
â êà÷åñòâå ïîäãðàôà, òî îí îáÿçàòåëüíî íåïëîñêèé.

                     1.4. Îñíîâíûå ïîíÿòèÿ
                  äëÿ îðèåíòèðîâàííûõ ãðàôîâ
   Âî ìíîãèõ ñëó÷àÿõ ïðè îïèñàíèè ãðàôà ëèíèÿì, ñîåäèíÿþùèì âåð-
øèíû ãðàôà, íåîáõîäèìî çàäàòü îðèåíòàöèþ (íàïðàâëåíèå), è òîãäà ëè-
íèè íàçûâàþòñÿ äóãàìè (ñòðåëêàìè), à ãðàô – îðèåíòèðîâàííûì (îðãðà-
ôîì). Ñòðóêòóðíîå ðàçëè÷èå ìåæäó íåîðèåíòèðîâàííûì ãðàôîì è îðã-
ðàôîì ñîñòîèò â òîì, ÷òî â ïåðâîì ñëó÷àå ãðàíè÷íûå òî÷êè ðåáðà îáðà-
çóþò íåóïîðÿäî÷åííóþ, à âî âòîðîì – óïîðÿäî÷åííóþ ïàðó âåðøèí. Íà
ðèñ. 1.14 ïîêàçàíî, ÷òî ðåáðî ýêâèâàëåíòíî ïðîòèâîïîëîæíî íàïðàâ-
ëåííûì äóãàì.
            à                        á

            vi                vj           vi             vj

                      Ðèñ. 1.14. Ðåáðî è äóãè ãðàôà

  Íåîáõîäèìîñòü ââåäåíèÿ îðèåíòàöèè ëèíèé ãðàôà âîçíèêàåò ïî äâóì
ïðè÷èíàì. Âî-ïåðâûõ, äóãà ïðåäñòàâëÿåò îòíîøåíèå ìåæäó ïàðîé íå-
                                                                 23


ñèììåòðè÷íûõ âåðøèí. Íàïðèìåð, â ñèñòåìå ãîðîäñêèõ óëèö íåîáõîäè-
ìî èçîáðàçèòü óëèöû ñ îäíîñòîðîííèì äâèæåíèåì. Âî-âòîðûõ, ââåäå-
íèå îðèåíòàöèè íåîáõîäèìî äëÿ óñòàíîâëåíèÿ ñèñòåìû êîîðäèíàò è óñ-
òðàíåíèÿ íåîäíîçíà÷íîñòåé. Íàïðèìåð, ïðè ñîåäèíåíèè ýëåêòðè÷åñêèõ
ïðèáîðîâ îäíî íàïðàâëåíèå íåîáõîäèìî îáîçíà÷èòü êàê “ïîëîæèòåëü-
íîå” äëÿ òîãî, ÷òîáû îäíîçíà÷íî îïèñàòü ðàñïðåäåëåíèå ýëåêòðè÷åñêî-
ãî òîêà.
    Ïðåäñòàâèì ôîðìàëüíîå îïèñàíèå îðãðàôà, îïèðàÿñü íà ñòðóêòóð-
íûå òåðìèíû, ââåäåííûå äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ.
    Îðãðàô G ìîæíî îïðåäåëèòü êàê ñîâîêóïíîñòü G=(V, U), ãäå
V={v1, … , vn} – ìíîæåñòâî âåðøèí ãðàôà, à U⊂V×V – êîíå÷íîå ïîä-
ìíîæåñòâî óïîðÿäî÷åííîãî (äåêàðòîâà) ïðîèçâåäåíèÿ V×V, îáðàçóþùåå
ìíîæåñòâî äóã ãðàôà.
    Äóãó (ñòðåëêó), ñîåäèíÿþùóþ âåðøèíû vi, vj, îáîçíà÷àþò (vi, vj), ãäå
vi – íà÷àëî äóãè, à vj – êîíåö äóãè. Ãîâîðÿò, ÷òî äóãà íàïðàâëåíà îò
âåðøèíû vi ê âåðøèíå vj, èëè, ÷òî äóãà èñõîäèò èç âåðøèíû vi è âõîäèò â
âåðøèíó vj. Äëÿ óäîáñòâà äóãè òàêæå îáîçíà÷àþò îäíîé áóêâîé: uij=(vi, vj),
uk=(vi, vj) èëè u=(vi, vj). Ïðèìåð îðãðàôà ïðèâåäåí íà ðèñ. 1.15.

                        v                                        L1 L2 L3 L4 L5
         u                            V                   L1   0 1 0 0 0
                                  u!
  v           u             u"             v!              L    1 0 2 0 0
                                                      S5×5= 2
                            u$                   u#         L3   0 0 1 1 0
          u%                 u&
                   v"           u'                          L4   1 0 0 0 0
                            v#
                                                            L5   0 0 0 1 1
       Ðèñ. 1.15. Îðèåíòèðîâàííûé ãðàô è åãî ìàòðèöà ñìåæíîñòè
   Îðãðàô íà ðèñ. 1.15 ñîñòîèò èç ìíîæåñòâà âåðøèí V={v1,v2,v3,v4,v5}
è ìíîæåñòâà äóã U={u1=(v1, v2), u2=(v2, v1), u3=(v2, v3), u4=(v2, v3), u5=
=(v3, v3), u6=(v3, v4), u7=(v4, v1), u8=(v5, v4), u9=(v5, v5)}.
                        Ìàòðèöà ñìåæíîñòè âåðøèí îðãðàôà
   Îðãðàô ìîæíî îïèñàòü êâàäðàòíîé ìàòðèöåé ñìåæíîñòè Sn×n, ãäå
n = | S | – êîëè÷åñòâî âåðøèí ãðàôà, à ýëåìåíò sij ðàâåí êîëè÷åñòâó
äóã (vi, vj), ò. å. ñòðåëîê, èäóùèõ îò âåðøèíû vi ê vj (ðèñ. 1.15).
   Ñìåæíûìè äóãàìè íàçûâàþòñÿ äóãè, èìåþùèå îáùóþ ãðàíè÷íóþ
òî÷êó, íàïðèìåð, äóãè u1, u2, u3, u4 ñìåæíûå îòíîñèòåëüíî âåðøèíû v2
(ðèñ. 1.15).
24


   Ñìåæíûìè âåðøèíàìè íàçûâàþòñÿ äâå ðàçëè÷íûå âåðøèíû vi, vj,
åñëè ñóùåñòâóåò õîòÿ áû îäíà äóãà, èäóùàÿ îò îäíîé èç íèõ ê äðóãîé,
íàïðèìåð, âåðøèíû v1 è v2, v1 è v4 ñìåæíû, à v1 è v3 íå ñìåæíû (ðèñ.1.15).
   Ïåòëåé íàçûâàåòñÿ äóãà (vi, vi), ãäå íà÷àëî è êîíåö äóãè ñîâïàäàþò,
íàïðèìåð, ïåòëè u5=(v3, v3) è u9=(v5, v5) (ðèñ. 1.15).
   Êðàòíûìè íàçûâàþòñÿ äóãè, ãðàíè÷íûå òî÷êè êîòîðûõ ñîâïàäàþò.
Ïðè ýòîì åñëè a1=(v, w) è b2=(v, w), òî äóãè a1 è b2 íàçûâàþòñÿ ïàðàë-
ëåëüíûìè, à åñëè c3 = (w, v), òî äóãè a1 è c3 áóäåì íàçûâàòü âñòðå÷íûìè.
Íàïðèìåð, ó ãðàôà íà ðèñ.1.15 åñòü êðàòíûå ïàðàëëåëüíûå äóãè u3 è u4
è âñòðå÷íûå äóãè u1 è u2. Ãðàô áåç ïàðàëëåëüíûõ äóã îïèñûâàåòñÿ áóëå-
âîé ìàòðèöåé ñìåæíîñòè.
   Ìóëüòèãðàôîì íàçûâàåòñÿ ãðàô ñ êðàòíûìè äóãàìè, ò. å. ãðàô íà
ðèñ. 1.15 ÿâëÿåòñÿ ìóëüòèãðàôîì.
   Äóãà è åå ãðàíè÷íûå âåðøèíû èíöèäåíòíû äðóã äðóãó. Äóãà u=(v, w)
ñ÷èòàåòñÿ ïîëîæèòåëüíî èíöèäåíòíîé åå êîíå÷íîé âåðøèíå w, ãîâîðÿò,
÷òî äóãà (ñòðåëêà) çàõîäèò â âåðøèíó w. Äóãà u ñ÷èòàåòñÿ îòðèöàòåëüíî
èíöèäåíòíîé åå íà÷àëüíîé âåðøèíå v, ãîâîðÿò, ÷òî äóãà èñõîäèò èç ýòîé
âåðøèíû.
   ×èñëî äóã, çàõîäÿùèõ â âåðøèíó v, íàçûâàåòñÿ ïîëîæèòåëüíîé ñòå-
ïåíüþ v è îáîçíà÷àåòñÿ ÷åðåç δ+(v). Îòðèöàòåëüíàÿ ñòåïåíü v îïðåäåëÿ-
åòñÿ àíàëîãè÷íî äëÿ èñõîäÿùèõ äóã è îáîçíà÷àåòñÿ δ–(v). Îðèåíòèðî-
âàííàÿ ïåòëÿ, èíöèäåíòíàÿ v, ñ÷èòàåòñÿ ïîëîæèòåëüíî è îòðèöàòåëüíî
èíöèäåíòíîé ñ v. Ñòåïåíü âåðøèíû ðàâíà δ(v)= δ+(v)+ δ–(v).
   Ó÷èòûâàÿ, ÷òî êàæäàÿ äóãà ïîëîæèòåëüíî èíöèäåíòíà âåðøèíå è
îòðèöàòåëüíî èíöèäåíòíà òàêæå îäíîé âåðøèíå, ïîëó÷èì

                        ∑ δ + (v ) = ∑ δ − (v ) = U   ,
                       v∈V          v∈V
ãäå |U| îçíà÷àåò ÷èñëî äóã ãðàôà. Âûøå áûëî ïîêàçàíî äëÿ íåîðèåíòè-
ðîâàííîãî ãðàôà

                              ∑ δ( v ) = 2 U   .
                             v∈V

          1.4.1. Äóãè, èíöèäåíòíûå ïîäìíîæåñòâó âåðøèí
   Ïóñòü çàäàí ãðàô G=(V, U) è íåïóñòîå ïîäìíîæåñòâî V1 ìíîæåñòâà
V (V1⊂V). Ãîâîðÿò, ÷òî äóãà u = (vi, vj) çàõîäèò â V1, åñëè vi∉V1, à vj∈V1

                                                                       25


(êîíåö äóãè vj íàõîäèòñÿ â V1). Åñëè æå vi∈V1, à vj∉V1, òî ãîâîðÿò, ÷òî
äóãà u èñõîäèò èç V1 (íà÷àëî äóãè vi íàõîäèòñÿ â V1).  îáîèõ ñëó÷àÿõ
äóãó u íàçûâàþò èíöèäåíòíîé ïîäìíîæåñòâó V1. Îáîçíà÷èì ÷åðåç U +
                                                               V1
è U − ìíîæåñòâà äóã, çàõîäÿùèõ â V1 è èñõîäÿùèõ èç íåãî. Íàïðèìåð,
    V1
äëÿ ãðàôà íà ðèñ.1.15

            U + = {u1=(v1, v2)}, U −1 = {u2=(v2, v1), u6(v3, v4)}.
              V                    V
               1

   Åñëè ïîäìíîæåñòâî ñâîäèòñÿ ê îäíîé âåðøèíå, òî äóãó íàçûâàþò
èíöèäåíòíîé ýòîé âåðøèíå (çàõîäÿùåé â íåå èëè èñõîäÿùåé èç íåå).
   Îáîçíà÷èì ÷åðåç Ãv ïîäìíîæåñòâî âåðøèí V, ñìåæíûõ ñ v, â êîòî-
ðûå ìîæíî ïðèéòè ïî èíöèäåíòíûì äóãàì (ñòðåëêè èñõîäÿò èç v) èëè
èíà÷å ïîäìíîæåñòâî êîíöîâ äóã, èìåþùèõ íà÷àëîì âåðøèíó v. Íàïðè-
ìåð, äëÿ ãðàôà íà ðèñ. 1.15
       Ãv1 = {v2}, Ãv2 = {v1, v3}, Ãv3 = {v3, v4}, Ãv4 = {v1}, Ãv5 = {v4, v5}.
   Ïî ìàòðèöå ñìåæíîñòè S ìîæíî âûäåëèòü ïîäìíîæåñòâî Ãvi ïî i-é
ñòðîêå, ãäå íåíóëåâûå ýëåìåíòû sij óêàçûâàþò íà âåðøèíû vj∈Ãvi. Ýòî
îòîáðàæåíèå èíöèäåíòíîñòè è ñìåæíîñòè ïîçâîëÿåò îïðåäåëèòü ãðàô
êàê ïàðó G=(V, Ã), îáðàçîâàííóþ ìíîæåñòâîì âåðøèí V è ìíîãîçàäà÷-
íûì îòîáðàæåíèåì Ã ìíîæåñòâà V â ñåáÿ. Ýëåìåíò vi∈V íàçûâàþò âåð-
øèíîé, à ïàðó (vi, vj), ãäå vj∈Ãvi, äóãîé. Ãðàô G èìååò ïîðÿäîê n, åñëè
÷èñëî âåðøèí |V|=n.
   Îòîáðàæåíèå Ã ìîæíî îïðåäåëèòü äëÿ ëþáîãî ïîäìíîæåñòâà èç V,
íàïðèìåð äëÿ ãðàôà íà ðèñ. 1.15
              Ã{v1, v2} = Ãv1 ∪ Ãv2 = {v2}∪{v1, v3} = {v1, v2, v3}.
     Îïðåäåëèì ãðàô G–1 ñ ïîìîùüþ îáðàòíîãî îòîáðàæåíèÿ Ö1:
                                  G–1 = (V, Ö1).
   Ñîîòâåòñòâóþùèå ïðåäñòàâëåíèÿ ãðàôà G–1 ïîëó÷àþòñÿ, åñëè Ö1v
ðàññìàòðèâàòü êàê ïîäìíîæåñòâà âåðøèí, ñìåæíûõ ñ v, èç êîòîðûõ ìîæíî
çàéòè â âåðøèíó v ïî èíöèäåíòíûì äóãàì, ïðè ýòîì ìàòðèöà ñìåæíîñ-
òè ãðàôà G–1 îáðàçóåòñÿ òðàíñïîíèðîâàíèåì (ïåðåñòàíîâêîé ñòðîê è
ñòîëáöîâ) ìàòðèöû ñìåæíîñòè ãðàôà G. Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.15
     Ö1v1={v2, v4}, Ö1v2={v1}, Ö1v3={v2, v3}, Ö1v4={v3, v5}, Ö1v5={v5}.

26


   Ïî òðàíñïîíèðîâàííîé ìàòðèöå ñìåæíîñòè S ò ìîæíî âûäåëèòü Ö1vi
ïî i-é ñòðîêå, ãäå íåíóëåâûå ýëåìåíòû s òij óêàçûâàþò íà âåðøèíû
vj∈ Ö1vi :
                                       L1 L2 L3 L4 L5
                              L1       0 1 0 1 0
                         Ò    L        1 0 0 0 0
                        S5×5= 2                       .
                              L3       0 2 1 0 0
                              L4       0 0 1 0 1
                              L5       0 0 0 0 1


                1.4.2. Ðàçäåëåíèå îðãðàôà íà ñîñòàâëÿþùèå
   Ñóãðàôîì G'=(V, Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô, åñëè (∀vi∈V)
(Ã'vi ⊆ Ãvi), ò. å. èç èñõîäíîãî ãðàôà óäàëÿåòñÿ íåêîòîðîå êîëè÷åñòâî
äóã (ñ ñîõðàíåíèåì âåðøèí) (ðèñ.1.16, à,á).
   Ïîäãðàôîì G'=(V', Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô, åñëè V'⊂V è
(∀vi∈V) (Ã'vi=V'∩Ãvi), ò. å. èç èñõîäíîãî ãðàôà óäàëÿþòñÿ íåêîòîðûå âåð-
øèíû âìåñòå ñî âñåìè äóãàìè, èíöèäåíòíûìè óäàëåííîé âåðøèíå
 (ðèñ.1.16, à,â).
     ×àñòè÷íûì ïîäãðàôîì G'=(V', Ã') ãðàôà G=(V, Ã) íàçûâàåòñÿ ãðàô,
 åñëè V'⊂V, Ã'⊂Ã, ò. å. ê èñõîäíîìó ãðàôó ïðèìåíåíû îáå îïèñàííûå
âûøå îïåðàöèè (ðèñ.1.16, à, ã).

  à)                     á                     â)               ã

       v                                             v
                              v                                         v


  v                                            v                 v
                         v               v!
                   v!
           v"                     v"                     v"                 v"
                 Ðèñ. 1.16. Ðàçäåëåíèå îðãðàôà íà ïîä÷àñòè:
            à – îðãðàô ; á – ñóãðàô; ⠖ ïîäãðàô; 㠖 ÷àñòè÷íûé ãðàô

            1.4.3. Íåêîòîðûå ñïåöèàëüíûå êëàññû îðãðàôîâ
    Ñèììåòðè÷åñêèì íàçûâàåòñÿ ãðàô G=(V, U), â êîòîðîì (∀vi∈V, ∀vj∈V)
(vi, vj)∈U ⇒ (vj, vi) ∈U ( ò. å. ëþáûå äâå ñìåæíûå âåðøèíû vi è vj ñî-

                                                                            27


 à                           á                       â
      v
                                    v                        v

                   v!
 v                            v            v!         v            v!


           v"                           v"                       v"

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

åäèíåíû äâóìÿ âñòðå÷íûìè, ò. å. ïðîòèâîïîëîæíî íàïðàâëåííûìè äó-
ãàìè) (ðèñ. 1.17,à).
    Àíòèñèììåòðè÷åñêèì íàçûâàåòñÿ ãðàô G=(V,U), â êîòîðîì (∀vi∈V,
∀vj∈V) (vi, vj)∈U ⇒ (vj, vi)∉U (ïàðà ñìåæíûõ âåðøèí ìîæåò áûòü ñîåäè-
íåíà ëèøü â îäíîì íàïðàâëåíèè, ïåòëè îòñóòñòâóþò) (ðèñ.1.17,á).
    Ïîëíûì íàçûâàåòñÿ ãðàô G=(V, U), â êîòîðîì (∀v i∈V, ∀v j∈V)
(vi, vj)∉ U ⇒ (vj, vi)∈U (i ≠ j) (ëþáûå äâå âåðøèíû ñîåäèíåíû ïî êðàé-
íåé ìåðå îäíîé äóãîé, ò. å. ñìåæíû) (ðèñ. 1.17, â).
    Ðåôëåêñèâíûì áóäåì íàçûâàòü ãðàô, èìåþùèé ïåòëþ â êàæäîé âåð-
øèíå.
    Òðàíçèòèâíûì íàçûâàåòñÿ ãðàô, â êîòîðîì èç íàëè÷èÿ äóã u1=(v, v') è
u2=(v', v'') ñëåäóåò ñóùåñòâîâàíèå äóãè u3=(v, v''). Òàêèì îáðàçîì â òðàí-
çèòèâíîì ãðàôå ñóùåñòâîâàíèå ëþáîãî ïóòè èç âåðøèíû v â âåðøèíó
w îçíà÷àåò ñóùåñòâîâàíèå äóãè èç v â w.
    Ïîëíûì ãðàôîì ñ ïåòëÿìè íàçûâàåòñÿ ãðàô G=(V, Ã), åñëè (∀vi∈V)
Ãvi=V (êàæäàÿ ïàðà âåðøèí, ðàçëè÷íûõ èëè íåò, ñîåäèíÿåòñÿ äóãîé, ò. å.
ýòî ñèììåòðè÷åñêèé, ðåôëåêñèâíûé è òðàíçèòèâíûé ãðàô). Î÷åâèäíî,
÷òî êàæäîìó ãðàôó ìîæíî ñîïîñòàâèòü ïîëíûé ãðàô ñ ïåòëÿìè.
                        1.4.4. Ïåðåìåùåíèÿ â îðãðàôå
   Ïåðåìåùåíèÿ ïî äóãàì îðãðàôà îáóñëîâëåíû èõ îðèåíòàöèåé.
   Ïóòåì äëèíû n ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü (íå îáÿçàòåëüíî ðàç-
ëè÷íûõ) äóã (u1, u2, … , un) òàêèõ, ÷òî äëÿ ñîîòâåòñòâóþùåé ïîñëåäî-
âàòåëüíîñòè n+1 âåðøèí v0, v1, … , vn ñïðàâåäëèâî ui=(vi-1, vi) äëÿ
i=1, 2, … , n (ò. å. êîíåö ïðåäûäóùåé äóãè ñîâïàäàåò ñ íà÷àëîì ñëå-
äóþùåé). Ïóòü ìîæíî çàäàòü ïîñëåäîâàòåëüíîñòüþ äóã èëè âåðøèí,

28


÷åðåç êîòîðûå îí ïðîõîäèò. Íàïðè-                v!
ìåð, íà ðèñ.1.18 ïîñëåäîâàòåëüíîñòü                              u
äóã (u1, u5, u5, u3) îáðàçóåò ïóòü ñ ñî-                                 v
îòâåòñòâóþùåé ïîñëåäîâàòåëüíîñòüþ             u       u" u%
âåðøèí (v3, v2, v2, v2, v1).                              u!
                                                                           u#
   Ïóòü íàçûâàåòñÿ çàìêíóòûì, åñëè
                                                 v            u$       v"
v0=vn, è íåçàìêíóòûì, åñëè v0≠vn. Â
ïîñëåäíåì ñëó÷àå ãîâîðÿò, ÷òî ïóòü
                                                         Ðèñ.1.18. Îðãðàô
ñîåäèíÿåò v0 è vn èëè, òî÷íåå, ÷òî îí
èäåò èç v0 â vn.
   Ïðîñòûì ïóòåì íàçûâàåòñÿ ïóòü, â êîòîðîì íåò ïîâòîðÿþùèõñÿ äóã,
íàïðèìåð ïóòü (u1, u5, u3, u6) íà ðèñ.1.18. ñ ïîñëåäîâàòåëüíîñòüþ âåð-
øèí (v3, v2, v2, v1, v4).
   Ýëåìåíòàðíûì ïóòåì íàçûâàåòñÿ ïóòü, åñëè âñå åãî âåðøèíû ðàç-
ëè÷íû, íàïðèìåð ýëåìåíòàðíûé ïóòü (u1, u3, u6) ñ âåðøèíàìè (v3, v2, v1, v4)
íà ðèñ. 1.18.
   Êîíòóðîì íàçûâàåòñÿ çàìêíóòûé ïóòü, êîãäà v0=vn, íàïðèìåð êîíòóð
(u7, u2, u4, u2, u6) ñ âåðøèíàìè (v4, v3,v1, v3, v1, v4) íà ðèñ.1.18. Ïðîñòûì
êîíòóðîì íàçûâàåòñÿ êîíòóð, â êîòîðîì âñå äóãè ðàçëè÷íû, íàïðèìåð
êîíòóð (u1, u5, u3, u4) ñ âåðøèíàìè (v3, v2, v2, v1, v3). Ýëåìåíòàðíûì êîí-
òóðîì íàçûâàåòñÿ êîíòóð ñ ðàçëè÷íûìè âåðøèíàìè (êðîìå íà÷àëüíîé è
êîíå÷íîé, êîòîðûå ñîâïàäàþò), íàïðèìåð, êîíòóð (u1, u3, u4) ñ âåðøèíà-
ìè (v3, v2, v1, v3) íà ðèñ.1.18.
   Äëèíîé ïóòè µ = (u1, u2, … , un) íàçûâàþò ÷èñëî åãî äóã è îáîçíà÷à-
þò ÷åðåç L(µ), íàïðèìåð íà ðèñ.1.18
   µ=(u1, u5, u3,u6); L(µ)=4;
   µ=(u1, u3, u4); L(µ)=3.
   Äëÿ óäîáñòâà ââîäÿò ïîíÿòèå ïóòè íóëåâîé äëèíû (èçîëèðîâàííàÿ
âåðøèíà).
   Îðãðàô íàçûâàåòñÿ öèêëè÷åñêèì (êîíòóðíûì), åñëè îí ñîäåðæèò,
ïî êðàéíåé ìåðå, îäèí êîíòóð, è àöèêëè÷åñêèì (áåñêîíòóðíûì) â ïðî-
òèâíîì ñëó÷àå. Çàìåòèì, ÷òî ïåòëÿ ÿâëÿåòñÿ ñïåöèàëüíûì âèäîì êîí-
òóðà.
   Ãàìèëüòîíîâ ïóòü – ýòî ýëåìåíòàðíûé ïóòü, â êîòîðîì ÷èñëî äóã íà
åäèíèöó ìåíüøå ÷èñëà âåðøèí ãðàôà V. Èíà÷å ãîâîðÿ, òàêîé ïóòü
ïðîõîäèò ÷åðåç âñå âåðøèíû â òî÷íîñòè ïî îäíîìó ðàçó. Ïðè çàïèñè ñ
ïîìîùüþ âåðøèí ãàìèëüòîíîâ ïóòü – ýòî ïåðåñòàíîâêà âåðøèí ãðàôà.
Íàïðèìåð, â ãðàôå ðèñ 1.18 åñòü äâà ãàìèëüòîíîâûõ ïóòè:
                                                                          29


   1) ïóòü (u1, u3, u6) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v3,v2, v1, v4);
   2) ïóòü (u6, u7, u1) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v1, v4, v3,v2).
   Àíàëîãè÷íî ãàìèëüòîíîâ êîíòóð – ýòî êîíòóð, ïðîõîäÿùèé ÷åðåç
âñå âåðøèíû â òî÷íîñòè ïî îäíîìó ðàçó (èñêëþ÷àÿ ïðîèçâîëüíî âûá-
ðàííîå íà÷àëî). Íàïðèìåð, íà ðèñ.1.18 åñòü îäèí ãàìèëüòîíîâ êîíòóð
(u1, u3, u6, u7) ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí (v3, v2, v1, v4, v3); ïðè÷åì
ëþáàÿ âåðøèíà ìîæåò áûòü âûáðàíà â êà÷åñòâå íà÷àëüíîé öèêëè÷åñ-
êèì ñäâèãîì.
                           1.4.5. Îðèåíòèðîâàííûå äåðåâüÿ
  Îðèåíòèðîâàííûì äåðåâîì (åãî íàçûâàþò òàêæå ïðàäåðåâîì), ðàñ-
òóùèì èç êîðíÿ v0, íàçûâàåòñÿ ãðàô G=(V,U),åñëè:
   1) (∃!v0∈V) Ö1{v0}=∅ (ãäå ñèìâîëüíîå îáîçíà÷åíèå ∃! îçíà÷àåò –
“ñóùåñòâóåò îäíà è òîëüêî îäíà”), ò. å. ñóùåñòâóåò åäèíñòâåííàÿ âåð-
øèíà v0 (íàçûâàåìàÿ êîðíåì äåðåâà), â êîòîðóþ íå çàõîäèò íè îäíà
äóãà (íåò ïðåäøåñòâóþùèõ âåðøèí);
   2) (∀vi∈V)|Ö1{vi}| =1 (vi≠v0), ò. å. â êàæäóþ äðóãóþ âåðøèíó çàõî-
äèò òîëüêî îäíà äóãà (òîëüêî îäíà âåðøèíà ïðåäøåñòâóåò âåðøèíå vi);
   3) ãðàô íå ñîäåðæèò êîíòóðîâ.
   Âåðøèíà vi íàçûâàåòñÿ âèñÿ÷åé, åñëè Ãvi=∅, ò. å. èç vi íå èñõîäèò
äóãà (íåò ñëåäóþùåé âåðøèíû), åå òàêæå íàçûâàþò ëèñòîì.
   Íà ðèñ.1.19,à ïîêàçàíî ïðàäåðåâî ñ êîðíåì v0 è âèñÿ÷èìè âåðøèíà-
ìè v3, v4, v5, v6.
   Òàêèì îáðàçîì, ìîæíî ñêàçàòü, ÷òî ïðàäåðåâîì ÿâëÿåòñÿ ãðàô áåç
êîíòóðîâ è ïåòåëü, â êîòîðîì èç êîðíÿ äåðåâà â ëþáóþ äðóãóþ âåðøèíó
ìîæíî ïðèéòè òîëüêî ïî îäíîìó ýëåìåíòàðíîìó ïóòè.

 à              v              á        v               â           A            .        J

      v         v                    v           v
                                                                 B               D             K
                            v!                                               C       G H   I
                                 v!                    v$
                                                                                               L
 v"         v#        v$                   v" v#                     E

                           v%     v&    v'   v
                    Ðèñ. 1.19. Îðèåíòèðîâàííûå äåðåâüÿ :
           à – ïðàäåðåâî; á – äâîè÷íîå äåðåâî; ⠖ âåòâÿùèéñÿ ãðàô
30



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