dm3 (Лекция), страница 7

Äèàãðàìîé íà ïëîñêîñòè (ãðàôè÷åñêèì èçîáðàæåíèåì).Âåðøèíàì ñîîòâåòñòâóþò òî÷êè íà ïëîñêîñòè, èõ ðàñïîëîæåíèå íå èìååò çíà÷åíèÿ. Ðåáðà ãðàôà èçîáðàæàþòñÿ îòðåçêàìè èëè äóãàìè êðèâûõ, ñîåäèíÿþùèìèïàðû òî÷åê.Ãðàôû èç ïðèìåðîâ 1 è 2 ìîæíî çàäàòü ñëåäóþùèìè èçîáðàæåíèÿìè.v1e1rr v2Ar v5e2e3 e4e5v7rv3 rr v4r v6CeeBCCCSCS C C S C S CS C CCC SCSC CC SS CC S CC SCC SCr ErD Cr3. Ìàòðèöàìè èç íóëåé è åäèíèö.A(G) ãðàôà G = ({v1 , . . .

, vn }, {e1 , . . . , em }) êâàäðàòíàÿ ïîðÿäêà n, îíà óñòðîåíà ñëåäóþùèì îáðàçîì: A(G) = (aij )n × n , ãäåÌàòðèöà ñìåæíîñòèaij =1,0,åñëè âåðøèíû vi è vj ñìåæíû,â ïðîòèâíîì ñëó÷àå.35Ìàòðèöà A(G) ñèììåòðè÷íà, åå äèàãîíàëüíûå ýëåìåíòû ðàâíû 0, ÷èñëî åäèíèöâ ñòðîêå i (êàê è ÷èñëî åäèíèö â ñòîëáöå i) ðàâíî d(vi ), îáùåå ÷èñëî åäèíèö âìàòðèöå ðàâíî 2m.B(G) ãðàôà G èìååò ðàçìåð m × n, B(G) = (bij )m × n ,ãäå1, åñëè ðåáðî ei è âåðøèíà vj èíöèäåíòíû,bij =0, â ïðîòèâíîì ñëó÷àå.Ìàòðèöà èíöèäåíöèéÊàæäàÿ ñòðîêà ìàòðèöû B(G) ñîäåðæèò ðîâíî äâå åäèíèöû, ÷èñëî åäèíèö âñòîëáöå j ðàâíî d(vj ).Ìàòðèöû è ñïèñêè ïðèìåíÿþòñÿ ïðè ðåøåíèè çàäà÷ î ãðàôàõ íà êîìïüþòåðå.Ïðè "ðó÷íîì" ðåøåíèè çàäà÷ íà íåáîëüøèõ ãðàôàõ ïðèâû÷íåå äèàãðàììû, îíèîáëàäàþò íàãëÿäíîñòüþ è ëàêîíè÷íîñòüþ. Êàæäûé èç ñïîñîáîâ ïîëíîñòüþ îïðåäåëÿåò ãðàô è ëåãêî ïðåîáðàçóåòñÿ â äðóãîé ñïîñîá ïðåäñòàâëåíèÿ ýòîãî æå ãðàôà.Ìû ÷àñòî áóäåì èñïîëüçîâàòü ìàòðèöû è ñïèñêè, ÷òîáû íå ðèñîâàòü äèàãðàììû.Äëÿ ãðàôà èç ïðèìåðà 1 ïîëó÷àåìA(G) = 0110000101100011000000100000000001000001000000000 .

B(G) = 01000101101110000010000010000100000.Ìåòîäàìè êîìáèíàòîðíûõ âû÷èñëåíèé íåòðóäíî ïîëó÷èòü×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn, ðàâíî. ×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn è ðîâíî mmðåáåð, ñîñòàâëÿåò Cn(n.− 1)/2Ââåäåì åùå íåñêîëüêî âàæíåéøèõ ïîíÿòèé. Ìàðøðóò, ñîåäèíÿþùèé âåðøèíûvi è vj ãðàôà, ýòî ÷åðåäóþùàÿñÿ ïîñëåäîâàòåëüíîñòü èíöèäåíòíûõ äðóã äðóãóÑëåäñòâèå 2.2n(n − 1)/2âåðøèí è ðåáåð, êðàéíèìè ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ vi è vj . Åñëè vi = vj , òîìàðøðóò íàçûâàåòñÿ.

