Элементы теории графов. Домнин Л.Н. - 7 стр.

   Èñòîðè÷åñêè ïåðâîé òåîðåìîé òåîðèè ãðàôîâ ÿâëåòñÿ óòâåð-
æäåíèå, ïðèíàäëåæàùåå Ýéëåðó è ñâÿçûâàþùåå êîëè÷åñòâî
ðåáåð, âåðøèí è èõ ñòåïåíåé.
   Òåîðåìà 1.1 Ñóììà ñòåïåíåé âåðøèí (n, m)-ãðàôà ðàâíà
                              P
                              n
óäâîåííîìó ÷èñëó åãî ðåáåð:         deg vi = 2|E| = 2m .
                              i=1
¤ Äîêàçàòåëüñòâî òðèâèàëüíî: ïîñêîëüêó ëþáîå ðåáðî èíöè-
äåíòíî äâóì âåðøèíàì, â ñóììå ñòåïåíåé âñåõ âåðøèí ãðàôà
êàæäîå ðåáðî ó÷èòûâàåòñÿ äâàæäû. ¢
   Ñ ë å ä ñ ò â è å.  ëþáîì ãðàôå ÷èñëî âåðøèí íå÷åòíîé
ñòåïåíè ÷åòíî. ¤ Ïóñòü V1 è V2  ìíîæåñòâà âåðøèí ÷åòíîé
è íå÷åòíîé ñòåïåíè ñîîòâåòñòâåííî. Î÷åâèäíî,÷òî
                 X            X
                      deg v +   deg v = 2m .
                v∈V1          v∈V2
Èìååì äâà ñëàãàåìûõ, ñóììà êîòîðûõ ÷åòíîå ÷èñëî. Ïåðâîå
ñëàãàåìîå ÷åòíî (êàê ñóììà ÷åòíûõ ÷èñåë). Çíà÷èò, âòîðîå
òàêæå äîëæíî áûòü ÷åòíûì, à ýòî ïðè ñóììèðîâàíèè íå÷åò-
íûõ ÷èñåë âîçìîæíî, åñëè òîëüêî èõ êîëè÷åñòâî ÷åòíî. ¢
   Èçîìîðôèçì ãðàôîâ. Îáðàòèìñÿ âíîâü ê ðèñ. 1.1, ãäå
ïðåäñòàâëåíû ÷åòûðå ðàçëè÷íûõ èçîáðàæåíèÿ îäíîãî è òîãî
æå ãðàôà. Çàäà÷à ðèñóíêà  ïîêàçàòü ìíîæåñòâåííîñòü îáðà-
çîâ ïðè ãðàôè÷åñêîé èíòåðïðåòàöèè ãðàôà. Ìîæíî ïîñòàâèòü
äðóãóþ, â íåêîòîðîì ñìûñëå îáðàòíóþ çàäà÷ó. Èìåþòñÿ èçîá-
ðàæåíèÿ ãðàôîâ îäíîãî ïîðÿäêà ñ îäèíàêîâûì ÷èñëîì ðåáåð.
Íåîáõîäèìî óñòàíîâèòü, ðàçíûå ýòî ãðàôû èëè îäèí, òîëüêî
ïî-ðàçíîìó èçîáðàæåííûé. ×òîáû ðàçëè÷àòü ïîäîáíûå ñèòó-
àöèè, èñïîëüçóþò ïîíÿòèå èçîìîðôèçìà.
   Èçîìîðôèçìîì íàçûâàþò âçàèìíî-îäíîçíà÷íîå ñîîòâåò-
ñòâèå ìåæäó ìíîæåñòâàìè âåðøèí äâóõ ãðàôîâ G1 è G2 , ñî-
õðàíÿþùåå îòíîøåíèå ñìåæíîñòè, à ñàìè ãðàôû íàçûâàþò
èçîìîðôíûìè. Îòîáðàæàÿ ýòî, ïèøóò: G1 ∼  =G2 èëè G1 =G2 .
   Èçîìîðôíîñòü ãðàôîâ íà ðèñ. 1.1 óñòàíîâèòü äîâîëüíî ïðî-
ñòî. Äîñòàòî÷íî ñîñòàâèòü ñïèñêè âåðøèí âñåõ ãðàôîâ, óêà-
çàâ äëÿ êàæäîé èç íèõ âñåõ åå "ñîñåäîê" (ìíîæåñòâî adj v ).
Ñðàâíèâ ñïèñêè, ëåãêî óáåäèòüñÿ â èõ èäåíòè÷íîñòè  ãðàôû


                               7