Основные понятия теории графов

7 Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâ Âàæíûì èíñòðóìåíòîì äèñêðåòíîé ìàòåìàòèêè ÿâëÿþòñÿ ãðàôû. Ãðàôîì íàçûâàåòñÿ ïàðà ìíîæåñòâ G = (V, E), V = {v1, . . . , vn}, E = {e1, . . . , em}. Ýëåìåíòû vi ìíîæåñòâà V íàçûâàþòñÿ âåðøèíàìè ãðàôà G, ýëåìåíòû ej ìíîæåñòâà E  ðåáðàìè, ýòî ïàðû ej = {vj1 , vj2 } ðàçëè÷íûõ âåðøèí. Åñëè âåðøèíû vj1 , vj2 îáðàçóþò ðåáðî ej , îíè íàçûâàþòñÿ ñìåæíûìè, ïðè ýòîì âåðøèíà vj1 è ðåáðî ej íàçûâàþòñÿ èíöèäåíòíûìè äðóã äðóãó, ýòî æå ñïðàâåäëèâî è äëÿ âåðøèíû vj2 è òîãî æå ðåáðà ej . ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå vi, íàçûâàåòñÿ ñòåïåíüþ ýòîé âåðøèíû è îáîçíà÷àåòñÿ d(vi). V E ( n m). Ïðèìåð 1. Ðàññìîòðèì ãðàô G ñî ñëåäóþùèìè âåðøèíàìè è ðåáðàìè: V = {v1 , . . . , v7 }, E = {e1 , e2 , e3 , e4 , e5 }, e1 = {v1 , v2 }, e2 = {v1 , v3 }, e3 = {v2 , v3 }, e4 = {v2 , v4 }, e5 = {v5 , v6 }. Òîãäà n = 7, m = 5, G íåîðèåíòèðîâàííûé è èìååò ñëåäóþùèå ñòåïåíè âåðøèí: i 1 2 3 4 5 6 7 d(vi ) 2 3 2 1 1 1 0 Åñëè ñëîæèòü ñòåïåíè, òî ïîëó÷èì 2 + 3 + 2 + 1 + 1 + 1 + 0 = 2 · 5. Òåîðåìà 1. Ñóììà ñòåïåíåé âñåõ âåðøèí ãðàôà ðàâíà óäâîåííîìó ÷èñëó ðåáåð: n X d(vi ) = 2m. (1) i=1 . Ïóñòü d(vi, vj )  ýòî ÷èñëî ðåáåð, ñîåäèíÿþùèõ âåðøèíû vi è vj . Òîãäà d(vi , vj ) = d(vj , vi ) ∈ {0, 1}, Äîêàçàòåëüñòâî n X i=1 d(vi ) = n X n X d(vi , vj ) = i=1 j=1 n n X X d(vi , vj ), j=1 i=1 è â ëåâîé ÷àñòè ðàâåíñòâà (1) êàæäîå ðåáðî ó÷òåíî ðîâíî äâàæäû: â ñëàãàåìûõ d(vi ) è d(vj ).  Ñëåäñòâèå 1. ×èñëî âåðøèí íå÷åòíîé ñòåïåíè â ãðàôå ÷åòíî.  ïðèìåðå 1 ÷åòûðå âåðøèíû íå÷åòíîé ñòåïåíè v2, v4, v5, v6. Âåðøèíà v7 èìååò ÷åòíóþ ñòåïåíü 0, òàêàÿ âåðøèíà íàçûâàåòñÿ èçîëèðîâàííîé. Ïðèâåäåì ïðèìåð, â êîòîðîì ãðàôû è ñòåïåíè âåðøèí ïðèìåíÿþòñÿ äëÿ ðåøåíèÿ ëîãè÷åñêîé çàäà÷è. Ïðèìåð 2. Ó÷åíèêè îäíîãî êëàññà ïðîâîäèëè íà óðîêå ìàòåìàòèêè êðóãîâîé òóðíèð ïî èãðå â "êðåñòèêè-íîëèêè". Ó÷àñòíèêîâ áûëî ïÿòåðî. Êîãäà ïðîçâåíåë 1 çâîíîê ñ óðîêà, òóðíèð ïðåðâàëè, â ýòîò ìîìåíò îêàçàëîñü ñûãðàíî 6 ïàðòèé. Áîëüøå âñåãî èãð, ïî òðè, ïðîâåëè òîëüêî Àëåíà è Âàñÿ. Ñêîëüêî èãð ïðîâåëè îñòàëüíûå ó÷àñòíèêè? Êòî ñ êåì èãðàë? Îïèøåì òóðíèð ãðàôîì ñ 5 âåðøèíàìè, ñîîòâåòñòâóþùèìè ó÷àñòíèêàì. Ñîåäèíèì ïàðó âåðøèí ðåáðîì, åñëè ñîîòâåòñòâóþùèå ó÷àñòíèêè ñûãðàëè äðóã ñ äðóãîì. Íàçîâåì ó÷àñòíèêîâ À (Àëåíà),  (Âàñÿ), Ñ(Ñàøà), D (Äàøà) è Å (Åãîð), òàê æå îáîçíà÷èì è âåðøèíû. Òîãäà ÷èñëî ïàðòèé, ñûãðàííûì êàæäûì ó÷àñòíèêîì X , åñòü ñòåïåíü d(X) âåðøèíû X . B ñèëó òåîðåìû 1 èìååì d(A) + d(B) + d(C) + d(D) + d(E) = 2 · 6, d(A) = d(B) = 3. Íå îãðàíè÷èâàÿ îáùíîñòè, ïîëàãàåì d(C) ≥ d(D) ≥ d(E). Òîãäà d(C) < 3 è d(C), d(D), d(E) ∈ {0, 1, 2}, (2) d(C) + d(D) + d(E) = 6. (3) Åñëè d(E) = 0, òî d(C) + d(D) = 6 è óñëîâèÿ (2) è (3) íå ìîãóò âûïîëíÿòüñÿ îäíîâðåìåííî. Åñëè d(E) = 1, òî d(C) + d(D) = 5 è óñëîâèÿ (2) è (3) òàêæå íå âûïîëíÿþòñÿ îäíîâðåìåííî. Îñòàåòñÿ åäèíñòâåííàÿ âîçìîæíîñòü d(E) = 2. Ïðè ýòîì è d(C) = d(D) = 2. Íåîáõîäèìî ïðîâåðèòü, ÷òî òàêàÿ âîçìîæíîñòü äåéñòâèòåëüíî ðåàëèçóåòñÿ, ò. å. ïîñòðîèòü ãðàô òóðíèðà. Ýòî ìîæíî ñäåëàòü, íàïðèìåð,òàê (ðåáðà ñîîòâåòñòâóþò ïàðàì èãðàâøèõ äðóã ñ äðóãîì ó÷àñòíèêîâ): ðåáðà A è C , A è D, A è E , B è C , B è D, B è E . Ðàññìîòðèì ñïîñîáû çàäàíèÿ ãðàôîâ. 1. Óêàçàíèåì ñïèñêîâ âåðøèí è ðåáåð. Ýòèì ñïîñîáîì áûëè çàäàíû ãðàôû â ïðèâåäåííûõ ïðèìåðàõ. 2. Äèàãðàìîé íà ïëîñêîñòè (ãðàôè÷åñêèì èçîáðàæåíèåì). Âåðøèíàì ñîîòâåòñòâóþò òî÷êè íà ïëîñêîñòè, èõ ðàñïîëîæåíèå íå èìååò çíà÷åíèÿ. Ðåáðà ãðàôà èçîáðàæàþòñÿ îòðåçêàìè èëè äóãàìè êðèâûõ, ñîåäèíÿþùèìè ïàðû òî÷åê. Ãðàôû èç ïðèìåðîâ 1 è 2 ìîæíî çàäàòü ñëåäóþùèìè èçîáðàæåíèÿìè. v1 e1 r r v2 r v5 A