×èñëî ðåáåð â ìàðøðóòå íàçûâàåòñÿ åãî. ãðàôå èç ïðèìåðà 1 ïîñëåäîâàòåëüíîñòü v1 e1 v2 e4 v4 e4 v2 e3 v3 îáðàçóåò ìàðøðóò äëèíû 4, ïîñëåäîâàòåëüíîñòü v1 e1 v2 e3 v3 e2 v1 öèêë äëèíû 3.Ãðàô íàçûâàåòñÿ, åñëè ëþáûå äâå åãî âåðøèíû ìîæíî ñîåäèíèòü íåêîòîðûì ìàðøðóòîì. Ãðàô G1 (V1 , E1 ) íàçûâàåòñÿG(V, E), åñëèöèêëîìäëèíîéñâÿçíûìïîäãðàôîì ãðàôà36ìíîæåñòâà åãî âåðøèí è ðåáåð îáðàçóþò ïîäìíîæåñòâà V1 ⊆ V , E1 ⊆ E . Ìàêñèìàëüíûé ñâÿçíûé ïîäãðàô ãðàôà íàçûâàåòñÿ åãî.

Ñâÿçíûé ãðàô èìååò ðîâíî îäíó êîìïîíåíòó ñâÿçíîñòè. Åñëè èìååòñÿ íå ìåíåå äâóõêîìïîíåíò, ãðàô íåñâÿçåí. Åñëè ãðàô G èìååò n âåðøèí è k ≥ 2 êîìïîíåíò, ñîäåðæàùèõ n1 , . . . nk âåðøèí, n1 + · · · + nk = n, òî åãî ìàòðèöà ñìåæíîñòè ðàçáèâàåòñÿíà áëîêè ïîäìàòðèöû ïîðÿäêîâ n1 , . . . , nk , îêðóæåííûå ëèøü íóëåâûìè ýëåìåíòàìè. (Ýòî õîðîøî âèäíî â ìàòðèöå äëÿ ãðàôà èç ïðèìåðà 1, â äðóãèõ ñëó÷àÿõ äëÿáîëüøåé íàãëÿäíîñòè óäîáíî ïðîâåñòè ïåðåñòàíîâêó ñòðîê (è ñòîëáöîâ) ìàòðèöûA(G).) Ãðàô èç ïðèìåðà 1 íåñâÿçåí, îí èìååò òðè êîìïîíåíòûêîìïîíåíòîé ñâÿçíîñòèG1 = ({v1 , v2 , v3 , v4 }, {e1 , e2 , e3 , e4 }),ãðàô èçïðèìåðà 2G2 = ({v5 , v6 }, {e5 }),G3 = ({v7 }, ∅);ñâÿçåí.Ýéëåðîâûì5Íåêîòîðûå öèêëû îñîáåííî âàæíû.íàçûâàåòñÿ öèêë, ïðîõîäÿùèé÷åðåç êàæäîå ðåáðî ãðàôà ðîâíî îäèí ðàç. Åñëè, íàïðèìåð, âåðøèíû ãðàôà ñîîòâåòñâóþò ïóíêòàì íà ìåñòíîñòè, à ðåáðà äîðîãàì, ñîåäèíÿþùèì ýòè ïóíêòû,òî ýéëåðîâ öèêë äàåò âîçìîæíîñòü îêàçàòüñÿ íà êàæäîé äîðîãå (÷òîáû âûïîëíèòü êàêîå-ëèáî äåéñòâèå íà íåé, íàïðèìåð, óñòàíîâèòü çíàê) ðîâíî îäèí ðàç èâåðíóòüñÿ â ìåñòî ñòàðòà.

 òàêîé ïîñòàíîâêå ýòà çàäà÷à è ïîÿâèëàñü âïåðâûå, â1752 ã., êàê çàäà÷à î êåíèãñáåðãñêèõ ìîñòàõ. Ðîëü âåðøèí ãðàôà èãðàëè ó÷àñòêèñóøè áåðåãà è îñòðîâà ïðîòåêàþùåé â ã. Êåíèãñáåðãå (íûíå Êàëèíèíãðàä) ðåêèÏðåãîëü, ðåáåð ìîñòû. Ëåîíàðä Ýéëåð, ðàáîòàâøèé â òî âðåìÿ â ÏåòåðáóðãñêîéÀêàäåìèè íàóê, äàë èñ÷åðïûâàþùåå ðåøåíèå çàäà÷è. Èì äîêàçàíàÒåîðåìà 2.Ýéëåðîâ öèêë â ãðàôå ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäàâûïîëíåíû äâà óñëîâèÿ:1) ãðàô ñâÿçåí,2) ñòåïåíü êàæäîé âåðøèíû ÷åòíà.Ýòîò ôàêò èíîãäà íàçûâàþò èñòîðè÷åñêè ïåðâîé òåîðåìîé òåîðèè ãðàôîâ, õîòÿË. Ýéëåð è åãî ñîâðåìåííèêè òàêîãî ïîíÿòèÿ íå çíàëè è íå ââîäèëè. ïðèìåðe 1 ýéëåðîâà öèêëà íåò, òàê êàê ãðàô G íå ÿâëÿåòñÿ ñâÿçíûì. Ýéëåðîâà öèêëà íåò è â êîìïîíåíòå ñâÿçíîñòè G1 ýòîãî ãðàôà, òàê êàê âåðøèíûv2 , v4 , v5 , v6 èìåþò íå÷åòíûå ñòåïåíè.5 ËåîíàðäÐîññèèÝéëåð (17071783) ìàòåìàòèê, ôèçèê è àñòðîíîì, ðîäèëñÿ â Øâåéöàðèè, ðàáîòàë â Ãåðìàíèè è37Ïðèìåð 3.Ïóñòü ãðàô çàäàí ìàòðèöåé ñìåæíîñòèA(G) = 010100101101010001110011000101011110.Ìàòðèöà A(G) íå ðàçáèâàåòñÿ íà áëîêè, ïîýòîìó ãðàô ñâÿçåí.

×èñëî åäèíèö âêàæäîé ñòðîêå ÷åòíî, ò. å ñòåïåíü êàæäîé âåðøèíû ÷åòíà. Ïî òåîðåìå 2 ñóùåñòâóåò ýéëåðîâ öèêë. Óêàæåì ðåáðà â ïîðÿäêå èõ ïðîõîæäåíèÿ ýéëåðîâûì öèêëîì:e1 = {v1 , v2 }, e2 = {v2 , v3 }, e3 = {v3 , v6 }, e4 = {v6 , v2 }, e5 = {v2 , v4 },e6 = {v4 , v6 }, e7 = {v6 , v5 }, e8 = {v5 , v4 }, e9 = {v4 , v1 }.Ãàìèëüòîíîâûì6 íàçûâàåòñÿ öèêë, ïðîõîäÿùèé ðîâíî îäèí ðàç ÷åðåç êàæäóþâåðøèíó ãðàôà.

Çàäà÷à î ñóùåñòâîâàíèè ãàìèëüòîíîâà öèêëà, èçâåñòíà ñ XIX â.è, â îòëè÷èå îò çàäà÷è îá ýéëåðîâîì öèêëå, íå ðåøåíà äî ñèõ ïîð.  ãðàôå èç ïðèìåðà 3 åñòü ãàìèëüòîíîâ öèêë (v1 , v2 , v3 , v6 , v5 , v4 , v1 ) (óêàçàíû òîëüêî âåðøèíû),â ïðèìåðå 1 îí îòñóòñòâóåò â ñèëó íåñâÿçíîñòè ãðàôà. Ðàññìîòðèì ïðèìåð 2.Öèêë, ñîäåðæàùèé âåðøèíû A è B , ïðèâîäèò âíîâü â îäíó èç ýòèõ âåðøèí, òàêêàê êàæäàÿ èç âåðøèí C, D, E ñìåæíà òîëüêî ñ A è B . Òàêèì îáðàçîì, ãàìèëüòîíîâ öèêë â ýòîì ãðàôå îòñóòñòâóåò.Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ èñïîëüçóþòñÿ ãðàôû, íàçûâàåìûå äåðåâüÿìè.Äåðåâî ýòî ñâÿçíûé ãðàô áåç öèêëîâ.Äåðåâüÿìè óäîáíî ïðåäñòàâëÿòü èåðàðõè÷åñêèå ñòðóêòóðû, ò.