e2 e3



e4 e5 v7 r



v3
r r v4 C r v6 2 e eB CS CC CS  C S   C  C S   C  C  C S   C S C   C C S   S  C C    C S C S C   C   C  SC r  D Cr SCr E 3. Ìàòðèöàìè èç íóëåé è åäèíèö. Ìàòðèöà ñìåæíîñòè A(G) ãðàôà G = ({v1, . . . , vn}, {e1, . . . , em})  êâàäðàòíàÿ ïîðÿäêà n, îíà óñòðîåíà ñëåäóþùèì îáðàçîì: A(G) = (aij )n × n, ãäå  1, åñëè âåðøèíû vi è vj ñìåæíû, aij = 0, â ïðîòèâíîì ñëó÷àå. Ìàòðèöà 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) =      1 1 1 1 1 1 1 1 1 1           . B(G) =        1 1 1 1 1 1 1 1 1 1    .   Ìåòîäàìè êîìáèíàòîðíûõ âû÷èñëåíèé íåòðóäíî ïîëó÷èòü . ×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn, ðàâíî Ñëåäñòâèå 2 . ×èñëî ðàçëè÷íûõ ãðàôîâ, èìåþùèõ âåðøèíû v1, . . . , vn è ðîâíî m m ðåáåð, ñîñòàâëÿåò Cn(n . − 1)/2 Ââåäåì åùå íåñêîëüêî âàæíåéøèõ ïîíÿòèé. Ìàðøðóò, ñîåäèíÿþùèé âåðøèíû vi è vj ãðàôà,  ýòî ÷åðåäóþùàÿñÿ ïîñëåäîâàòåëüíîñòü èíöèäåíòíûõ äðóã äðóãó 2n(n − 1)/2 3 âåðøèí è ðåáåð, êðàéíèìè ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿ vi è vj . Åñëè vi = vj , òî ìàðøðóò íàçûâàåòñÿ öèêëîì. ×èñëî ðåáåð â ìàðøðóòå íàçûâàåòñÿ åãî äëèíîé.  ãðàôå èç ïðèìåðà 1 ïîñëåäîâàòåëüíîñòü v1e1v2e4v4e4v2e3v3 îáðàçóåò ìàðøðóò äëèíû 4, ïîñëåäîâàòåëüíîñòü v1e1v2e3v3e2v1  öèêë äëèíû 3. Ãðàô íàçûâàåòñÿ ñâÿçíûì, åñëè ëþáûå äâå åãî âåðøèíû ìîæíî ñîåäèíèòü íåêîòîðûì ìàðøðóòîì. Ãðàô G1(V1, E1) íàçûâàåòñÿ ïîäãðàôîì ãðàôà G(V, E), åñëè ìíîæåñòâà åãî âåðøèí è ðåáåð îáðàçóþò ïîäìíîæåñòâà 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 }), G2 = ({v5 , v6 }, {e5 }), G3 = ({v7 }, ∅); ãðàô èç ïðèìåðà 2 ñâÿçåí. Íåêîòîðûå öèêëû îñîáåííî âàæíû. Ýéëåðîâûì1 íàçûâàåòñÿ öèêë, ïðîõîäÿùèé ÷åðåç êàæäîå ðåáðî ãðàôà ðîâíî îäèí ðàç. Åñëè, íàïðèìåð, âåðøèíû ãðàôà ñîîòâåòñâóþò ïóíêòàì íà ìåñòíîñòè, à ðåáðà  äîðîãàì, ñîåäèíÿþùèì ýòè ïóíêòû, òî ýéëåðîâ öèêë äàåò âîçìîæíîñòü îêàçàòüñÿ íà êàæäîé äîðîãå (÷òîáû âûïîëíèòü êàêîå-ëèáî äåéñòâèå íà íåé, íàïðèìåð, óñòàíîâèòü çíàê) ðîâíî îäèí ðàç è âåðíóòüñÿ â ìåñòî ñòàðòà.  òàêîé ïîñòàíîâêå ýòà çàäà÷à è ïîÿâèëàñü âïåðâûå, â 1752 ã., êàê çàäà÷à î êåíèãñáåðãñêèõ ìîñòàõ. Ðîëü âåðøèí ãðàôà èãðàëè ó÷àñòêè ñóøè  áåðåãà è îñòðîâà ïðîòåêàþùåé â ã. Êåíèãñáåðãå (íûíå Êàëèíèíãðàä) ðåêè Ïðåãîëü, ðåáåð  ìîñòû. Ëåîíàðä Ýéëåð, ðàáîòàâøèé â òî âðåìÿ â Ïåòåðáóðãñêîé Àêàäåìèè íàóê, äàë èñ÷åðïûâàþùåå ðåøåíèå çàäà÷è. Èì äîêàçàíà Òåîðåìà 2. Ýéëåðîâ öèêë â ãðàôå ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäà âûïîëíåíû äâà óñëîâèÿ: 1) ãðàô ñâÿçåí, 2) ñòåïåíü êàæäîé âåðøèíû ÷åòíà. Ýòîò ôàêò íàçûâàþò èñòîðè÷åñêè ïåðâîé òåîðåìîé òåîðèè ãðàôîâ, õîòÿ Ë. Ýéëåð è åãî ñîâðåìåííèêè òàêîãî ïîíÿòèÿ íå çíàëè è íå ââîäèëè.  ïðèìåðe 1 ýéëåðîâà öèêëà íåò, òàê êàê ãðàô G íå ÿâëÿåòñÿ ñâÿçíûì. Ýéëåðîâà öèêëà íåò è â êîìïîíåíòå ñâÿçíîñòè G1 ýòîãî ãðàôà, òàê êàê âåðøèíû v2 , v4 , v5 , v6 èìåþò íå÷åòíûå ñòåïåíè. 1 Ëåîíàðä Ýéëåð (17071783)  ìàòåìàòèê, ôèçèê è àñòðîíîì, ðîäèëñÿ â Øâåéöàðèè, ðàáîòàë â Ãåðìàíèè è Ðîññèè 4 . Ïóñòü ãðàô çàäàí ìàòðèöåé ñìåæíîñòè Ïðèìåð 3     A(G) =     1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1     .    Ìàòðèöà 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 }. Ãàìèëüòîíîâûì2 íàçûâàåòñÿ öèêë, ïðîõîäÿùèé ðîâíî îäèí ðàç ÷åðåç êàæäóþ âåðøèíó ãðàôà. Çàäà÷à î ñóùåñòâîâàíèè ãàìèëüòîíîâà öèêëà, èçâåñòíà ñ XIX â. è, â îòëè÷èå îò çàäà÷è îá ýéëåðîâîì öèêëå, íå ðåøåíà äî ñèõ ïîð.  ãðàôå èç ïðèìåðà 3 åñòü ãàìèëüòîíîâ öèêë (v1 , v2 , v3 , v6 , v5 , v4 , v1 ) (óêàçàíû òîëüêî âåðøèíû), â ïðèìåðå 1 îí îòñóòñòâóåò â ñèëó íåñâÿçíîñòè ãðàôà. Ðàññìîòðèì ïðèìåð 2. Öèêë, ñîäåðæàùèé âåðøèíû A è B , ïðèâîäèò âíîâü â îäíó èç ýòèõ âåðøèí, òàê êàê êàæäàÿ èç âåðøèí C, D, E ñìåæíà òîëüêî ñ A è B . Òàêèì îáðàçîì, ãàìèëüòîíîâ öèêë â ýòîì ãðàôå îòñóòñòâóåò. Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ èñïîëüçóþòñÿ ãðàôû, íàçûâàåìûå äåðåâüÿìè. Äåðåâî  ýòî ñâÿçíûé ãðàô áåç öèêëîâ.Äåðåâüÿìè óäîáíî ïðåäñòàâëÿòü èåðàðõè÷åñêèå ñòðóêòóðû, ò. å. ìíîæåñòâà îáúåêòîâ, èç êîðûõ îäíè íàõîäÿòñÿ â ïîä÷èíåíèè îòíîñèòåëüíî äðóãèõ. Âñåì èçâåñòíû ãåíåàëîãè÷åñêèå äåðåâüÿ, îïèñûâàþùèå ðîäîñëîâíûå ñåìåé â èñòîðèè, ïðîèñõîæäåíèå îðãàíèçìîâ è âèäîâ â áèîëîãèè, ñòðóêòóðû äàííûõ â èíôîðìàòèêå è ìíîãîå äðóãîå. Âîò îäèí èç ïðèìåðîâ äåðåâà. 2 Óèëüÿì Ãàìèëüòîí (18051865)  èðëàíäñêèé ìàòåìàòèê. Çàäà÷ó î òàêîì öèêëå â ãðàôå ñ 20 âåðøèíàìè îí èñïîëüçîâàë â 1859 ã. êàê îñíîâó äëÿ èãðóøêè-ãîëîâîëîìêè, ïîëó÷èâ ïàòåíò è íàëàäèâ (õîòÿ è áåç êîììåð÷åñêîãî óñïåõà) åå ïðîèçâîäñòâî. 5 . Ïðèìåð 4 ev5 @ @ @ ev6 ev7 @uv3 ruv4 @ @ @ @ @ uv2 @ @ @ @ @ @ @ @ @e v1 Äåðåâî îáëàäàåò çàìå÷àòåëüíûìè ñâîéñòâàìè. Óêàæåì íåêîòîðûå èç íèõ. Òåîðåìà 3. Åñëè G  äåðåâî, èìåþùåe n âåðøèí è m ðåáåð, òî ; ëþáûå äâå ðàçëè÷íûå âåðøèíû ñîåäèíåíû åäèíñòâåííûì ìàðøðóòîì áåç ïîâòîðåíèé âõîäÿùèõ â íåãî âåðøèí è ðåáåð; 3) ïðè óäàëåíèå ëþáîãî ðåáðà îáðàçóåòñÿ ðîâíî äâå êîìïîíåíòû ñâÿçíîñòè: 4) ïðè äîáàâëåíèè ðåáðà, ñîåäèíÿþùåãî ëþáûå äâå íå ñìåæíûå ïðåæäå âåðøèíû, îáðàçóåòñÿ ðîâíî îäèí öèêë. 1) m = n − 1 2) Ýòè ñâîéñòâà ëåãêî âèäåòü íà äèàãðàììå èç ïðèìåðà 4. Ðàñêðàñêîé ãðàôà ñ âåðøèíàìè v1, . . . , vn íàçûâàåòñÿ íàáîð öâåòîâ  íàòóðàëüíûõ ÷èñåë c1, . . . cn, ïðèïèñàííûõ âåðøèíàì òàê, ÷òî ëþáûå äâå ñìåæíûå âåðøèíû vi è vj èìåþò ðàçëè÷íûå öâåòà ci 6= cj . Ìèíèìàëüíîå ÷èñëî öâåòîâ, äîñòàòî÷íîå äëÿ ðàñêðàñêè ãðàôà G, íàçûâàåòñÿ åãî õðîìàòè÷åñêèì ÷èñëîì χ(G). Ãðàô íàçûâàåòñÿ ïîëíûì, åñëè îí ñîäåðæèò n âåðøèí è âñå n(n − 1)/2 ðåáåð, ñîåäèíÿþùèõ âñå ïàðû âåðøèí. Êàæäûé âíåäèàãîíàëüíûé ýëåìåíò ìàòðèöû ñìåæíîñòè ïîëíîãî ãðàôà ðàâåí 1. Ïîëíûé ãðàô, èìåþùèé n âåðøèí, îáîçíà÷àåòñÿ Kn. Òåîðåìà 4 (ñâîéñòâà õðîìàòè÷åñêîãî ÷èñëà). 1. Åñëè ãðàô G ñîäåðæèò ðîâíî n âåðøèí, òî χ(G) ≤ n. Åñëè ãðàô ñîäåðæèò ïîäãðàô G1, òî χ(G) ≥ χ(G1). . . . Åñëè ãðàô ñîäåðæèò ïîäãðàô Kp, òî χ(G) ≥ p. 2. G 3 χ(Kp ) = p 4 G 6 . Åñëè n ≥ 3 è ãðàô Cn ïðåäñòàâëÿåò ñîáîé n-óãîëüíèê (öèêë èç n âåðøèí è n ðåáåð, ïðè ýòîì C3 = K3 ), òî  2, åñëè n ÷åòíî, χ(Cn ) = 3, åñëè n íå÷åòíî. 6. Åñëè ãðàô G  äåðåâî, òî χ(G) = 2. 7. Åñëè ãðàô G ïëàíàðíûé, ò. å. ìîæåò áûòü èçîáðàæåí äèàãðàììîé íà ïëîñêîñòè, â êîòîðîé ðåáðà ïåðåñåêàþòñÿ òîëüêî â âåðøèíàõ, òî χ(G) ≤ 4 (òåîðåìà î 4 êðàñêàõ). 5 Ïðîñòåéøèìè íåïëàíàðíûìè ãðàôàìè ÿâëÿþòñÿ K5 è K3,3. K5 u B@@  B @  B @  B @  B @  B @  B @  B u @u  B " b " Bb "   B bb B "  B b  B " b " b  B "B b "   B B b "  " b  B B " b B  B  " b b B  B  "" b u bBu B" u e @ A@
A
A@
A @
A @
K3,3 A @
@ A
@
A A
@ A
@ @ A
@e u A
@ @
A @
A @
A @ A