å. ìíîæåñòâà îáúåêòîâ, èç êîðûõ îäíè íàõîäÿòñÿ â ïîä÷èíåíèè îòíîñèòåëüíî äðóãèõ. Âñåì èçâåñòíû ãåíåàëîãè÷åñêèå äåðåâüÿ, îïèñûâàþùèåðîäîñëîâíûå ñåìåé â èñòîðèè, ïðîèñõîæäåíèå îðãàíèçìîâ è âèäîâ â áèîëîãèè,ñòðóêòóðû äàííûõ â èíôîðìàòèêå è ìíîãîå äðóãîå.

Âîò îäèí èç ïðèìåðîâ äåðåâà.6 Óèëüÿì Ãàìèëüòîí (18051865) èðëàíäñêèé ìàòåìàòèê. Çàäà÷ó î òàêîì öèêëå â ãðàôå ñ 20 âåðøèíàìè îíèñïîëüçîâàë â 1859 ã. êàê îñíîâó äëÿ èãðóøêè-ãîëîâîëîìêè, ïîëó÷èâ ïàòåíò è íàëàäèâ (õîòÿ è áåç êîììåð÷åñêîãîóñïåõà) åå ïðîèçâîäñòâî.38Ïðèìåð 4.ev5@@@ev6ev7@uv3ruv4@@@@@uv2@@@@@@@@@ev1Äåðåâî îáëàäàåò çàìå÷àòåëüíûìè ñâîéñòâàìè.

Óêàæåì íåêîòîðûå èç íèõ.Òåîðåìà 3.GnmÅñëè äåðåâî, èìåþùåe âåðøèí è ðåáåð, òî1) m = n − 1;2) ëþáûå äâå ðàçëè÷íûå âåðøèíû ñîåäèíåíû åäèíñòâåííûì ìàðøðóòîì áåçïîâòîðåíèé âõîäÿùèõ â íåãî âåðøèí è ðåáåð;3) ïðè óäàëåíèå ëþáîãî ðåáðà îáðàçóåòñÿ ðîâíî äâå êîìïîíåíòû ñâÿçíîñòè:4) ïðè äîáàâëåíèè ðåáðà, ñîåäèíÿþùåãî ëþáûå äâå íå ñìåæíûå ïðåæäå âåðøèíû, îáðàçóåòñÿ ðîâíî îäèí öèêë.Ýòè ñâîéñòâà ëåãêî âèäåòü íà äèàãðàììå èç ïðèìåðà 4.ñ âåðøèíàìè v1 , .

. . , vn íàçûâàåòñÿ íàáîð íàòóðàëüíûõ ÷èñåë c1 , . . . cn , ïðèïèñàííûõ âåðøèíàì òàê, ÷òî ëþáûå äâå ñìåæíûå âåðøèíûvi è vj èìåþò ðàçëè÷íûå öâåòà ci 6= cj . Ìèíèìàëüíîå ÷èñëî öâåòîâ, äîñòàòî÷íîåäëÿ ðàñêðàñêè ãðàôà G, íàçûâàåòñÿ åãîχ(G).Ãðàô íàçûâàåòñÿ, åñëè îí ñîäåðæèò n âåðøèí è âñå n(n − 1)/2 ðåáåð, ñîåäèíÿþùèõ âñå ïàðû âåðøèí. Êàæäûé âíåäèàãîíàëüíûé ýëåìåíò ìàòðèöûñìåæíîñòè ïîëíîãî ãðàôà ðàâåí 1. Ïîëíûé ãðàô, èìåþùèé n âåðøèí, îáîçíà÷àåòñÿ Kn .Òåîðåìà 4 (ñâîéñòâà õðîìàòè÷åñêîãî ÷èñëà).1.Gnχ(G) ≤ nÐàñêðàñêîé ãðàôàöâåòîâïîëíûìõðîìàòè÷åñêèì ÷èñëîìÅñëè ãðàô ñîäåðæèò ðîâíî âåðøèí, òî.2.