@ A
@ A @ A

@ A
@ A @A

@ Ae u  ñèëó ñâîéñòâà 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 öâåòà (òåìíûå è ñâåòëûå êðóæêè). 7 8 Àëãåáðà âû÷åòîâ ïî ìîäóëþ m Ïóñòü m  íàòóðàëüíîå ÷èñëî, m ≥ 2. Íà ìíîæåñòâå Z öåëûõ ÷èñåë îïðåäåëèì äâóõìåñòíûå îïåðàöèè +, −, · (mod m) ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ ïî ìîäóëþ m êàê ôóíêöèè Z → {0, 1, . . . , m − 1}. Ðåçóëüòàòîì îïåðàöèè x + y, x − y, x · y (mod m) ÿâëÿåòñÿ îñòàòîê îò äåëåíèÿ îáû÷íîé ñóììû (ñîîòâåòñòâåííî ðàçíîñòè, ïðîèçâåäåíèÿ) öåëûõ ÷èñåë x, y íà m. Íàïðèìåð, 6 + 11 = 2 (mod 5), 9 − 20 = 1 (mod 6), 3 · 12 = 4 (mod 8), 23 = 2·2·2 = 1 (mod 7). ×èñëà 0, 1, . . . , m−1 íàçûâàþòñÿ íàèìåíüøèìè íåîòðèöàòåëüíûìè âû÷åòàìè ïî ìîäóëþ m. Ìíîæåñòâî {0, 1, . . . , m − 1} ñ îïåðàöèÿìè +, · (mod m) íàçûâàåòñÿ àëãåáðîé âû÷åòîâ ïî ìîäóëþ m è îáîçíà÷àåòñÿ êàê Zm : Zm = ({0, 1, . . . , m − 1}; +, · (mod m)). Îïåðàöèè +, · (mod m) äîñòàòî÷íî çàäàòü òîëüêî íà ìíîæåñòâå {0, 1, . . . , m − 1}. Ýòî ìîæíî ñäåëàòü, óêàçûâàÿ ðåçóëüòàòû îïåðàöèé â äâóõ òàáëèöàõ ðàçìåðà m × m, íàïðèìåð, x 0 1 x 0 1 y y · (mod 2) + (mod 2) 0 0 1 0 0 0 1 1 0 1 0 1 (÷àñòî x + y (mod 2) çàïèñûâþò êàê x ⊕ y), x 0 1 2 x 0 1 2 y y · (mod 3) 0 + (mod 3) 0 0 1 2 0 0 0 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 + (mod 4) y 1 2 3 x 0 1 2 3 1 2 3 1 2 3 2 3 1 3 1 2 · 1 (mod 4) y 1 2 3 x 0 1 2 3 1 2 3 2 2 3 2 1  àëãåáðå âàæíåéøåé çàäà÷àåé ÿâëÿåòñÿ ðåøåíèå óðàâíåíèé. Ðàññìîòðèì ïðîñòåéøåå óðàâíåíèå ax = b (mod m) (1) â àëãåáðå âû÷åòîâ. Òåîðåìà 1 (î ðåøåíèè óðàâíåíèÿ ïåðâîé ñòåïåíè â àëãåáðå âû÷åòîâ) d= (a, m) . Ïóñòü ÍÎÄ (íàèáîëüøèé îáùèé äåëèòåëü), òîãäà ñïðàâåäëèâî ñëåäóþùåå. 1. Åñëè ÷èñëî b íå äåëèòñÿ íà d, òî óðàâíåíèå (1) íå èìååò ðåøåíèÿ. 2. Eñëè b êðàòíî d, òî óðàâíåíèå (1) èìååò â ìíîæåñòâå {0, 1, . . . , m − 1} ðîâíî d ðàçëè÷íûõ ðåøåíèé. Åñëè x0  ðåøåíèå, òî îñòàëüíûå d − 1 ðåøåíèé åñòü xk = x0 + k(m/d) (mod m), . Óðàâíåíèå 12x = 45 ÍÎÄ(12, 32) = 4, à 45 íå÷åòíî. Ïðèìåð 2. Ðàññìîòðèì óðàâíåíèå Ïðèìåð 1 20x = 44 k = 1, . . . , d − 1. (mod 32) íå èìååò ðåøåíèé, òàê êàê (mod 108). (2) Èìååì ÍÎÄ(20, 108) = 4, 44 êðàòíî 4. Pàçäåëèì îáå ÷àñòè óðàâíåíèÿ (2) è ìîäóëü íà 4, ïîëó÷èì áîëåå ïðîñòîå óðàâíåíèå 5x = 11 (mod 27). (3) Äëÿ íåãî ÍÎÄ(5, 27) = 1, ïîýòîìó óðàâíåíèå (3) èìååò ðîâíî îäíî ðåøåíèå x0 ∈ {0, 1, . . . , 26}. Íåòðóäíî ïðîâåðèòü, ÷òî x0 = 13. (Ê ñîæàëåíèþ, íàéòè ðåøåíèå ìîæíî òîëüêî ïåðåáîðîì ðàçëè÷íûõ ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà âû÷åòîâ, õîòÿ âî ìíîãèõ ñëó÷àÿõ ïåðåáîð íå ïîëíûé.) Òîãäà îñòàëüíûå ðåøåíèÿ óðàâíåíèÿ (2) â ìíîæåñòâå {0, 1, . . . , 107} åñòü x1 = 13 + 27 = 40, x2 = 13 + 2 · 27 = 67, x3 = 12 + 3 · 27 = 94. : x = 13, 40, 67, 94. Ïîÿñíèì, êàê ìîæíî ñîêðàòèòü ïåðåáîð ïðè ðåøåíèè óðàâíåíèÿ (3). ×èñëà 11 è 11 + 27n, n ∈ Z, èìåþò îäèíàêîâûé îñòàòîê îò äåëåíèÿ íà 27, ïîýòîìó äîñòàòî÷íî íàéòè òàêîå íàèìåíüøåå íàòóðàëüíîå n, ÷òîáû ÷èñëî 11 + 27n äåëèëîñü íà 5. Äëÿ n = 1 ÷èñëî 11 + 27 = 38 íå äåëèòñÿ íà 5, äëÿ n = 2 ïîëó÷àåì ÷èñëî 11 + 27 · 2 = 65, êðàòíîå 5. Òàêèì îáðàçîì, óðàâíåíèå (3) ðàâíîñèëüíî óðàâíåíèþ 5x = 65 (mod 27), îòêóäà x = x0 = 65/5 = 13. Îòâåò 2 Ê óðàâíåíèþ (1) ñâîäÿòñÿ è áîëåå ñëîæíûå âèäû óðàâíåíèé â àëãåáðå âû÷åòîâ. Ðàññìîòðèì ñèñòåìó ëèíåéíûõ óðàâíåíèé ïî ìîäóëþ m ñ êâàäðàòíîé ìàòðèöåé. Tåîðåìà 2. Åñëè êâàäðàòíàÿ ñèñòåìà ëèíåéíûõ óðàâíåíèé   a11 x1 + · · · +a1n xn = b1 (mod m) an1 x1 + · · · +ann xn = bn (mod m)  .. .. èìååò îïðåäåëèòåëü ∆ òàêîé, ÷òî ÍÎÄ(∆, m) = 1, òî ýòà ñèñòåìà óðàâíåíèé èìååò ðîâíî îäíî ðåøåíèå (x1, . . . , xn) â ìíîæåñòâå {0, 1, . . . , m − 1}n. . Ðåøèì ñèñòåìó ïîðÿäêà 2 Ïðèìåð 3  3x − 2y = 1 (mod m) 4x + 7y = 2 (mod m) äëÿ ìîäóëåé m = 4, 9, 10, 16, 20, 30, 50, 100. Îïðåäåëèòåëü ñèñòåìû 3 · 7 + 2 · 4 = 29 ÿâëÿåòñÿ ïðîñòûì ÷èñëîì, óñëîâèå òåîðåìû 2 âûïîëíÿåòñÿ, ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå äëÿ êàæäîãî ìîäóëÿ. Íàéäåì åãî. Âû÷èòàÿ èç âòîðîãî óðàâíåíèÿ ïåðâîå, ïîëó÷àåì x + 9y = 1 (mod m). (4) Óìíîæèì óðàâíåíèå (4) íà 3 è âû÷òåì èç ðåçóëüòàòà ïåðâîå óðàâíåíèå èñõîäíîé ñèñòåìû, ïîëó÷èì 29y = 2, x = 1 − 9y (mod m). Ýòè ôîðìóëû îäíîçíà÷íî îïðåäåëÿþò ðåøåíèå. Çàïèøåì ðåøåíèÿ (ïàðû (x, y)) äëÿ êàæäîãî èç ðàññìàòðèâàåìûõ ìîäóëåé â òàáëèöó: m 4 9 10 16 20 30 50 100 x 3 1 9 7 19 19 9 59 y 2 1 8 10 18 28 38 38 Êâàäðàòíîå óðàâíåíèå ax2 + bx + c = 0 (mod m) ìîæíî ðåøèòü íåñêîëüêèìè ñïîñîáàìè. Îäèí èç íèõ  ðàçëîæåíèå íà ìíîæèòåëè ax2 + bx + c = a(x − x1 )(x − x2 ) (mod m). Äðóãîé ñïîñîá ñîñòîèò â ïðèìåíåíèè òåîðåìû Âèåòà1 è ôîðìóë äëÿ êîðíåé x1 + x2 = a−1 b, 1 Ôðàíñóà x1 x2 = a−1 c (mod m). Âèåò (15401603)  ôðàíöóçñêèé ìàòåìàòèê, "îòåö àëãåáðû" 3 Òðåòèé ñïîñîá ñîñòîèò â ïðèìåíåíèè îáùåé ôîðìóëû äëÿ êîðíåé êâàäðàòíîãî óðàâíåíèÿ â àðèôìåòèêå ïî ìîäóëþ m: x = (2a)−1 (−b ± p b2 − 4ac ) (mod m). Ïðèìåíÿòü åå ìîæíî òîëüêî ïðè íå÷åòíîì ìîäóëå m.  ýòîì ñëó÷àå ôîðìóëó ìîæíî óïðîñòèòü: x = a−1 (−2−1 b ± p (2−1 b)2 − ac ) (mod m). (5) . Ðåøèì óðàâíåíèå x2 + x + 2 = 0 (mod 11). Åãî ìîæíî çàïèñàòü â âèäå x2 − 10x + 24 = 0 (mod 11) è ðàçëîæèòü Ïðèìåð 4 x2 + x + 2 = x2 − 10x + 24 = (x − 4)(x − 6) (mod 11), îòêóäà x1 = 4, x2 = 6. Ëåãêî ïðîâåðèòü âûïîëíèìîñòü ôîðìóë Âèåòà: 4+6 = −1, Åñëè æå ïðèìåíèòü òðåòèé ñïîñîá è ôîðìóëó (5), òî x = −2 −1 p p √ −1 2 ± (2 ) − 2 = −6 ± 62 − 2 = 5 ± 1 (6) 4×6 = 2 (mod 11). (mod 11). √ 1 = 1 (mod 11) Èìååòñÿ √ äâà çíà÷åíèÿ êâàäðàòíîãî êîðíÿ èç 1 ïî ìîäóëþ 11: è 1 = −1 = 10 (mod 11), ïîýòîìó ïîëó÷àåì òå æå ðåøåíèÿ (6). 9 Óðàâíåíèÿ â öåëûõ ÷èñëàõ  äèñêðåòíîé ìàòåìàòèêå ïðèìåíÿþòñÿ òîëüêî öåëûå ÷èñëà, à ðàçðåøèìîñòü óðàâíåíèé â öåëûõ ÷èñëàõ îïðåäåëÿåòñÿ ñâîéñòâàìè äåëèìîñòè. Íàïðèìåð, î÷åíü ïðîñòîå óðàâíåíèå 2x = 1 íå èìååò öåëî÷èñëåííûõ ðåøåíèé.  àëãåáðå âû÷åòîâ ðàññìàòðèâàþòñÿ îñòàòêè îò äåëåíèÿ öåëûõ ÷èñåë íà ìîäóëü, ïîýòîìó âû÷åòû ïðèìåíÿþòñÿ ïðè àíàëèçå è ðåøåíèè öåëî÷èñëåííûõ óðàâíåíèé. Ðàññìîòðèì îäíî èç òàêèõ óðàâíåíèé  ëèíåéíîå óðàâíåíèå îòíîñèòåëüíî n íåèçâåñòíûõ a1 x1 + · · · + an xn = c. Çäåñü êîýôôèöèåíòû a1, . . . , an, c è íåèçâåñòíûå x1, . . . , xn  öåëûå ÷èñëà. Íåîáõîäèìûì óñëîâèåì ðàçðåøèìîñòè òàêîãî óðàâíåíèÿ ÿâëÿåòñÿ äåëèìîñòü êîýôôèöèåíòà c íà ÍÎÄ(a1, . . . , an). Èíòåðåñíî, ÷òî ýòî æå óñëîâèå ÿâëÿåòñÿ è äîñòàòî÷íûì äëÿ ðàçðåøèìîñòè óðàâíåíèÿ. Åñëè n = 1, òî ðåøåíèå, êîãäà îíî ñóùåñòâóåò, 4 åäèíñòâåííî: x1 = c/a1. Ïðè n ≥ 2 óðàâíåíèå â ñëó÷àå ðàçðåøèìîñòè èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé. Ðàññìîòðèì óðàâíåíèå ñ äâóìÿ íåèçâåñòíûìè. Äëÿ óïðîùåíèÿ îáîçíà÷åíèé çàïèøåì åãî â âèäå ax + by = c, Òåîðåìà a > 0, . Ïóñòü d =ÍÎÄ(a, |b|). Tîãäà: b 6= 0. (1) åñëè c íå êðàòíî d, òî óðàâíåíèå (1) íåðàçðåøèìî, åñëè c êðàòíî d, òî óðàâíåíèå (1) èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé, çàâèñÿùèõ îò öåëî÷èñëåííîãî ïàðàìåòðà k: x = x0 + bk, ãäå x0 ax0 = c  ëþáîå öåëîå ïðè b = ±1. y= c − ax0 − ak, b (mod |b|) k ∈ Z, (2) ïðè |b| > 1, . Ðàññìîòðèì óðàâíåíèå 3x − 7y = −24. Èìååì a = 3, b = −7, d =ÍÎÄ(3, 7) = 1, óðàâíåíèå ðàçðåøèìî. Èç óðàâíåíèÿ â àëãåáðå âû÷åòîâ 3x0 = −24 (mod 7) íàõîäèì x0 = 6. Òîãäà, ñîãëàñíî (2), Ïðèìåð x = 6 − 7k, y= −24 − 3 · 6 − 3k = 6 − 3k, −7 k ∈ Z. Ïîëåçíî áûâàåò ñäåëàòü ïðîâåðêó. Ïîäñòàâëÿÿ ïîëó÷åííûå âûðàæåíèÿ x = x(k), y = y(k) â ëåâóþ ÷àñòü èñõîäíîãî óðàâíåíèÿ, âèäèì, ÷òî ñëàãàåìûå, ñîäåðæàùèå k , óíè÷òîæàþòñÿ è ïîëó÷àåòñÿ ÷èñëî −24. Ôîðìóëû (2) îïðåäåëÿþò îáùåå ðåøåíèå. Èç íåãî çàìåíîé ïåðåìåííîé k íà êîíêðåòíûå öåëûå ÷èñëà ïîëó÷àåòñÿ áåñêîíåñêîå ìíîæåñòâî ÷àñòíûõ ðåøåíèé.  ðàññìîòðåííîì ïðèìåðå ïðè k = 0 ïîëó÷àåì ÷àñòíîå ðåøåíèå (x, y) = (6, 6), ïðè k = 1  ÷àñòíîå ðåøåíèå (x, y) = (−1, 3) è òàê äàëåå. 10 ×èñëà Ñòèðëèíãà 2-ãî ðîäà è ÷èñëà Áåëëà Êîëè÷åñòâî ðàçáèåíèé n-ìíîæåñòâà íà k íåïóñòûõ ïîäìíîæåñòâ îáîçíà÷àåòñÿ êàê Sn,k . Çíà÷åíèÿ Sn,k , n, k ≥ 0, íàçûâàþòñÿ ÷èñëàìè Ñòèðëèíãà 2-ãî ðîäà. Íàïðèìåð, S3,2 = 3, òàê êàê èìååòñÿ ðîâíî 3 ðàçáèåíèÿ ìíîæåñòâà {1, 2, 3} íà 2 ïîäìíîæåñòâà, îäíî èç êîòîðûõ ñîäåðæèò ðîâíî îäèí ýëåìåíò, à âòîðîå  äâà: 1|23, 2|13, 3|12. Óêàæåì ïðîñòåéøèå ñâîéñòâà ýòèõ ÷èñåë. 5 Åñëè n ≥ 1, òî Sn,1 = Sn,n = 1, Sn,0 = 0. Äëÿ ÷èñëà S0,0, íå èìåþùåãî ñîäåðæàòåëüíîãî ñìûñëà, ïðèìåì ôîðìàëüíîå ñîãëàøåíèå S0,0 = 1. Òåîðåìà 1. Äëÿ ÷èñåë Sn,k ñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåíòíàÿ ôîðìóëà: Sn,k = Sn−1,k−1 + kSn−1,k . . Ðàññìîòðèì óíèâåðñàëüíîå ìíîæåñòâî U = {e1, . . . , en−1, en}. Âñå åãî ðàçáèåíèÿ íà k íåïóñòûõ ïîäìíîæåñòâ ðàçäåëèì íà äâå ãðóïïû: ñîäåðæàùèå îäíîýëåìåíòíîå ïîäìíîæåñòâî {en}, êîëè÷åñòâî òàêèõ ðàçáèåíèé ðàâíî ÷èñëó Sn−1,k−1 ðàçáèåíèé (n − 1) ïîäìíîæåñòâà {e1, . . . , en−1} íà k − 1 íåïóñòûõ ïîäìíîæåñòâ; íå ñîäåðæàùèå ïîäìíîæåñòâà {en}, ïðè ýòîì ýëåìåíò en ìîæåò îêàçàòüñÿ â ëþáîì èç k íåïóñòûõ ïîäìíîæåñòâ (n − 1)-ìíîæåñòâà {e1, . . . en−1}, êîëè÷åñòâî òàêèõ ðàçáèåíèé ðàâíî kSn−1,k . Îñòàåòñÿ ïðèìåíèòü ïðàâèëî ñóììû.  Íàïðèìåð, Äîêàçàòåëüñòâî S4,3 = S3,2 + 3S3,3 = 3 + 3 · 1 = 6, S5,4 = S4,3 + 4S4,4 = 6 + 4 · 1 = 10. Ýòè ñâîéñòâà ïîçâîëÿþò çàïîëíèòü êîíå÷íîå ìíîæåñòâî ïåðâûõ ñòðîê áåñêîíå÷íîé òàáëèöû äëÿ ÷èñåë Sn,k , àíàëîãè÷íîé òðåóãîëüíèêó Ïàñêàëÿ äëÿ áèíîìèàëüíûõ êîýôôèöèåíòîâ: n 0 1 k 1 2 3 4 5 1 2 3 4 5 1 1 1 1 3 1 1 7 6 1 1 15 25 10 1 ×èñëà Ñòèðëèíãà 2-ãî ðîäà ïðèìåíÿþòñÿ, â ÷àñòíîñòè ïðè ðåøåíèè ñëåäóþùåé çàäà÷è. Ïðèìåð. Èìååòñÿ n ðàçëè÷íûõ (ïî âíåøíåìó âèäó) ïèðîæêîâ è k òàðåëîê. Êàæäàÿ òàðåëêà äîñòàòî÷íî áîëüøàÿ è ìîæåò âìåñòèòü âñå n ïèðîæêîâ. Ñêîëüêèìè ñïîñîáàìè ïèðîæêè ìîæíî ðàçëîæèòü íà òàðåëêè òàê, ÷òîáû ïóñòûõ òàðåëîê íå áûëî? Îòâåò: k!Sn,k . 6 ×èñëîì Áåëëà Bn íàçûâàåòñÿ êîëè÷åñòâî âñåõ ðàçáèåíèé n-ìíîæåñòâà íà íåïó- ñòûå ïîäìíîæåñòâà/ Ñëåäñòâèå. Ñïðàâåäëèâû ðàâåíñòâà B0 = B1 = 1, Bn = n X Sn,k . k=0 . Äëÿ ÷èñåë Áåëëà ñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåíòíàÿ ôîðìóëà: Òåîðåìà 2 Bn+1 = n X Cnk Bk . k=0 . Ðàññìîòðèì óíèâåðñàëüíîå (n+1)-ìíîæåñòâî U = {e1, . . . , en, en+1 }. Ôèêñèðóåì öåëîå k , 0 ≤ k ≤ n. Äëÿ êàæäîãî èç Cnk ïîäìíîæåñòâ A ⊆ {e1 , . . . , en }, ñîñòîÿùèõ èç k ýëåìåíòîâ, èìååòñÿ ðîâíî Bk ðàçáèåíèé ìíîæåñòâà A íà íåïóñòûå ïîäìíîæåñòâà (íàçîâåì èõ áëîêàìè). Åñëè ýëåìåíò en+1 çàíåñòè â ëþáîé èç ýòèõ áëîêîâ, òî ïîëó÷èì ðàçáèåíèå ìíîæåñòâà U .  Óêàæåì ïåðâûå ÷ëåíû ïîñëåäîâàòåëüíîñòè ÷èñåë Áåëëà: Äîêàçàòåëüñòâî n 0 1 2 3 4 5 6 ... Bn 1 1 2 5 15 52 203 . . .  ÷àñòíîñòè, âñå B3 = 5 ðàçáèåíèé ìíîæåñòâà {1, 2, 3} åñòü 1|2|3, 1|23, 2|13, 7 3|12, 123.