Åñëè ãðàô G ñîäåðæèò ïîäãðàô G1 , òî χ(G) ≥ χ(G1 ).3. χ(Kp ) = p.4. Åñëè ãðàô G ñîäåðæèò ïîäãðàô Kp , òî χ(G) ≥ p.5. Åñëè n ≥ 3 è ãðàô Cn ïðåäñòàâëÿåò ñîáîé n-óãîëüíèê (öèêë èç n âåðøèí è39nðåáåð, ïðè ýòîì C3 = K3), òîåñëè n ÷åòíî,åñëè n íå÷åòíî.6. Åñëè ãðàô G äåðåâî, òî χ(G) = 2.7. Åñëè ãðàô G ïëàíàðíûé, ò. å. ìîæåò áûòü èçîáðàæåí äèàãðàììîé íàïëîñêîñòè, â êîòîðîé ðåáðà ïåðåñåêàþòñÿ òîëüêî â âåðøèíàõ, òî χ(G) ≤ 4(òåîðåìà î 4 êðàñêàõ).χ(Cn ) =2,3,Ïðîñòåéøèìè íåïëàíàðíûìè ãðàôàìè ÿâëÿþòñÿ K5 è K3,3 .K5uB@@ B @ B@B@B@B@B@Bu@uBb""Bbb"BBb"Bb B "b"Bb"Bb"BBb "bB"B" bB B b"b B B ""bbBuB"uue@A@AA@A @A @K3,3A @@A@A@A @A@A @euA@A@@ A@ A@AA @@A@A@ A@ A@Au@Ae ñèëó ñâîéñòâà 3 èìååì χ(K5 ) = 5.

À äëÿ âòîðîãî ãðàôà, êàê íåòðóäíî ïðîâåðèòü, χ(K3,3 ) = 2. ïðèìåðå 1 ãðàô G cîäåðæèò òðåóãîëüíèê, ïîýòîìó χ(G) ≥ 3. Ñ äðóãîéñòîðîíû, ìîæíî ïîñòðîèòü ðàñêðàñêó â 3 öâåòà, íàïðèìåð,c(v3 ) = c(v4 ) = c(v6 ) = c(v7 ) = 1, c(v1 ) = c(v5 ) = 2, c(v2 )3,ïîýòîìó χ(G) ≤ 3. Òàêèì îáðàçîì, χ(G) = 3.Ãðàôû èç ïðèìåðîâ 2 è 3 èìåþò õðîìàòè÷åñêèå ÷èñëà 2 è 3 ñîîòâåòñòâåííî. Äåðåâî èç ïðèìåðà 4 èìååò â ñèëó ñâîéñòâà 6 õðîìàòè÷åñêîå ÷èñëî 2, íàäèàãðàììå ïðåäñòàâëåíà åãî ðàñêðàñêà â 2 öâåòà (òåìíûå è ñâåòëûå êðóæêè).40Çàäàíèå äëÿ ñâìîñòîÿòåëüíîãî ðåøåíèÿÏîñòðîéòå ìàòðèöû ñìåæíîñòè è èíöèäåíöèé ãðàôà.Ïîñòðîéòå ýéëåðîâ è ãàìèëüòîíîâ öèêëû èëè äîêàæèòå, ÷òî ñîîòâåòñòâóþùèé öèêë íå ñóùåñòâóåò.Íàéäèòå õðîìàòè÷åñêîå ÷èñëî è îïòèìàëüíóþ ðàñêðàñêó âåðøèíãðàôà.Âñå ãðàôû èìåþò ìíîæåñòâî âåðøèí{1, 2, 3, 4, 5, 6}.Ðåáðà îïðåäåëÿ-þòñÿ â âàðèàíòå çàäàíèÿ. Äëÿ êðàòêîñòè îíè óêàçûâàþòñÿ áåç ñêîáîêè çàïÿòûõ.1.