КРИТЕРИИ ВЫСОТНОСТИ АТОМА

Виктория Трифонова

КРИТЕРИИ ВЫСОТНОСТИ АТОМА

Работа посвящена высотным атомам. Доказывается, что все высотные атомы ориентируемы. Устанавливаются два новых критерия высотности атома в терминах f-графа (аналоги теоремы Понтрягина-Куратовского). Доказывается минимальность списка препятствий к высотности атома. Предоставляется новое доказательство гипотезы В.А. Васильева о планарности крестовых графов.

Математика

Дипломы

Вуз: Московский государственный университет имени М.В. Ломоносова (МГУ имени М.В. Ломоносова)

ID: 5ee28c48cd3d3e0001ffa754

UUID: 7ac7cfb0-8e4b-0138-09d0-0242ac180006

Язык: Русский

Опубликовано: больше 4 лет назад

Просмотры: 5

10.1

Виктория Трифонова

Московский государственный университет имени М.В. Ломоносова (МГУ имени М.В. Ломоносова)

Комментировать 10

Рецензировать 0

Скачать - 8,9 МБ

Поделиться работой

ÔÅÄÅÐÀËÜÍÎÅ ÃÎÑÓÄÀÐÑÒÂÅÍÍÎÅ ÁÞÄÆÅÒÍÎÅ ÎÁÐÀÇÎÂÀÒÅËÜÍÎÅ Ó×ÐÅÆÄÅÍÈÅ ÂÛÑØÅÃÎ ÎÁÐÀÇÎÂÀÍÈß "ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒ èìåíè Ì.Â. ËÎÌÎÍÎÑÎÂÀ" ÌÅÕÀÍÈÊÎ-ÌÀÒÅÌÀÒÈ×ÅÑÊÈÉ ÔÀÊÓËÜÒÅÒ ÊÀÔÅÄÐÀ ÄÈÔÔÅÐÅÍÖÈÀËÜÍÎÉ ÃÅÎÌÅÒÐÈÈ È ÏÐÈËÎÆÅÍÈÉ ÂÛÏÓÑÊÍÀß ÊÂÀËÈÔÈÊÀÖÈÎÍÍÀß ÐÀÁÎÒÀ (ÄÈÏËÎÌÍÀß ÐÀÁÎÒÀ) ñïåöèàëèñòà ÊÐÈÒÅÐÈÈ ÂÛÑÎÒÍÎÑÒÈ ÀÒÎÌÀ Âûïîëíèëà ñòóäåíòêà 607 ãðóïïû Òðèôîíîâà Âèêòîðèÿ Àëåêñàíäðîâíà ïîäïèñü ñòóäåíòà Íàó÷íûé ðóêîâîäèòåëü: àêàä. À.Ò. Ôîìåíêî ïîäïèñü íàó÷íîãî ðóêîâîäèòåëÿ Ñîðóêîâîäèòåëè: ïðîô. Å.À. Êóäðÿâöåâà ïîäïèñü ñîðóêîâîäèòåëÿ äîö. È.Ì. Íèêîíîâ ïîäïèñü ñîðóêîâîäèòåëÿ Ìîñêâà 2020

Ñîäåðæàíèå 1. Ââåäåíèå 2 2. Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ 3 3. Êðèòåðèè âûñîòíîñòè àòîìà 6 4. Íîâîå äîêàçàòåëüñòâî ãèïîòåçû Â.À.Âàñèëüåâà 1 21

1. Ââåäåíèå Ïîíÿòèå àòîìà, ïîÿâèâøååñÿ â çàäà÷àõ êà÷åñòâåííîãî àíàëèçà è êëàññèôèêàöèè äèíàìè÷åñêèõ ñèñòåì, íàõîäèò ïðèìåíåíèå â ñàìûõ ðàçíûõ ðàçäåëàõ ñîâðåìåííîé êîìáèíàòîðèêè è ìàëîìåðíîé òîïîëîãèè, òåîðèè óçëîâ [112]. Ïîíÿòèå àòîìà â ãàìèëüòîíîâîé è ñèìïëåêòè÷åñêîé ãåîìåòðèè è òîïîëîãèè áûëî ââåäåíî À.Ò. Ôîìåíêî [3] è èñïîëüçóåòñÿ äëÿ ëèóâèëëåâîé êëàññèôèêàöèè èíòåãðèðóåìûõ ãàìèëüòîíîâûõ ñèñòåì [8]. Çàäà÷à êëàññèôèêàöèè âûñîòíûõ àòîìîâ áûëà ñôîðìóëèðîâàíà À.Ò. Ôîìåíêî. Èçó÷åíèþ ýòîãî êëàññà àòîìîâ ïîñâÿùåíû ðàáîòû Â.Î. Ìàíòóðîâà [2], È.Ì. Íèêîíîâà è Í.Â. Âîë÷àíåöêîãî [12], È.Ì. Íèêîíîâà [10], Â.À. Òðèôîíîâîé [11]. Ïðè ýòîì â ðàáîòàõ [12,10,11] ïîëó÷åíû êëàññèôèêàöèè âûñîòíûõ àòîìîâ, ãðóïïû ñîáñòâåííûõ ñèììåòðèé êîòîðûõ òðàíçèòèâíî äåéñòâóþò íà ðåáðàõ [12], èëè âåðøèíàõ [10], èëè áåëûõ êîëüöàõ [11] àòîìà. Âûñîòíûå àòîìû èãðàþò âàæíóþ ðîëü â òåîðèè óçëîâ. Îêàçûâàåòñÿ, ÷òî âñå óçëû ìîãóò áûòü çàêîäèðîâàíû (íåîäíîçíà÷íî) âûñîòíûìè àòîìàìè. À.À. Îøåìêîâûì â ðàáîòå [16] áûëî ââåäåíî ïîíÿòèå ïîìîùüþ f -ãðàôîâ f -ãðàôà. Âûÿñíèëîñü, ÷òî ñ óäîáíî îïèñûâàòü ïåðåñòðîéêè òîðîâ Ëèóâèëëÿ èíòåãðèðóåìûõ ãà- ìèëüòîíîâûõ ñèñòåì, à òàêæå ëåãêî ðåàëèçîâàòü àëãîðèòì ïåðå÷èñëåíèÿ òàêèõ ïåðåñòðîåê. È.Ì. Íèêîíîâ [10] îáíàðóæèë, ÷òî âûñîòíîñòü àòîìà ýêâèâàëåíòíà îðèåíòèðîâàííîé âëîæèìîñòè åãî f -ãðàôà â ïëîñêîñòü (òåîðåìà 1). Â ðàçäåëå 2 íàñòîÿùåé ðàáîòû äîêàçûâàåòñÿ, ÷òî âñå âûñîòíûå àòîìû ÿâëÿþòñÿ îðèåíòèðóåìûìè (óòâåðæäåíèå 1). Â ðàçäåëå 3 óñòàíàâëèâàþòñÿ äâà íîâûõ êðèòåðèÿ âûñîòíîñòè àòîìà â òåðìèíàõ åãî f -ãðàôà (òåîðåìà K1 è òåîðåìà K2 ). Õîòÿ âñå êðèòåðèè âûñîòíîñòè ïî ñóòè ýêâèâàëåíò- íû, îíè âåñüìà ïîëåçíû â ðàçíûõ ñèòóàöèÿõ äëÿ äîêàçàòåëüñòâà âûñîòíîñòè ðàçëè÷íûõ êëàññîâ àòîìîâ. Íàéäåíû ïðåïÿòñòâèÿ ê îðèåíòèðîâàííîé âëîæèìîñòè f -ãðàôà â ïëîñ- êîñòü, äîêàçàíà èõ ìèíèìàëüíîñòü (óòâåðæäåíèå 2). Â ðàçäåëå 4 ïðèâîäèòñÿ íîâîå äîêàçàòåëüñòâî ãèïîòåçû Â.À.Âàñèëüåâà [21] î êðèòåðèè ïëàíàðíîñòè ãðàôà ñ âåðøèíàìè ñòåïåíè 4 è äîïîëíèòåëüíîé êðåñòîâîé ñòðóêòóðîé. Âïåðâûå ãèïîòåçà áûëà äîêàçàíà Â.Î.Ìàíòóðîâûì [22]. Àâòîð áëàãîäàðåí À.Ò. Ôîìåíêî çà ïîñòàíîâêó çàäà÷ è ïîñòîÿííîå âíèìàíèå ê ðàáîòå. Àâòîð òàêæå áëàãîäàðèò Å.À.Êóäðÿâöåâó è È.Ì.Íèêîíîâà çà ïîëåçíûå îáñóæäåíèÿ è öåííûå çàìå÷àíèÿ. 2

2. Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ M 2 ãëàäêîå çàìêíóòîå äâóìåðíîå ìíîãîîáðàçèå, f : M 2 → R ôóíêöèÿ 2 −1 Ìîðñà íà M è f (0) = {x ∈ M 2 : f (x) = 0}, åå ñâÿçíûé êðèòè÷åñêèé óðîâåíü. −1 Òîãäà ñóùåñòâóåò ε > 0, òàêîå, ÷òî f ([−ε, +ε]) íå ñîäåðæèò êðèòè÷åñêèõ òî÷åê, êðîìå −1 ëåæàùèõ íà êðèòè÷åñêîì óðîâíå f (0). Îïðåäåëåíèå. Àòîìîì íàçûâàåòñÿ ïîâåðõíîñòü f −1 ([−ε, +ε]) ñ çàäàííîé íà íåé ôóíêöèåé Ìîðñà f . Äâà àòîìà íàçûâàþòñÿ èçîìîðôíûìè, åñëè ñóùåñòâóåò ãîìåîìîðÏóñòü ôèçì ïîâåðõíîñòåé (ñîõðàíÿþùèé îðèåíòàöèþ, åñëè ïîâåðõíîñòü îðèåíòèðîâàíà), êîòîðûé ëèíèè óðîâíÿ ôóíêöèè ïåðåâîäèò â ëèíèè óðîâíÿ ôóíêöèè. Îïðåäåëåíèå. Íàçîâåì àòîì, ïîðîæäåííûé ôóíêöèåé f , âûñîòíûì, åñëè ñóùå−1 ñòâóåò òàêîå âëîæåíèå i : f ([−ε, +ε]) → R3 , ÷òî f (p) = z(i(p)) äëÿ êàæäîé òî÷êè p ∈ f −1 ([−ε, +ε]), ãäå z ñòàíäàðòíàÿ êîîðäèíàòà â ïðîñòðàíñòâå R3 , ò.å. z ôóíêöèÿ −1 âûñîòû íà i(f ([−ε, +ε])). Ñëó÷àé ïîãðóæåíèÿ (âìåñòî âëîæåíèÿ) èçó÷åí â ðàáîòå Å.À.Êóäðÿâöåâîé [13]. Ñëåäóþùåå óòâåðæäåíèå áûëî ñôîðìóëèðîâàíî â [2, çàìå÷àíèå ïåðåä îïðåäåëåíèåì 6] áåç äîêàçàòåëüñòâà. Òàê êàê ìû íå íàøëè åãî äîêàçàòåëüñòâà â ëèòåðàòóðå, òî ïðèâîäèì äîêàçàòåëüñòâî â äàííîé äèïëîìíîé ðàáîòå. Óòâåðæäåíèå 1. Âñå âûñîòíûå àòîìû ÿâëÿþòñÿ îðèåíòèðóåìûìè. Äîêàçàòåëüñòâî. Âûñîòíûé àòîì, êàê ìíîãîáðàçèå ñ êðàåì, âëîæèì â R3 òàê, ÷òî åãî êðàÿ ëåæàò â äâóõ ïàðàëëåëüíûõ ïëîñêîñòÿõ. Èõ ìîæíî çàêëåèòü äèñêàìè 3 òàê, ÷òî ïîëó÷èòñÿ âëîæåííàÿ â R çàìêíóòàÿ äâóìåðíàÿ ïîâåðõíîñòü. Äîêàæåì, ÷òî 3 ëþáàÿ âëîæèìàÿ â R çàìêíóòàÿ äâóìåðíàÿ ïîâåðõíîñòü S îðèåíòèðóåìà. Èç ýòîãî áóäåò ñëåäîâàòü îðèåíòèðóåìîñòü âûñîòíîãî àòîìà. Íàì ïîíàäîáèòñÿ ñëåäóþùàÿ òåîðåìà. Òåîðåìà (ÆîðäàíàÁðàóýðà [14]). Äîïîëíåíèå ê êîìïàêòíîé ñâÿçíîé ãèïåðïîâåðõíîñòè R â Rn ñîñòîèò èç äâóõ îòêðûòûõ ñâÿçíûõ ìíîæåñòâ: "âíåøíåãî" D0 è "âíóòðåííåãî" D1 . Áîëåå òîãî, ãðàíèöåé çàìûêàíèÿ êàæäîãî èç äàííûõ ìíîæåñòâ ÿâëÿåòñÿ ãèïåðïîâåðõíîñòü R. 3 3 Èç äàííîé òåîðåìû ñëåäóåò, ÷òî ïîâåðõíîñòü S , âëîæåííàÿ â R , ðàçáèâàåò R íà äâà òðåõìåðíûõ ìíîãîîáðàçèÿ ñ êðàåì S . Ýòè ìíîãîîáðàçèÿ îðèåíòèðóåìûå, ïîñêîëüêó â R3 íåò íåîðèåíòèðóåìûõ òðåõìåðíûõ ïîäìíîãîîáðàçèé. Òîãäà â êàæäîé òî÷êå ãðàíèöû S ýòèõ ìíîãîîáðàçèé îäíîçíà÷íî îïðåäåëåíà âíåøíÿÿ è âíóòðåííÿÿ íîðìàëü. Ýòî îçíà÷àåò, ÷òî ïîâåðõíîñòü S îðèåíòèðóåìà. Óòâåðæäåíèå äîêàçàíî. Îïðåäåëåíèå. Ýêâèâàëåíòíûì îáðàçîì àòîì (à òî÷íåå, àòîì ñ òî÷íîñòüþ äî èçî2 # ìîðôèçìà) ìîæíî çàäàòü êàê îñíàùåííóþ ïàðó (P , K) (òîæå ðàññìàòðèâàåìóþ ñ 2 òî÷íîñòüþ äî èçîìîðôèçìà), ãäå P êîìïàêòíàÿ ïîâåðõíîñòü ñ êðàåì, K íåïóñòîé 2 êîíå÷íûé ñâÿçíûé ãðàô, âëîæåííûé â P è èìåþùèé âåðøèíû ñòåïåíè 4, ïðè÷åì ìíî2 1 1 2 æåñòâî P \ K ÿâëÿåòñÿ íåñâÿçíûì îáúåäèíåíèåì êîëåö S × (0, 1], S × {1} ⊂ ∂P , è ìíîæåñòâî êîëåö ðàçáèòî íà äâà ïîäìíîæåñòâà (áåëûå è ÷åðíûå êîëüöà) òàêèì îáðàçîì, ÷òî ê êàæäîìó ðåáðó ãðàôà K ïðèìûêàþò ðîâíî îäíî áåëîå êîëüöî è ðîâíî îäíî ÷åðíîå êîëüöî. Óêàçàííîå ðàçáèåíèå êîëåö íà áåëûå è ÷åðíûå íàçûâàåòñÿ îñíàùåíèåì ïàðû (P 2 , K), è îñíàùåííàÿ ïàðà îáîçíà÷àåòñÿ ÷åðåç (P 2 , K)# . Äâå îñíàùåííûå ïàðû ñ÷èòàþòñÿ èçîìîðôíûìè, åñëè ñóùåñòâóåò ãîìåîìîðôèçì ïàð, ñîõðàíÿþùèé îðèåíòàöèþ ïîâåðõíîñòåé è ðàñêðàñêó êîëåö. Ãðàô K áóäåì íàçûâàòü îñòîâîì Äåéñòâèòåëüíî, ïî àòîìó îäíîçíà÷íî ñòðîèòñÿ îñíàùåííàÿ ïàðà àòîìà. 2 # (P , K) , ãäå áåëûå (ñîîòâåòñòâåííî ÷åðíûå) êîëüöà çàäàþòñÿ íåðàâåíñòâîì f > 0 (ñîîòâåòñòâåííî 2 # Âåðíî è îáðàòíîå: ïî îñíàùåííîé ïàðå (P , K) îäíîçíà÷íî ñòðîèòñÿ àòîì. 3 f < 0).

Àòîì (òî÷íåå, àòîì ñ òî÷íîñòüþ äî èçîìîðôèçìà) ìîæåò áûòü îïðåäåëåí òàêæå êàê f- ãðàô (ñì. [16]), ÷òî â ñâîþ î÷åðåäü ïîçâîëÿåò ðàáîòàòü ñ àòîìàìè êàê ñ êîìáèíàòîðíûìè îáúåêòàìè. Îïðåäåëåíèå (À.À.Îøåìêîâ [16], 1994). Êîíå÷íûé ñâÿçíûé ãðàô G íàçîâåì f - ãðàôîì, åñëè îí óäîâëåòâîðÿåò ñëåäóþùèì óñëîâèÿì: 1) Âñå âåðøèíû ãðàôà G èìåþò ñòåïåíü 3. 2) Íåêîòîðûå ðåáðà ãðàôà G îðèåíòèðîâàíû, ïðè÷åì ê êàæäîé âåðøèíå ãðàôà G ïðèìûêàþò ðîâíî äâà îðèåíòèðîâàííûõ ðåáðà, èç êîòîðûõ îäíî âõîäèò â âåðøèíó, à äðóãîå âûõîäèò èç íåå. Îòìåòèì, ÷òî âåðøèíà ìîæåò áûòü íà÷àëîì è êîíöîì îäíîãî è òîãî æå îðèåíòèðîâàííîãî ðåáðà-ïåòëè. 3) Êàæäîìó íåîðèåíòèðîâàííîìó ðåáðó ãðàôà G ïðèïèñàíî ÷èñëî 2 # Îïèøåì ïîñòðîåíèå f -ãðàôà ïî àòîìó X = (P , K) . ±1. Çàôèêñèðóåì ïðîèçâîëüíûì îáðàçîì îðèåíòàöèþ íà êàæäîé ãðàíè÷íîé îêðóæíîñòè áåëûõ êîëåö àòîìà. Â êà÷åñòâå íåîðèåíòèðîâàííîãî ðåáðà âåðøèíó ãðàôà K f -ãðàôà G áåðåòñÿ îòðåçîê, ïðîõîäÿùèé ÷åðåç è ñîåäèíÿþùèé ãðàíèöû ïðîòèâîïîëîæíûõ áåëûõ êîëåö (ñì. ðèñ. 1), à â êà÷åñòâå âåðøèí ñîîòâåòñòâóþùèå êîíöû îòðåçêà. Â ðîëè îðèåíòèðîâàííûõ ðåáåð âûñòóïàþò ïðèìûêàþùèå ê âåðøèíàì äóãè áåëûõ êîëåö ñ ñîîòâåòñòâóþùåé îðèåíòàöèåé. f -Ãðàô, ãðàôîì. ïîñòðîåííûé ïî ÷åðíûì êîëüöàì àòîìà Ðèñ. 1. Ïîñòðîåíèå Èç äàííîãî ïîñòðîåíèÿ ÿñíî, ÷òî f -ãðàô (P 2 , K), f -ãðàôà íàçîâåì äâîéñòâåííûì f - ïî àòîìó (äâîéñòâåííûé f -ãðàô) ñîñòîèò èç íåïó- ñòîãî ìíîæåñòâà îðèåíòèðîâàííûõ öèêëîâ, êîòîðûì ñîîòâåòñòâóþò îðèåíòèðîâàííûå ãðàíè÷íûå îêðóæíîñòè áåëûõ (ñîîòâåòñòâåííî ÷åðíûõ) êîëåö, è íåîðèåíòèðîâàííûõ ðåáåð. Îðèåíòèðîâàííûå öèêëû áóäåì íàçûâàòü Äëÿ çàâåðøåíèÿ ïîñòðîåíèÿ f -ãðàôà îêðóæíîñòÿìè. îñòàëîñü ðàññòàâèòü ìåòêè íà íåîðèåíòèðîâàí- íûõ ðåáðàõ. Äëÿ ýòîãî ðàññìîòðèì ìàëóþ îêðåñòíîñòü íåîðèåíòèðîâàííîãî ðåáðà â 2 ïîâåðõíîñòè P . Ýòî ïðÿìîóãîëüíèê, äâå ïðîòèâîïîëîæíûå ñòîðîíû êîòîðîãî ëåæàò íà ãðàíè÷íûõ îêðóæíîñòÿõ áåëûõ êîëåö, è ïîòîìó îðèåíòèðîâàíû. Åñëè ýòè ñòîðîíû 4

ïðÿìîóãîëüíèêà èíäóöèðóþò îäíó è òó æå îðèåíòàöèþ ãðàíèöû ïðÿìîóãîëüíèêà, òî ñòàâèì ìåòêó ε = +1. Åñëè æå îðèåíòàöèè ïðîòèâîïîëîæíû, òî ñòàâèì ìåòêó ε = −1. P 2 îðèåíòèðîâàíà, òî ñîîòâåòñòâóþùèé f -ãðàô èìååò Çàìåòèì, ÷òî åñëè ïîâåðõíîñòü âñå ìåòêè, ðàâíûå +1. Ïîñêîëüêó âñþäó äàëåå â äàííîì ðàçäåëå è â ðàçäåëå 3 ìû èìååì äåëî òîëüêî ñ âûñîòíûìè àòîìàìè, êîòîðûå îðèåíòèðóåìû ïî óòâåðæäåíèþ 1, 2 òî áóäåì ñ÷èòàòü, ÷òî ïîâåðõíîñòü P îðèåíòèðóåìà è íà íåé ôèêñèðîâàíà îðèåíòàöèÿ, à ñîîòâåòñòâóþùèé f -ãðàô áóäåì ðàññìàòðèâàòü áåç ìåòîê. Â ðàçäåëå 4 â îïðåäåëåíèè P 2 áóäåì ñ÷èòàòü êîìïàêòíóþ ïîâåðõíîñòü ñ êðàåì è áóäåì àòîìà ïîä ïîâåðõíîñòüþ óòî÷íÿòü, êîãäà îíà îðèåíòèðóåìà, à êîãäà íåîðèåíòèðóåìà. Îïðåäåëåíèå. Íåîðèåíòèðîâàííîå ðåáðî f -ãðàôà áóäåì íàçûâàòü âíóòðåííåé õîð- äîé, åñëè õîðäîé. îáà åãî êîíöà ëåæàò íà îäíîé îêðóæíîñòè. Èíà÷å ðåáðî íàçîâåì Îïðåäåëåíèå. Íàçîâåì âíåøíåé f -ãðàô îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü, åñëè åãî ìîæíî âëîæèòü â ïëîñêîñòü òàê, ÷òî îêðóæíîñòè, ñîåäèíåííûå õîòÿ áû îäíèì ðåáðîì, ëåæàò îäíà â äðóãîé òîãäà è òîëüêî òîãäà, êîãäà îíè èìåþò ïðîòèâîïîëîæíóþ îðèåíòàöèþ. Ñîîòâåòñòâóþùåå âëîæåíèå òàêæå áóäåì íàçûâàòü îðèåíòèðîâàííûì. Ñëåäóþùèé êðèòåðèé ïîçâîëÿåò íàì ñâåñòè çàäà÷ó ïðîâåðêè âûñîòíîñòè àòîìà ê ïðîâåðêå îðèåíòèðîâàííîé âëîæèìîñòè åãî f -ãðàôà â ïëîñêîñòü. Òåîðåìà 1 (È.Ì. Íèêîíîâ, êðèòåðèé âûñîòíîñòè àòîìà [10]). Àòîì ÿâëÿ- åòñÿ âûñîòíûì òîãäà è òîëüêî òîãäà, êîãäà åãî f-ãðàô îðèåíòèðîâàííî âëîæèì â ïëîñêîñòü. Çàìå÷àíèå. Åñëè àòîì âûñîòíûé, òî, ïîìåíÿâ ðàñêðàñêó åãî êîëåö, ïîëó÷èì âû- ñîòíûé àòîì. Ïîýòîìó òåîðåìà 1 áóäåò âåðíà, åñëè f -ãðàô çàìåíèòü íà äâîéñòâåííûé f -ãðàô. Îïðåäåëèì ïîíÿòèå ïîä-f -ãðàôà. Îïðåäåëåíèå. f -Ãðàô G íàçûâàåòñÿ ïîä-f -ãðàôîì íåêîòîðîãî f -ãðàôà H , åñëè ìíîæåñòâî îêðóæíîñòåé ãðàôà H , à êàæäîå f -ãðàôà H . f -ãðàôà G ÿâëÿåòñÿ ïîäìíîæåñòâîì ìíîæåñòâà îêðóæíîñòåé íåîðèåíòèðîâàííîå ðåáðî f -ãðàôà G f- ÿâëÿåòñÿ íåîðèåíòèðîâàííûì ðåáðîì Òåïåðü äàäèì îïðåäåëåíèå èçîìîðôíîñòè è f -ãîìåîìîðôíîñòè f -ãðàôîâ. Îïðåäåëåíèå. f -Ãðàôû G1 è G2 íàçûâàþòñÿ èçîìîðôíûìè, åñëè ñóùåñòâóåò âçàèìíîf : V1 → V2 f -ãðàôà G1 íà ìíîæåñòâî V2 âåðøèí f -ãðàôà G2 , óäîâëåòâîðÿþùåå óñëîâèþ: âåðøèíû A, B ∈ V1 ñîåäèíåíû ðåáðîì â òîì è òîëüêî òîì ñëó÷àå, êîãäà âåðøèíû f (A), f (B) ∈ V2 ñîåäèíåíû ðåáðîì, ïðè÷åì åñëè ðåáðî îðèåíòèðîâàíî îò A ê B (îò B ê A ), òî ñîîòâåòñòâóþùåå ðåáðî îðèåíòèðîâàíî îò f (A) ê f (B) (ñîîòâåòñòâåííî îò f (B) ê f (A)). Îïðåäåëåíèå. f -Ãðàô G f -ãîìåîìîðôåí f -ãðàôó H , åñëè ñóùåñòâóåò êîíå÷íàÿ öåïî÷êà ïðåîáðàçîâàíèé G = G1 → . . . →Gn = H , êîìïîçèöèÿ êîòîðûõ ïðåîáðàçóåò G â H è êàæäîå èç êîòîðûõ îòíîñèòñÿ ê îäíîìó èç ñëåäóþùèõ âèäîâ: 1) èçîìîðôèçì f -ãðàôîâ; 2) ïîäðàçáèåíèå íåîðèåíòèðîâàííîãî ðåáðà f -ãðàôà (ñì. ðèñ. 2a,b); îäíîçíà÷íîå îòîáðàæåíèå ìíîæåñòâà V1 âåðøèí 3) îáðàòíàÿ îïåðàöèÿ ê ïîäðàçáèåíèþ íåîðèåíòèðîâàííîãî ðåáðà. Êàæäîå èç òðåõ äàííûõ âèäîâ ïðåîáðàçîâàíèé áóäåì íàçûâàòü ôèçìà. Îïðåäåëåíèå. Ïðåïÿòñòâèåì V îïåðàöèåé f -ãîìåîìîð- f -ãðàô, ñîñòîÿùèé èç äâóõ îêðóæíîñòåé ñ âåðøèíàìè v1 , v2 , v3 íà îäíîé îêðóæíîñòè è u1 , u2 , u3 íà äðóãîé, öèêëè÷åñêèé ïîðÿäîê êîòîðûõ ñîãëàñîâàí ñ îðèåíòàöèåé ñîîòâåòñòâóþùåé îêðóæíîñòè, è õîðä (v1 , u1 ), (v2 , u2 ), (v3 , u3 ) (ñì. ðèñ. 3,a). íàçîâåì 5

Ðèñ. 2. Îïåðàöèÿ ïîäðàçáèåíèÿ íåîðèåíòèðîâàííîãî ðåáðà Îïðåäåëåíèå. Ïðåïÿòñòâèåì V (r), r ≥ 1, îêðóæíîñòè c âåðøèíàìè íàçîâåì f -ãðàô, f -ãðàôà ñîñòîÿùèé èç îäíîé v1 , . . . , v4r+2 , öèêëè÷åñêèé ïîðÿäîê êîòîðûõ ñîãëàñîâàí ñ îðè(v4i−3 , v4i ), 1 ≤ i ≤ r, (v4i−1 , v4i+2 ), 1 ≤ i ≤ r, è (v4r+1 , v2 ) åíòàöèåé îêðóæíîñòè, è õîðä (ñì. ðèñ. 3,b). Ðèñ. 3. Ïðåïÿòñòâèÿ V è V (r) 3. Êðèòåðèè âûñîòíîñòè àòîìà Â äàííîì ðàçäåëå áóäåì ñ÷èòàòü, ÷òî ïîâåðõíîñòü âàíà îðèåíòàöèÿ, à ó ñîîòâåòñòâóþùåãî f -ãðàôà P 2 îðèåíòèðóåìà è íà íåé ôèêñèðî- ìåòêè íà âñåõ õîðäàõ ïðåäïîëàãàþòñÿ ðàâíûìè +1. Òåîðåìà K1 (Â.À. Òðèôîíîâà, êðèòåðèé âûñîòíîñòè àòîìà [15]). Àòîì ÿâëÿåòñÿ âûñîòíûì òîãäà è òîëüêî òîãäà, êîãäà åãî f -ãðàô íå ñîäåðæèò ïîä-f -ãðàôà, f -ãîìåîìîðôíîãî ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Äîêàçàòåëüñòâî. Äîêàæåì íåîáõîäèìîñòü. Ïóñòü äàí âûñîòíûé àòîì, à F åãî f -ãðàô. Òîãäà ïî òåîðåìå 1 ñóùåñòâóåò îðèåíòèðîâàííîå âëîæåíèå R f -ãðàôà F â ïëîñêîñòü. Ëþáîé ïîä-f -ãðàô L ýòîãî f -ãðàôà ÿâëÿåòñÿ îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü. L ÿâëÿåòñÿ ïîäìíîæåñòâîì îêðóæíîñòåé è ñîîòâåòñòâåííî õîðä â R, ïðè÷åì ëþáûå îêðóæíîñòè, ñîåäèíåííûå õîòÿ áû îäíèì ðåáðîì â R, ëåæàò îäíà â äðóãîé òîãäà è òîëüêî òîãäà, êîãäà îíè èìåþò ïðîòèâîïîëîæíóþ îðèåíòàöèþ. Ýòî îçíà÷àåò, ÷òî L îðèåíòèðîâàííî âëîæèì â ïëîñêîñòü. Ëåììà 1. Ëþáîé f -ãðàô, f -ãîìåîìîðôíûé îðèåíòèðîâàííî âëîæèìîìó f -ãðàôó â ïëîñêîñòü, òàêæå ÿâëÿåòñÿ îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü. Äåéñòâèòåëüíî, ìíîæåñòâî îêðóæíîñòåé è õîðä 6

Äîêàçàòåëüñòâî. Ïóñòü f -ãðàô G îðèåíòèðîâàííî âëîæèì â ïëîñêîñòü. Ïîêàæåì, ÷òî îïåðàöèåé ïîäðàçáèåíèÿ íåîðèåíòèðîâàííîãî ðåáðà ýòîãî åíòèðîâàííî âëîæèìûé f -ãðàôà ìû ïîëó÷èì îðè- f -ãðàô. Ðàññìîòðèì îðèåíòèðîâàííîå âëîæåíèå â ïëîñêîñòü è ïðîèçâîëüíîå f -ãðàôà. Â ñåðåäèíó ðåáðà e âñåãäà ìîæíî âñòàâèòü f -ãðàô îñòàâàëñÿ ïëàíàðíûì. Íà ðèñóíêå 4a, b, c, d äîáàâëÿåìîé îêðóæíîñòè, ÷òîáû ïîëó÷åííûé f -ãðàô îñòàâàëñÿ íåîðèåíòèðîâàííîå ðåáðî e R f -ãðàôà G ýòîãî îêðóæíîñòü òàê, ÷òîáû ïîëó÷åííûé ïîêàçàíà îðèåíòàöèÿ íå òîëüêî ïëàíàðíûì, íî è îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü. a) c) b) d) Ðèñ. 4. Âñòàâêà îêðóæíîñòè â ðåáðî e Òàê, íà ðèñóíêå 4a ðåáðî îêðóæíîñòè h âî âëîæåíèè e ÿâëÿåòñÿ âíóòðåííåé õîðäîé f -ãðàôà G è ëåæèò âíå R, íà êîòîðóþ îíî îïèðàåòñÿ. Òàê êàê äîáàâëåííàÿ îêðóæ- h ëåæàò âíå äðóã äðóãà, òî èõ îðèåíòàöèè äîëæíû ñîâïàäàòü. Íà e ÿâëÿåòñÿ âíóòðåííåé õîðäîé f -ãðàôà G è ëåæèò âíóòðè îêðóæíîñòè h âî âëîæåíèè R, íà êîòîðóþ îíî îïèðàåòñÿ. Íà ðèñóíêå 4c ðåáðî e ÿâëÿåòñÿ âíåøíåé õîðäîé, ñîåäèíÿþùåé äâå îêðóæíîñòè, ëåæàùèå îäíà â äðóãîé. Íà ðèñóíêå 4d ðåáðî e ÿâëÿåòñÿ âíåøíåé õîðäîé, ñîåäèíÿþùåé äâå îêðóæíîñòè, êîòîðûå ëåæàò âíå äðóã íîñòü è îêðóæíîñòü ðèñóíêå 4b ðåáðî äðóãà. Òåïåðü ïîêàæåì, ÷òî îáðàòíîé îïåðàöèåé ê ïîäðàçáèåíèþ íåîðèåíòèðîâàííîãî ðåáðà f -ãðàôà G ìû ïîëó÷èì îðèåíòèðîâàííî âëîæèìûé Ðàññìîòðèì óäàëÿåìóþ îêðóæíîñòü O f -ãðàô. îðèåíòèðîâàííîãî âëîæåíèÿ â ïëîñêîñòü. Èç íåå âûõîäÿò äâå âíåøíèå õîðäû l1 , l2 . îòìå÷åíàÿ ñåðûì öâåòîì, ëåæèò âíóòðè äðóãîé îêðóæíîñòè O1 , O è O1 ýòîãî f -ãðàôà O, ñ êîòîðîé ñîåäèíåíà âíåøíèìè õîðäàìè, ïðè÷åì âíåøíèå õîðäû ëåæàò âíå îêðóæíîñòè îêðóæíîñòè R Íà ðèñóíêå 5a îêðóæíîñòü O. Ñëó÷àé, êîãäà ëåæàò âíå äðóã äðóãà, ðàññìàòðèâàåòñÿ àíàëîãè÷íî (äåéñòâèòåëü- íî, âìåñòî âëîæåíèÿ f -ãðàôà G â ïëîñêîñòü ìû ìîæåì ðàññìîòðåòü åãî âëîæåíèå â ñôåðó, òîãäà ñëó÷àè, êîãäà îáå õîðäû l1 , l2 è îêðóæíîñòü èëè îäíîâðåìåííî ñíàðóæè îêðóæíîñòè O1 , ëåæàò îäíîâðåìåííî âíóòðè ñòàíóò ïîëíîñòüþ àíàëîãè÷íû äðóã äðó- ãó). Óäàëèì îäíó ïîëóîêðóæíîñòü îêðóæíîñòè 7 O O è ñíèìåì îðèåíòàöèþ âòîðîé ïî-

ëóîêðóæíîñòè. Òîãäà íîâîå íåîðèåíòèðîâàííîå ðåáðî ïîëó÷åííîãî f -ãðàôà ñîñòîèò èç äâóõ âíåøíèõ õîðä è íåîðèåíòèðîâàííîé âòîðîé ïîëóîêðóæíîñòè îêðóæíîñòè f -ãðàô, O. Òàêîé î÷åâèäíî, îñòàíåòñÿ îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü. Ðèñ. 5. Ïðåîáðàçîâàíèå îêðóæíîñòè O è õîðä l1 , l2 â íåîðèåíòèðîâàííîå ðåáðî Íà ðèñóíêå 5b,c ïîêàçàíû äâà ñëó÷àÿ ðàñïîëîæåíèÿ âíåøíèõ õîðä è îêðóæíîñòåé O1 è O2 , ñ êîòîðûìè ñîåäèíåíà îêðóæíîñòü 5b îêðóæíîñòè O. O1 è O2 O, îòìå÷åíàÿ ñåðûì öâåòîì. Íà ðèñóíêå ëåæàò âíå äðóã äðóãà, à õîðäû Òîãäà íîâîå íåîðèåíòèðîâàííîå ðåáðî f -ãðàôà l1 è l2 ëåæàò âíå îêðóæíîñòè ïîëó÷èì óæå ðàññìîòðåííûì ñïîñî- áîì. Îíî ñîñòîèò èç äâóõ âíåøíèõ õîðä è íåîðèåíòèðîâàííîé âòîðîé ïîëóîêðóæíîñòè îêðóæíîñòè O. O1 ëåæèò âíóòðè îêðóæíîñòè O2 , à õîðäû l1 è l2 ëåæàò âíå îêðóæO. Òîãäà èíâåðñèåé îòíîñèòåëüíî îêðóæíîñòè O2 äàííûé ñëó÷àé ñâîäèòñÿ ê ðàññìîòðåííîìó, â êîòîðîì îêðóæíîñòè O1 è O2 ëåæàò âíå äðóã äðóãà. Íà ðèñóíêå 5c îêðóæíîñòü O1 ëåæèò âíóòðè îêðóæíîñòè O , à îêðóæíîñòü O2 ëåæèò Ïóñòü îêðóæíîñòü íîñòè âíå. Òîãäà åñëè ïîëó÷èòü íåîðèåíòèðîâàííîå ðåáðî ðàññìîòðåííûì ñïîñîáîì, îêðóæíîñòè O1 è O2 áóäóò ëåæàòü âíå äðóã äðóãà, íî èìåòü ïðîòèâîïîëîæíóþ îðèåíòàöèþ. ×òîáû ýòîãî íå äîïóñòèòü, èçìåíèì âëîæåíèå O âìåñòå ñ ëåæàùåé âíóòðè íåå ÷àñòüþ Ïðåîáðàçóÿ îêðóæíîñòü åíòèðîâàííî âëîæèìûé O è õîðäû l1 , l2 f -ãðàô. R íà òàêîå, ïðè êîòîðîì îêðóæíîñòü f -ãðàôà G çàìåíåíà íà åå çåðêàëüíûé îáðàç. â íåîðèåíòèðîâàííîå ðåáðî, ìû ïîëó÷èì îðè- 8

O1 Ïóñòü îêðóæíîñòü îêðóæíîñòè ëåæèò âíóòðè îêðóæíîñòè O, à îêðóæíîñòü O ëåæèò âíóòðè O2 . Òîãäà èíâåðñèåé îòíîñèòåëüíî îêðóæíîñòè O2 äàííûé ñëó÷àé ñâîäèòñÿ O1 ëåæèò âíóòðè îêðóæíîñòè O, à îêðóæ- ê ðàññìîòðåííîìó, â êîòîðîì îêðóæíîñòü íîñòü l1 O2 ëåæèò âíå. Ñëó÷àé, êîãäà õîðäû l1 è l2 ëåæàò âíóòðè îêðóæíîñòè O, è l2 ëåæàò âíå, èíâåðñèåé îòíîñèòåëüíî îêðóæíîñòè Ëåììà äîêàçàíà. Èç ëåììû 1 ñëåäóåò, ÷òî f -ãðàô F O. ñâîäèòñÿ ê ñëó÷àþ, êîãäà íå ñîäåðæèò ïîä-f -ãðàô, f -ãîìåîìîðôíûé íå îðèåíòèðîâàííî âëîæèìîìó â ïëîñêîñòü. f -ãðàô, Äîêàæåì, ÷òî ñåðèè V (r), r ≥ 1, V èëè ïðåïÿòñòâèå èç íå ÿâëÿåòñÿ îðèåíòèðîâàííî âëîæèìûì â ïëîñêîñòü. Ïîñêîëüêó àòîì ñ íàÿ âëîæèìîñòü ïðåäñòàâëÿþùèé ñîáîé ïðåïÿòñòâèå V f -ãðàôîì V f -ãðàô V (1), òî îðèåíòèðîâàíâëîæèìîñòè V (1). Òàêèì îáðàçîì, èìååò äâîéñòâåííûé ýêâèâàëåíòíà îðèåíòèðîâàííîé f -ãðàôû ñåðèè V (r), r ≥ 1. Ëåììà 2. Êàæäûé f -ãðàô èç ñåðèè V (r), r ≥ 1, ñîäåðæèò ïîäãðàô, ãîìåîìîðôíûé ïîëíîìó äâóäîëüíîìó ãðàôó K3,3 . Äîêàçàòåëüñòâî. Ïîëíûé äâóäîëüíûé ãðàô K3,3 ìîæíî ðåàëèçîâàòü íà ïëîñêîñòè â âèäå îêðóæíîñòè è òðåõ âíóòðåííèõ õîðä, ïîêàçàííûõ ïóíêòèðíîé ëèíèåé (ðèñ. 6,a). Íà ðèñ. 6,b ïðåäñòàâëåíî ïðåïÿòñòâèå V (r) ñ âûäåëåííûì, ãîìåîìîðôíûì K3,3 ïîäãðàôîì, äîñòàòî÷íî ðàññìîòðåòü ðåáðà êîòîðîãî èçîáðàæåíû æèðíûìè è ïóíêòèðíûìè ëèíèÿìè. Ðèñ. 6. Âûäåëåíèå ïîäãðàôà â Ëåììà äîêàçàíà. V (r), ãîìåîìîðôíîãî K3,3 f -ãðàô èç V (r), r ≥ 1, â ïëîñêîñòü íåâëîæèì. Òåì áîëåå íå ñóùåñòâóåò îðèåíòèðîâàííîãî âëîæåíèÿ V (r), r ≥ 1, â ïëîñêîñòü. Òàêèì îáðàçîì, f -ãðàô F íå ñîäåðæèò ïîä-f -ãðàôà, f -ãîìåîìîðôíîãî ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Íåîáõîäèìîñòü äîêàçàíà. Äîêàæåì äîñòàòî÷íîñòü. Ïóñòü f -ãðàô F àòîìà íå ñîäåðæèò ïîä-f -ãðàôà, f -ãîìåîìîðôíîãî ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Ïîêàæåì, ÷òî F îðèåíòèÈç ëåììû 2 è òåîðåìû ÏîíòðÿãèíàÊóðàòîâñêîãî ñëåäóåò, ÷òî êàæäûé ñåðèè ðîâàííî âëîæèì â ïëîñêîñòü. Åñëè îðèåíòèðîâàííûé ãðàô ÿâëÿåòñÿ öèêëîì, âñå âåðøèíû êîòîðîãî ïîìå÷åíû áóê- ìå÷åíûì öèêëîì. Ïðè ýòîì áóêâû ìîãóò ïîâòîðÿòüñÿ. Ìå÷åíûé öèêë, ñîñòîÿùèé èç r âåðøèí, ýòî òî æå ñàìîå, ÷òî öèêëè÷åñêîå âàìè, òî íàçîâåì åãî îðèåíòèðîâàíûé 9

ñëîâî äëèíû r â àëôàâèòå X èç n, n ≤ r, áóêâ x1 , . . . , x n , â êîòîðîì áóêâû ìîãóò ïî- âòîðÿòüñÿ. Òàêèå ñëîâà ðàññìàòðèâàþòñÿ ñ òî÷íîñòüþ äî öèêëè÷åñêèõ ïåðåñòàíîâîê âõîäÿùèõ â íèõ áóêâ, ïðîèçâîëüíîé ïåðåíóìåðàöèè ïåðåìåííûõ x1 , . . . , x n è çàìåíû àëôàâèòà. Äàëåå ÷åðåç Sxi , xi ∈ X , áóäåì îáîçíà÷àòü ìíîæåñòâî âñåõ âåðøèí íà ìå÷åíîì îðèåíòèðîâàííîì öèêëå, ãäå Îïðåäåëåíèå. X àëôàâèò, à n xi , i = 1, 2, . . . , n, åãî ðàçìåð. Áóêâû a è b, ñîîòâåòñòâóþùèå íåêîòîðûì âåðøèíàì ìå÷åíîãî öèêçàöåïëåííûìè, åñëè ñóùåñòâóþò äâå ïàðû âåðøèí (a1 , a2 ) è (b1 , b2 ), ai ∈ Sa , bi ∈ Sb , i = 1, 2, êîòîðûå ìû âñòðå÷àåì ïîñëåäîâàòåëüíî (. . . a1 . . . b1 . . . a2 . . . b2 ) ïðè ëà, íàçîâåì öèêëè÷åñêîì îáõîäå. Îïðåäåëåíèå. Ìå÷åíûé îðèåíòèðîâàííûé öèêë íàçîâåì îñíàùàåìûì, åñëè ìíîæå- ñòâî åãî âåðøèí ìîæíî ðàçáèòü íà äâà êëàññà, ïðè÷åì áóêâû ëþáûõ äâóõ âåðøèí èç îäíîãî êëàññà íå çàöåïëåíû è âåðøèíû, îáîçíà÷åííûå îäíîé è òîé æå áóêâîé, ïðèíàäëåæàò îäíîìó êëàññó. Ôèêñèðîâàííîå ðàçáèåíèå íà äâà êëàññà íàçîâåì îñíàùåíèåì îðèåíòèðîâàííîãî öèêëà. Îïðåäåëåíèå. Õîðäîâîé äèàãðàììîé íàçîâåì ìå÷åíûé îðèåíòèðîâàííûé öèêë, â êî- òîðîì êàæäàÿ áóêâà âñòðå÷àåòñÿ ðîâíî äâà ðàçà. Îñíàùàåìóþ õîðäîâóþ äèàãðàììó íàçîâåì d-äèàãðàììîé. Çàìå÷àíèå. Õîðäîâóþ äèàãðàììó ìîæíî òàêæå ýêâèâàëåíòíî îïðåäåëèòü êàê f- ãðàô, ñîñòîÿùèé èç îäíîãî îðèåíòèðîâàííîãî öèêëà. Îïðåäåëåíèå. Ãðàôîì ïåðåñå÷åíèé Γ(O) ìå÷åíîãî îðèåíòèðîâàííîãî öèêëà O íàçî- âåì íåîðèåíòèðîâàííûé ãðàô, âåðøèíû êîòîðîãî (vi ) íàõîäÿòñÿ âî âçàèìíî-îäíîçíà÷íîì ñîîòâåòñòâèè ñ ìíîæåñòâàìè Sxi , i = 1, 2, . . . , n, è äâå âåðøèíû êîòîðîãî (vk è vl ) ñîåäè- íåíû ðåáðîì â òîì è òîëüêî òîì ñëó÷àå, êîãäà áóêâû ñîîòâåòñòâóþùèõ ìíîæåñòâ (Sxk Sxl ) çàöåïëåíû. Ãðàôîì ïåðåñå÷åíèé Γ(H) f -ãðàôà H , ñîñòîÿùåãî èç îäíîãî îðèåíòèðîâàííîãî öèêëà, áóäåì íàçûâàòü ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû, ñîîòâåòñòâóþùåé H . è Ñóùåñòâóåò ïîëíîå îïèñàíèå ãðàôîâ, ïðåäñòàâèìûõ êàê ãðàôû ïåðåñå÷åíèé õîðäîâûõ äèàãðàìì (ñì. [17]). Ãðàôû ïåðåñå÷åíèé ñîäåðæàò äîâîëüíî ìíîãî èíôîðìàöèè î ñâîèõ õîðäîâûõ äèàãðàììàõ. Ñ.Â. ×ìóòîâ, Ñ.Â. Äóæèí è Ñ.Ê. Ëàíäî âûäâèíóëè [18] ãèïîòåçó î òîì, ÷òî êëàññ ýêâèâàëåíòíîñòè õîðäîâûõ äèàãðàìì ìîæíî îïðåäåëèòü èõ ãðàôîì ïåðåñå÷åíèé; îíè äîêàçàëè ãèïîòåçó â ñëó÷àå, êîãäà ãðàô ïåðåñå÷åíèé ÿâëÿåòñÿ äåðåâîì. Â ñòàòüå [19] ãèïîòåçà áûëà äîêàçàíà äëÿ áîëåå îáùåãî ñëó÷àÿ, êîãäà ãðàô ïåðåñå÷åíèé Γ(H) õîðäîâîé äèàãðàììû Â ÷àñòíîñòè, âåðíî ñëåäóþùåå óòâåðæäåíèå: H óíèöèêëè÷åñêèé, ò.å. π1 (Ã(H)) = Z. f -ãðàôû, èìåþùèå îäèí îðèåíòèðîâàí- íûé öèêë (õîðäîâûå äèàãðàììû), èçîìîðôíû, åñëè èõ ãðàôû ïåðåñå÷åíèé ñîâïàäàþò è ïðåäñòàâëÿþò ñîáîé åäèíñòâåííûé öèêë. Îêîí÷àòåëüíî òî÷êó â îáñóæäåíèÿõ î ñâÿçè èíâàðèàíòíûõ õîðäîâûõ äèàãðàìì è èõ ãðàôîâ ïåðåñå÷åíèé ïîñòàâèëè Ñ.Â. ×ìóòîâ è Ñ.Ê. Ëàíäî â ñòàòüå [20]. Èññëåäóåì òåïåðü ìå÷åíûå îðèåíòèðîâàííûå öèêëû, èìåþùèå öèêëè÷åñêèé ãðàô ïåðåñå÷åíèé. Ëåììà 3. Ïóñòü ãðàô ïåðåñå÷åíèé íåêîòîðîãî ìå÷åíîãî îðèåíòèðîâàííîãî öèêëà O ïðåäñòàâëÿåò ñîáîé çàìêíóòûé öèêë K (èìåþùèé n ≥ 3 âåðøèí). Òîãäà èç êàæäîãî ìíîæåñòâà Sxi ìîæíî âûäåëèòü ïîäìíîæåñòâî Sx′ i , i = 1, 2, . . . , n, ñîñòîÿùåå èç äâóõ âåðøèí, òàêîå, ÷òî ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû, îáðàçîâàííîé èç S ′ = {Sx′ i }i=1,2,...,n , ñîâïàäàåò ñ K . Äîêàçàòåëüñòâî. Ìå÷åíûé îðèåíòèðîâàííûé öèêë O ñ k âåðøèíàìè èìååò ñëåäóþùóþ çàïèñü: (i1 i2 . . . ik ), ãäå âåðøèíû i1 , i2 , . . . , ik ðàñïîëîæåíû èìåííî â ýòîì ïîðÿäêå 10

ïðè öèêëè÷åñêîì îáõîäå. Òàêæå öèêë i1 , i2 , . . . , ik . O ìîæíî ïðåäñòàâèòü êàê îðèåíòèðîâàííóþ îêðóæíîñòü ñ âåðøèíàìè Ïóñòü a, b, d1 , d2 d1 è d2 ðàçáèâàþò îêðóæíîñòü. Ïóñòü Z íåêîòîðûå âåðøèíû öèêëà ëåæàò íà ðàçíûõ äóãàõ, íà êîòîðûå âåðøèíû a è b O, ïðè÷åì âåðøèíû O. Äàëåå áóäåì ïèñàòü, Z îãðàíè÷åíû íà öèêëå O âåðøèíàìè a è b (ñîîòâåòñòâåííî a è d1 ) â âèäå (a . . . z . . . d1 . . . b . . . d2 . . . ), åñëè êàæäàÿ âåðøèíà z ìíîæåñòâà Z ëåæèò íà äóãå îêðóæíîñòè, îãðàíè÷åííîé a è b è ñîäåðæàùåé âåðøèíó d1 (ñîîòâåòñòâåííî íà äóãå îêðóæíîñòè, îãðàíè÷åííîé a è d1 ). Áóäåì äîêàçûâàòü èíäóêöèåé ïî n êîëè÷åñòâó âåðøèí K = Γ(O). Áàçà èíäóêöèè. Ïóñòü n = 3 è âåðøèíû öèêëà O îáîçíà÷åíû áóêâàìè a, b, c. Òîãäà ãðàô ïåðåñå÷åíèé Γ(O) öèêëà O ïðåäñòàâëÿåò ñîáîé çàìêíóòûé öèêë, èìåþùèé òðè âåðøèíû va , vb , vc , ò.å. òðåóãîëüíèê. Êàê è âûøå, îáîçíà÷èì ÷åðåç Sa (ñîîòâåòñòâåííî Sb , Sc ) ìíîæåñòâî âñåõ âåðøèí öèêëà O ñ îäèíàêîâûìè áóêâàìè a (ñîîòâåòñòâåííî b, c), ïðè÷åì âåðøèíå va (ñîîòâåòñòâåííî vb , vc ) ñîîòâåòñòâóåò ìíîæåñòâî Sa (ñîîòâåòñòâåííî Sb , Sc ). Âåðøèíû va è vb ãðàôà ïåðåñå÷åíèé ñîåäèíåíû ðåáðîì, ñëåäîâàòåëüíî, ñóùåñòâóþò äâå ïàðû âåðøèí (a1 , a2 ) è (b1 , b2 ), ai ∈ Sa , bi ∈ Sb , i = 1, 2, ðàñïîëîæåííûõ íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (a1 . . . b1 . . . a2 . . . b2 . . . ). Ðàçáåðåì âñå ñëó÷àè ðàñïîëîæåíèÿ âåðøèí èç ìíîæåñòâà Sc íà öèêëå O . Åñëè ñóùåñòâóåò ïàðà (c1 , c2 ), ðàñïîëîæåííàÿ íà öèêëå O â ïîñëåäîâàòåëüíîñòè (a1 . . . b1 . . . c1 . . . a2 . . . b2 . . . c2 . . . ) èëè (a1 . . . c1 . . . b1 . . . a2 . . . c2 . . . b2 . . . ), òî óòâåðæäåíèå ëåììû ïðè n = 3 äîêàçàíî (ãðàô ïåðåñå÷åíèé êàæäîé èç õîðäîâûõ äèàãðàìì (a1 b1 c1 a2 b2 c2 ) è (a1 c1 b1 a2 c2 b2 ) ïðåäñòàâëÿåò ñîáîé òðåóãîëüíèê). ïðîèçâîëüíîå íåïóñòîå ïîäìíîæåñòâî ìíîæåñòâà âåðøèí öèêëà ÷òî âåðøèíû ìíîæåñòâà Îñòàëîñü ðàññìîòðåòü ñëåäóþùèå ñëó÷àè. a1 è b1 â âèäå (a1 . . . c . . . b1 . . . a2 . . . b2 . . . ). b1 è a2 â âèäå (a1 . . . b1 . . . c . . . a2 . . . b2 . . . ). 3. Âåðøèíû ìíîæåñòâà îãðàíè÷åíû a2 è b2 â âèäå (a1 . . . b1 . . . a2 . . . c . . . b2 . . . ). 4. Âåðøèíû ìíîæåñòâà îãðàíè÷åíû b2 è a1 â âèäå (a1 . . . b1 . . . a2 . . . b2 . . . c . . . ). 5. Âåðøèíû ìíîæåñòâà îãðàíè÷åíû a1 è a2 , ïðè÷åì âåðøèíà b1 ïðèíàäëåæèò òîé æå äóãå, ÷òî è âåðøèíû ìíîæåñòâà Sc , à òàêæå ñóùåñòâóåò ïàðà (c1 , c2 ), ðàñïîëîæåííàÿ íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (a1 . . . c1 . . . b1 . . . c2 . . . a2 . . . b2 . . . ). 6. Âåðøèíû ìíîæåñòâà Sc îãðàíè÷åíû b1 è b2 , ïðè÷åì âåðøèíà a2 ïðèíàäëåæèò òîé æå äóãå, ÷òî è âåðøèíû ìíîæåñòâà Sc , à òàêæå ñóùåñòâóåò ïàðà (c1 , c2 ), ðàñïîëîæåííàÿ íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (a1 . . . b1 . . . c1 . . . a2 . . . c2 . . . b2 . . . ). 7. Âåðøèíû ìíîæåñòâà Sc îãðàíè÷åíû a2 è a1 , ïðè÷åì âåðøèíà b2 ïðèíàäëåæèò òîé æå äóãå, ÷òî è âåðøèíû ìíîæåñòâà Sc , à òàêæå ñóùåñòâóåò ïàðà (c1 , c2 ), ðàñïîëîæåííàÿ íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (a1 . . . b1 . . . a2 . . . c1 . . . b2 . . . c2 . . . ). 8. Âñå âåðøèíû èç ìíîæåñòâà Sc ðàñïîëîæåíû ìåæäó b1 è b2 , ïðè÷åì âåðøèíà a1 ïðèíàäëåæèò òîé æå äóãå, ÷òî è âåðøèíû ìíîæåñòâà Sc , à òàêæå ñóùåñòâóåò ïàðà (c1 , c2 ), ðàñïîëîæåííàÿ íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (a1 . . . c2 . . . b1 . . . a2 . . . b2 . . . c1 . . . ). Îñòàíîâèìñÿ íà ñëó÷àå 1 (ñëó÷àè 24 àíàëîãè÷íû). Âåðøèíû va è vc ãðàôà ïåðåñå÷åíèé Γ(O) ñîåäèíåíû ðåáðîì, ñëåäîâàòåëüíî, ñóùåñòâóþò ïàðà (c1 , c2 ) è áóêâà a3 , ðàñïîëîæåííûå â ïîñëåäîâàòåëüíîñòè (a1 . . . c1 . . . a3 . . . c2 . . . b1 . . . a2 . . . b2 . . . ). Äàëåå âåðøèíó a1 íà öèêëå O ðàññìàòðèâàòü íå áóäåì. Òîãäà (ò.å. åñëè ïîìåíÿòü îáîçíà÷åíèå âåðøèíû a3 íà a1 ) ìû ïðèøëè ê ñëó÷àþ 8 (ñëó÷àè 57 àíàëîãè÷íû ñëó÷àþ 8). Òàê êàê âåðøèíû vc è vb ãðàôà ïåðåñå÷åíèé Γ(O) ñîåäèíåíû ðåáðîì, òî âîçìîæíû 1. Âåðøèíû ìíîæåñòâà 2. Âåðøèíû ìíîæåñòâà Sc Sc Sc Sc Sc îãðàíè÷åíû îãðàíè÷åíû ñëåäóþùèå ïîäñëó÷àè. 11

1.1. Ñóùåñòâóåò âåðøèíà b3 , îãðàíè÷åííàÿ c1 è a3 : (a3 . . . c2 . . . b1 . . . a2 . . . b2 . . . c1 . . . b3 . . . ). Âûäåëèì èç ìíîæåñòâà Sa ïîäìíîæåñòâî {a2 , a3 }, èç Sb ïîäìíîæåñòâî {b1 , b3 }, èç Sc ïîäìíîæåñòâî {c1 , c2 }. Òîãäà ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû (a3 c2 b1 a2 c1 b3 ), îáðàçîâàííîé èç óêàçàííûõ ïîäìíîæåñòâ, ïðåäñòàâëÿåò ñîáîé òðåóãîëüíèê. 1.2. Ñóùåñòâóåò âåðøèíà b3 , îãðàíè÷åííàÿ a3 è c2 â âèäå (a3 . . . b3 . . . c2 . . . b1 . . . a2 . . . b2 . . . c1 . . . ). Âûäåëèì èç ìíîæåñòâà Sa ïîäìíîæåñòâî {a2 , a3 }, èç Sb ïîäìíîæåñòâî {b2 , b3 }, èç Sc ïîäìíîæåñòâî {c1 , c2 }. Òîãäà ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû (a3 b3 c2 a2 b2 c1 ), îáðàçîâàííîé èç óêàçàííûõ ïîäìíîæåñòâ, ïðåäñòàâëÿåò ñîáîé òðåóãîëüíèê. 1.3. Ñóùåñòâóþò âåðøèíû b3 è c3 , îãðàíè÷åííûå c2 è b1 â âèäå (a3 . . . c2 . . . b3 . . . c3 . . . b1 . . . {a2 , a3 }, èç Sb ïîäìíî- a2 . . . b2 . . . c1 . . . ). Âûäåëèì èç ìíîæåñòâà Sa ïîäìíîæåñòâî æåñòâî {b2 , b3 }, èç Sc ïîäìíîæåñòâî {c1 , c3 }. Òîãäà ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû (a3 b3 c3 a2 b2 c1 ), îáðàçîâàííîé èç óêàçàííûõ ïîäìíîæåñòâ, ïðåäñòàâëÿåò ñîáîé òðåóãîëüíèê. 1.4. Ñóùåñòâóþò âåðøèíû b3 è c3 , îãðàíè÷åííûå b2 è c1 â âèäå (a3 . . . c2 . . . b1 . . . a2 . . . b2 . . . {a2 , a3 }, èç Sb ïîäìíîæå- c3 . . . b3 . . . c1 . . . ). Âûäåëèì èç ìíîæåñòâà Sa ïîäìíîæåñòâî ñòâî {b1 , b3 }, èç Sc ïîäìíîæåñòâî {c2 , c3 }. Òîãäà ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû (a3 c2 b1 a2 c3 b3 ), îáðàçîâàííîé èç óêàçàííûõ ïîäìíîæåñòâ, ïðåäñòàâëÿåò ñîáîé òðåóãîëüíèê. Ïóñòü íå ñóùåñòâóåò âåðøèíû èç ìíîæåñòâà b2 è ñîäåðæàùåé âåðøèíó ìíîæåñòâà Sb a3 . Sb , ëåæàùåé íà äóãå, îãðàíè÷åííîé b1 è Òîãäà äóãà îêðóæíîñòè, íà êîòîðîé ëåæàò âñå âåðøèíû íå ïåðåñåêàåòñÿ ñ äóãîé, íà êîòîðîé ëåæàò âñå âåðøèíû ìíîæåñòâà Sc . vc è vb ãðàôà ïåðåñå÷åíèé Γ(O) ñîåäèíåíû ðåáðîì. Òàêèì îáðàçîì, óòâåðæåíèå ëåììû ïðè n = 3 ïîëíîñòüþ äîêàçàíî. Øàã èíäóêöèè. Ïðåäïîëîæèì, ÷òî óòâåðæäåíèå ëåììû âåðíî ïðè n = k, k ≥ 3. Äîêàæåì, ÷òî îíî âåðíî ïðè n = k + 1. Ïóñòü âåðøèíû öèêëà O ïîìå÷åíû áóêâàìè a, b, c, d è ò.ä. Òîãäà ãðàô ïåðåñå÷åíèé Γ(O) ïðåäñòàâëÿåò ñîáîé çàìêíóòûé öèêë, èìåþùèé k + 1 âåðøèíó va , vb , vc , vd è ò.ä. Íå îãðàíè÷èâàÿ îáùíîñòè, ïîëàãàåì, ÷òî âåðøèíà va ñîåäèíåíà ðåáðîì ñ vd è vb , à âåðøèíà vb ñîåäèíåíà ðåáðîì ñ va è vc . Êàê è âûøå, îáîçíà÷èì ÷åðåç Sa (ñîîòâåòñòâåííî Sb , Sc , Sd ) ìíîæåñòâî âñåõ âåðøèí öèêëà O ñ îäèíàêîâûìè áóêâàìè a (ñîîòâåòñòâåííî b, c, d), ïðè÷åì âåðøèíå va ( ñîîòâåòñòâåííî vb , vc , vd ) ñîîòâåòñòâóåò ìíîæåñòâî Sa (ñîîòâåòñòâåííî Sb , Sc , Sd ). Òåïåðü îáîçíà÷èì áóêâó b áóêâîé a, ïîëó÷èì ′ ′ öèêë O . ×åðåç Sa′ áóäåì îáîçíà÷àòü ìíîæåñòâî âñåõ âåðøèí öèêëà O , ïîìå÷åííûõ ′ ′ áóêâîé a. Òîãäà ãðàô ïåðåñå÷åíèé Γ(O ) öèêëà O ïðåäñòàâëÿåò ñîáîé çàìêíóòûé öèêë, ′ èìåþùèé k âåðøèí va , vc , vd è äð., è äëÿ Γ(O ) âûïîëíÿåòñÿ óòâåðæäåíèå ëåììû ïî ′ ′ ïðåäïîëîæåíèþ èíäóêöèè. Òî åñòü ñóùåñòâóþò äâóõýëåìåíòíûå ïîäìíîæåñòâà Sa , Sc , ′ Sd , . . . ìíîæåñòâ Sa′ , Sc , Sd , . . . ñîîòâåòñòâåííî, òàêèå, ÷òî ãðàô ïåðåñå÷åíèé õîðäîâîé ′ ′ ′ ′ ′ äèàãðàììû, îáðàçîâàííîé èç S = {Sa , Sc , Sd , . . . }, ñîâïàäàåò ñ Γ(O ). Ðàññìîòðèì äâà Ýòî íåâîçìîæíî, ïîñêîëüêó âåðøèíû ñëó÷àÿ. vc è vd Γ(O′ ) k = 3 è Γ(O) ïðåäñòàâëÿåò ñîáîé ÷åòûðåõóãîëüíèê. Òîãäà ñóùåñòâóþò ai1 , ai2 èç ìíîæåñòâà Sa′ , c1 , c2 ′ èç ìíîæåñòâà Sc , d1 , d2 èç ìíîæåñòâà Sd , ðàñïîëîæåííûå íà öèêëå O â öèêëè÷åñêîì ïîðÿäêå (ai1 . . . d1 . . . c1 . . . ai2 . . . d2 . . . c2 . . . ). Âåðíåì èñõîäíîå áóêâåííîå îáîçíà÷åíèå âñåì ′ âåðøèíàì íà öèêëå O . Ïîñêîëüêó â ãðàôå Γ(O) âåðøèíà va íå ñîåäèíåíà ñ vc , à vb c vd , òî âåðøèíû ai1 , ai2 íå ìîãóò îäíîâðåìåííî ïðèíàäëåæàòü ìíîæåñòâó Sa (èëè Sb ). Ðàññìîòðèì ñëó÷àé, êîãäà âåðøèíà ai1 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sa , îáîçíà÷èì åå a1 , à ai2 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sb , îáîçíà÷èì åå b1 . Ñëó÷àé, êîãäà ai1 ÿâëÿåòñÿ ýëåìåíòîì Sb , à ai2 ýëåìåíòîì Sa , ðàññìàòðèâàåòñÿ àíàëîãè÷íî. Òàê êàê va íå ñîåäèíåíà ðåáðîì ñ vc , òî êàæäàÿ âåðøèíà a èç ìíîæåñòâà Sa îãðàíè÷åíà c1 è Ñëó÷àé 1. Ïóñòü âåðøèíû ãðàôà 12 ñîåäèíåíû ðåáðîì, ò.å.

c2 (c2 . . . a . . . c1 . . . b1 . . . d2 . . . ). Òàêæå êàæäàÿ âåðøèíà b èç ìíîæåñòâà Sb îãðàíè÷åíà d1 è d2 â âèäå (c2 . . . a1 . . . d1 . . . b . . . d2 . . . ). Òàê êàê va ñîåäèíåíà ðåáðîì ñ vb â ãðàôå Γ(O), çàêëþ÷àåì, ÷òî ñóùåñòâóþò a2 èç ìíîæåñòâà Sa è b2 èç ìíîæåñòâà Sb , îãðàíè÷åííûå c1 è d1 â âèäå (c2 . . . a1 . . . d1 . . . b2 . . . a2 . . . c1 . . . b1 . . . d2 . . . ). Òàêèì îáðàçîì, èç ìíîæåñòâà Sa âûäåëÿåòñÿ ïîäìíîæåñòâî {a1 , a2 }, èç Sb ïîäìíîæåñòâî {b1 , b2 }, èç Sc ïîäìíîæåñòâî {c1 , c2 }, èç Sd ïîäìíîæåñòâî {d1 , d2 }. Òîãäà ãðàô ïåðåñå÷åíèé õîðäîâîé äèàãðàììû (c2 a1 d1 b2 a2 c1 b1 d2 ), îáðàçîâàííîé èç óêàçàííûõ ïîäìíîæåñòâ, ïðåäñòàâëÿåò â âèäå ñîáîé ÷åòûðåõóãîëüíèê. vd ãðàôà Γ(O′ ) íå ñîåäèíåíû ðåáðîì, ò.å. k ≥ 4. Òîãäà ñóùåñòâóþò ai1 , ai2 èç ìíîæåñòâà Sa′ ; c1 , c2 èç ìíîæåñòâà Sc ; d1 , d2 èç ìíîæåñòâà Sd , ′ ðàñïîëîæåííûå íà öèêëå O â öèêëè÷åñêîì ïîðÿäêå (c1 . . . ai1 . . . c2 . . . d1 . . . ai2 . . . d2 . . . ). ′ Âåðíåì èñõîäíîå áóêâåííîå îáîçíà÷åíèå âñåì âåðøèíàì íà öèêëå O . Ïîñêîëüêó â ãðàôå Γ(O) âåðøèíà va íå ñîåäèíåíà ñ vc , à vb c vd , òî âåðøèíû ai1 , ai2 íå ìîãóò îäíîâðåìåííî ïðèíàäëåæàòü ìíîæåñòâó Sa (èëè Sb ). Òîãäà âîçìîæíû ñëåäóþùèå ïîäñëó÷àè. Ïîäñëó÷àé 2.1. Âåðøèíà ai1 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sa , îáîçíà÷èì åå a, à ai2 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sb , îáîçíà÷èì åå b1 . Òàê êàê âåðøèíà va íå ñîåäèíåíà ðåáðîì ñ vc â ãðàôå Γ(O), òî âåðøèíû ìíîæåñòâà Sa îãðàíè÷åíû c1 è c2 â âèäå (c1 . . . a . . . c2 . . . d1 . . . b1 . . . d2 . . . ). Òàê êàê va ñîåäèíåíà ðåáðîì ñ vb â ãðàôå Γ(O), òî ñóùåñòâóþò âåðøèíû a1 , a2 èç ìíîæåñòâà Sa è b2 èç ìíîæåñòâà Sb , ðàñïîëîæåííûå íà öèêëå O â öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè (c1 . . . a1 . . . b2 . . . a2 . . . c2 . . . d1 . . . b1 . . . d2 . . . ). Íî òàêîå ðàñïîëîæåíèå ïðîòèâîðå÷èò òîìó, ÷òî vb íå ñîåäèíåíà ñ vd â ãðàôå Γ(O). Ïîäñëó÷àé 2.2. Âåðøèíà ai1 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sb , îáîçíà÷èì åå b1 , à ai2 ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà Sa , îáîçíà÷èì åå a1 . Çàìåòèì, ÷òî òàê êàê va íå ñîåäèíåíà ðåáðîì ñ vc , òî íå ñóùåñòâóåò âåðøèíû a èç ìíîæåñòâà Sa , îãðàíè÷åííîé c1 è c2 â âèäå (c1 . . . a . . . c2 . . . d1 . . . a1 . . . d2 . . . ). Òàêæå çàìåòèì, ÷òî íå ñóùåñòâóåò âåðøèíû b èç ìíîæåñòâà Sb , îãðàíè÷åííîé d1 è d2 â âèäå (c1 . . . b1 . . . c2 . . . d1 . . . b . . . d2 . . . ). Ó÷èòûâàÿ ýòè çàìå÷àíèÿ è òî, ÷òî va ñîåäèíåíà ðåáðîì ñ vb â ãðàôå Γ(O), çàêëþ÷àåì, ÷òî ñóùåñòâóåò a2 èç ìíîæåñòâà Sa è b2 èç ìíîæåñòâà Sb , îãðàíè÷åííûå c2 è d1 (èëè d2 è c1 ) â âèäå (c1 . . . b1 . . . c2 . . . a2 . . . b2 . . . d1 . . . a1 . . . d2 . . . ) (ñîîòâåòñòâåííî â âèäå (c1 . . . b1 . . . c2 . . . d1 . . . a1 . . . d2 . . . b2 . . . a2 . . . )). Ðàññìîòðèì ãðàô ïåðåñå÷åíèé Γ(U ) õîðäîâîé äèàãðàììû U , îáðàçîâàííîé èç {a1 , a2 }, {b1 , b2 }, S ′ \ Sa′ . Âåðøèíà ãðàôà Γ(U ), ñîîòâåòñòâóþùàÿ ìíîæåñòâó {a1 , a2 }, ñîåäèíåíà òîëüêî ñ äâóìÿ âåðøèíàìè, îäíà èç êîòîðûõ ñîîòâåòñòâóåò ìíîæåñòâó {b1 , b2 }, à äðóãàÿ ′ ìíîæåñòâó Sd . Âåðøèíà ãðàôà Γ(U ), ñîîòâåòñòâóþùàÿ ìíîæåñòâó {b1 , b2 }, ñîåäèíåíà òàêæå òîëüêî ñ äâóìÿ âåðøèíàìè, îäíà èç êîòîðûõ ñîîòâåòñòâóåò ìíîæåñòâó {a1 , a2 }, à ′ äðóãàÿ ìíîæåñòâó Sc . Âåðøèíû ãðàôà Γ(U ), ñîîòâåòñòâóþùèå ýëåìåíòàì ìíîæåñòâà S ′ \ Sa′ , èìåþò ñòåïåíü äâà. Òàêèì îáðàçîì, Γ(U ) ñîâïàäàåò ñ Γ(O). Ëåììà äîêàçàíà. Îòìåòèì, ÷òî óòâåðæäåíèå ëåììû 3 ïåðåñòàåò áûòü âåðíûì, åñëè ãðàô K íå ÿâëÿåòñÿ e: çàìêíóòûì öèêëîì. Ïðèìåðîì ñëóæèò ñëåäóþùèé ìå÷åíûé îðèåíòèðîâàííûé öèêë O e (d1 , a1 , c1 , d2 , a2 , c2 , b1 , a3 , b2 ). Åãî ãðàô ïåðåñå÷åíèé Γ(O) íå ÿâëÿåòñÿ çàìêíóòûì öèêëîì. Êàæäîå èç ìíîæåñòâ Sb , Sc , Sd ñîñòîèò èç äâóõ âåðøèí, à ìíîæåñòâî Sa ñîñòîèò èç òðåõ. Âûäåëèòü äâå âåðøèíû èç ìíîæåñòâà Sa ìîæíî òðåìÿ ñïîñîáàìè. Ãðàô ïåðåñå÷åíèé êàæäîãî èç ñëåäóþùèõ òðåõ îðèåíòèðîâàííûõ öèêëîâ (d1 , a1 , c1 , d2 , c2 , b1 , b2 ), e . (d1 , c1 , d2 , a2 , c2 , b1 , b2 ), (d1 , c1 , d2 , c2 , b1 , a3 , b2 ) íå ñîâïàäàåò ñ Γ(O) Îïèøåì ïðîöåäóðó ñíàáæåíèÿ âåðøèí ïðîèçâîëüíîãî f -ãðàôà áóêâàìè. Äëÿ êàæäîé îêðóæíîñòè A f -ãðàôà ñäåëàåì ñëåäóþùåå. Ðàçíûìè áóêâàìè ïîìåòèì âñå âíóòðåííèå õîðäû îêðóæíîñòè A. Êîíöàì êàæäîé õîðäû ïðèïèøåì òó æå áóêâó, ÷òî è ó õîðäû. Åñëè íà îêðóæíîñòè A îñòàëèñü âåðøèíû, íå ïîìå÷åííûå áóêâàìè, òî Ñëó÷àé 2. Ïóñòü âåðøèíû vc è 13

A âìåñòå ñ âíóòðåííèìè õîðäàìè êîòîðûõ ïðèíàäëåæèò A, f -ãðàô ðàç- ïîñòóïèì òàêèì îáðàçîì. Ïîñëå óäàëåíèÿ îêðóæíîñòè è âåðøèíàìè âíåøíèõ õîðä, õîòÿ áû îäèí êîíåö áèâàåòñÿ íà m≥1 íåïóñòûõ ñâÿçíûõ êîìïîíåíò. Îáîçíà÷èì ýòè êîìïîíåíòû ðàçíûìè áóêâàìè (ïðè ýòîì îáîçíà÷åíèÿ âíóòðåííèõ õîðä è êîìïîíåíò äîëæíû áûòü ïîïàðíî ðàçíûìè). Òåïåðü äëÿ êàæäîé êîìïîíåíòû ñäåëàåì ñëåäóþùåå. Îäíà êîìïîíåíòà ñîåäèíåíà ñ îêðóæíîñòüþ A ðåáðàìè. Ïîìåòèì âåðøèíû ýòèõ ðåáåð íà îêðóæíîñòè òîé æå áóêâîé, ÷òî è ó êîìïîíåíòû. Â êîíå÷íîì èòîãå ïîëó÷èì èç A A îêðóæíîñòü, âñå âåðøèíû êîòîðîé îáîçíà÷åíû áóêâàìè. f -Ãðàô íàçîâåì ìå÷åíûì, åñëè âñå åãî âåðøèíû ïîìå÷åíû áóêâàìè óêàçàííûì îáðàçîì (âîîáùå ãîâîðÿ, íåîäíîçíà÷íûì, òàê êàê ìåòêè íà âåðøèíàõ ðàçíûõ îêðóæíîñòåé ââîäÿòñÿ íåçàâèñèìî äðóã îò äðóãà, ò.å. ìîãóò ïîâòîðÿòüñÿ ó ðàçíûõ îêðóæíîñòåé). Äàëåå áóäåì ðàññìàòðèâàòü òîëüêî ìå÷åíûå f -ãðàôû. Ëåììà 4. Åñëè f -ãðàô íå ñîäåðæèò ïîä-f -ãðàôà, f -ãîìåîìîðôíîãî ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1, òî êàæäûé åãî ìå÷åíûé îðèåíòèðîâàííûé öèêë îñíàùàåì. Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíûé îðèåíòèðîâàííûé öèêë A f -ãðàôà è ïîñòðîèì ãðàô ïåðåñå÷åíèé Γ(A). Ïðåäïîëîæèì, ÷òî Γ(A) ñîäåðæèò öèêë íå÷åòíîé äëèíû. Åñëè öèêëîâ íåñêîëüêî, âûáåðåì ñðåäè íèõ íàèìåíüøèé ïî ÷èñëó çâåíüåâ è âûäåëèì åãî â ãðàôå ïåðåñå÷åíèé. Γ(A) íå ñóùåñòâóåò ðåáðà, ñîåäèíÿþùåãî äâå íåñìåæíûå âåðøèíû âûöèêëà C (èíà÷å ïîëó÷èì, ÷òî ñóùåñòâóåò öèêë íå÷åòíîé äëèíû â Γ(A), ó Çàìåòèì, ÷òî â äåëåííîãî êîòîðîãî çâåíüåâ ìåíüøå). Òåïåðü áóäåì ðàññìàòðèâàòü òîëüêî òå ìíîæåñòâà âåðøèí ñ C . Ïî ëåììå 2 èç êàæäîãî ìíîæåñòâà Sxi (ñîîòâåòñòâóþùåãî íåêîòîðîé âåðøèíå öèêëà C ) ìîæíî ′ âûäåëèòü ïîäìíîæåñòâî Sx , i = 1, 2, . . . , r , ñîñòîÿùåå èç äâóõ âåðøèí, òàêîå, ÷òî ãðàô i ′ ′ ïåðåñå÷åíèé õîðäîâîé äèàãðàììû, îáðàçîâàííîé èç S = {Sx }i=1,2...,r , ñîâïàäàåò ñ C . Ýòî i îçíà÷àåò, ÷òî â ñàìîì f -ãðàôå ñóùåñòâóåò ïîä-f -ãðàô, f -ãîìåîìîðôíûé ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Ïðîòèâîðå÷èå ñ óñëîâèåì ëåììû. Èòàê, ãðàô ïåðåñå÷åíèé Γ(A) íå ñîäåðæèò öèêëà íå÷åòíîé äëèíû. À çíà÷èò, ÿâëÿåòñÿ äâóäîëüíûì. Òî åñòü ìíîæåñòâî âåðøèí ãðàôà Γ(A) ìîæíî ðàçáèòü íà äâà êëàññà òàêèì îäèíàêîâûìè áóêâàìè íà öèêëå A, êîòîðûì ñîîòâåòñòâóþò âåðøèíû öèêëà îáðàçîì, ÷òî êàæäîå ðåáðî ãðàôà ñîåäèíÿåò íåêîòîðóþ âåðøèíó èç îäíîãî êëàññà ñ Γ(A) íåêîòîðîé âåðøèíîé èç äðóãîãî êëàññà. Èç äâóäîëüíîñòè ñëåäóåò ñóùåñòâîâàíèå A. Ëåììà äîêàçàíà. Âåðíåìñÿ ê ðàññìîòðåíèþ f -ãðàôà F . Ïóñòü F ñîñòîèò èç îäíîãî îðèåíòèðîâàííîãî öèêëà A, êîòîðûé ïî ëåììå 4 îñíàùàåì (ò.å. öèêë A ÿâëÿåòñÿ d-äèàãðàììîé). Çàôèê- îñíàùåíèÿ îðèåíòèðîâàííîãî öèêëà ñèðóåì êàêîå-ëèáî îñíàùåíèå öèêëà è ðàññìîòðèì åãî ðåàëèçàöèþ íà ïëîñêîñòè áåç ñàìîïåðåñå÷åíèé. À èìåííî: çàìåòèì, ÷òî ëþáûå áóêâû èç îäíîãî êëàññà çàöåïëåííûìè íå ÿâëÿþòñÿ. Òîãäà âñå õîðäû f -ãðàôà F , êîíöû êîòîðûõ ëåæàò â îäíîì êëàññå, ìîæíî èçîáðàçèòü íà ïëîñêîñòè íåïåðåñåêàþùèìèñÿ êðèâîëèíåéíûìè îòðåçêàìè áåç ñàìîïåðåñå÷åíèé âíóòðè öèêëà. Àíàëîãè÷íî âñå õîðäû f -ãðàôà F , êîíöû êîòîðûõ ëåæàò â äðóãîì êëàññå, ìîæíî èçîáðàçèòü íà ïëîñêîñòè íåïåðåñåêàþùèìèñÿ è áåç ñàìîïåðåñå÷åíèé âíå öèêëà. Ïîëó÷èì îðèåíòèðîâàííîå âëîæåíèå Äàëåå áóäåì ñ÷èòàòü, ÷òî F ñîäåðæèò ℓ≥2 F â ïëîñêîñòü. îðèåíòèðîâàííûõ öèêëîâ. Çàôèêñèðóåì îñíàùåíèå íà êàæäîì îðèåíòèðîâàííîì öèêëå. Îäèí êëàññ èç îïðåäåëåíèÿ îñíàùåíèÿ ïîìåòèì ÷èñëîì 0, âòîðîé êëàññ ïîìåòèì 1. Òîãäà âñå âåðøèíû f -ãðàôà F 0 è 1. Õâîñòîì âåðøèíû ðàçáèâàþòñÿ íà êëàññû â f -ãðàôå íàçîâåì ïîëóðåáðî õîðäû ( ò.å. íåîðèåíòèðîâàííîãî âíåøíèì (âíóòðåííèì), åñëè îí ëåæèò íà âíåøíåé (ñîîòâåòñòâåííî âíóòðåííåé) õîðäå f -ãðàôà. Â ïðîèçâîëüíîì íåîðè- ðåáðà), ñîäåðæàùåå äàííóþ âåðøèíó. Õâîñò íàçîâåì 14

åíòèðîâàííîì ãðàôå ïîä õâîñòàìè âåðøèíû áóäåì ïîíèìàòü ñîäåðæàùèå åå ïîëóðåáðà. Çàìêíóòîé öåïüþ íàçîâåì f -ãðàô, ñîñòîÿùèé èç s ≥ 1 îðèåíòèðîâàííûõ öèêëîâ è s = 1 çàìêíóòàÿ öåïü ñîñòîèò èç öèêëè÷åñêè ñîåäèíÿþùèõ õîðä, êàê íà ðèñ. 7,a. Ïðè îäíîãî îðèåíòèðîâàííîãî öèêëà ñ âíóòðåííåé õîðäîé. Ïîñòðîèì äëÿ f -ãðàôà F äåðåâî T F åñòü çàìêíóðàçäåëèì åå: âûäåëèì ñëåäóþùèì îáðàçîì. Åñëè â ãðàôå òàÿ öåïü, òî âûáåðåì ïðîèçâîëüíóþ õîðäó, âõîäÿùóþ â öåïü, è íà õîðäå äâå âåðøèíû (ñì. ðèñ.7,b), îáîçíà÷èì èõ êðàñíûì öâåòîì, à ÷àñòü õîðäû, ñî- åäèíÿþùóþ êðàñíûå âåðøèíû, óäàëèì (ñì. ðèñ. 7,c). Ïîâòîðÿåì ïðåäûäóùèé øàã äëÿ ïîëó÷åííîãî ãðàôà, ïîêà íå ïîëó÷èì ãðàô, íå ñîäåðæàùèé çàìêíóòûõ öåïåé. Äàëåå êàæäûé îðèåíòèðîâàííûé öèêë ñòÿíåì â òî÷êó (ñì. ðèñ. 7,d). Ïîëó÷èì äåðåâî T, ïðè ýòîì äëÿ êàæäîé âåðøèíû äåðåâà åñòåñòâåííûì îáðàçîì îïðåäåëåí îðèåíòèðîâàííûé öèêëè÷åñêèé ïîðÿäîê åå õâîñòîâ. Äàëåå ïîä öèêëè÷åñêèì ïîðÿäêîì âåðøèíû äåðåâà áóäåì ïîíèìàòü îðèåíòèðîâàííûé öèêëè÷åñêèé ïîðÿäîê åå õâîñòîâ. Ðèñ. 7. Ðàçäåëåíèå õîðäû, âõîäÿùåé â çàìêíóòóþ öåïü F , òî òàout-èäåíòè÷íûìè ( ñîîòâåòñòâåííî in-èäåíòè÷íûìè). Áóäåì ãîèäåíòè÷íû, åñëè îíè ÿâëÿþòñÿ out-èäåíòè÷íûìè èëè in-èäåíòè÷- Åñëè äâå êðàñíûå âåðøèíû ëåæàëè íà îäíîé âíåøíåé (âíóòðåííåé) õîðäå â êèå âåðøèíû íàçîâåì âîðèòü, ÷òî âåðøèíû íûìè. Ëåììà 5. Ëþáîå äåðåâî ñ çàäàííûì öèêëè÷åñêèì ïîðÿäêîì åãî âåðøèí (ñì. âû- ìîæíî èçîáðàçèòü ñ ó÷åòîì ýòîãî ïîðÿäêà áåç ñàìîïåðåñå÷åíèé íà ïëîñêîñòè âíóòðè îêðóæíîñòè, ïðè÷åì âåðøèíû äåðåâà áóäóò ëåæàòü íà îêðóæíîñòè, à ðåáðà ïðåäñòàâëÿòü ñîáîé ïðÿìûå îòðåçêè. øå) Çàìå÷àíèå. Âëîæåíèå äåðåâà ñ ó÷åòîì öèêëè÷åñêîãî ïîðÿäêà åãî âåðøèí ñîñòîèò â ñëåäóþùåì. Îáîçíà÷èì ÷åðåç êàæäîé âåðøèíû v, v â U U óêàçàííóþ ðåàëèçàöèþ äåðåâà âíóòðè îêðóæíîñòè. Äëÿ îðèåíòèðîâàííûé öèêëè÷åñêèé ïîðÿäîê ïîëóðåáåð â âåðøèíå çàäàâàåìûé âëîæåíèåì è îðèåíòàöèåé ïîëóðåáåð ïðîòèâ ÷àñîâîé ñòðåëêè, äîëæåí ñîâïàäàòü ñ öèêëè÷åñêèì ïîðÿäêîì äåðåâà â âåðøèíå Äîêàçàòåëüñòâî. Èíäóêöèÿ ïî N v. ÷èñëó âåðøèí äåðåâà. Ïðè N = 2 (ò.å. äëÿ ïðîñòîãî ðåáðà) óòâåðæäåíèå ëåììû î÷åâèäíî. Ïóñòü ëåììà âåðíà ïðè N = κ. Ðàññìîòðèì äåðåâî ñ N = κ+1 ÷èñëîì âåðøèí. Â ëþáîì äåðåâå ñóùåñòâóåò âèñÿ÷àÿ âåðøèíà (ò.å. âåðøèíà ñòåïåíè 1). Âûäåëèì ðåáðî â íàøåì äåðåâå, êîòîðîìó ïðèíàäëåæèò âèñÿ÷àÿ âåðøèíà, è îáîçíà÷èì áóêâîé êîíåö ðåáðà, îòëè÷íóþ îò âèñÿ÷åé. Î÷åâèäíî, ÷òî ñòåïåíü âåðøèíû l l âåðøèíó- áîëüøå èëè ðàâíà äâóì. Óäàëèì âèñÿ÷óþ âåðøèíó. Ïîëó÷èòñÿ äåðåâî ñ N = κ âåðøèíàìè, êîòîðîå ìîæíî âëîæèòü â ïëîñêîñòü óêàçàííûì îáðàçîì. Ðàññìîòðèì òàêîå âëîæåíèå. Îáîçíà÷èì ÷åðåç X ìíîæåñòâî çàìêíóòûõ ñâÿçíûõ îáëàñòåé, íà êîòîðûå îêðóæíîñòü è âëîæåííîå â 15

íåãî äåðåâî ðàçáèâàþò ïëîñêîñòü. Îòìåòèì, ÷òî âñå ýëåìåíòû ìíîæåñòâà X ÿâëÿþòñÿ âûïóêëûìè. 1. Ðàññìîòðèì ñëó÷àé, êîãäà âåðøèíà l ïîñëå óäàëåíèÿ âèñÿ÷åé âåðøèíû ñòàëà âèñÿ- ÷åé. Ïîñêîëüêó â äåðåâå íåò öèêëîâ, òî ñóùåñòâóåò çàìêíóòàÿ îáëàñòü, êîòîðàÿ ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà ðåáðî ñ êîíöîì l, X è ãðàíèöåé êîòîðîé ÿâëÿþòñÿ ðåáðà äåðåâà, â òîì ÷èñëå è íåêîòîðàÿ äóãà îêðóæíîñòè. Ñîåäèíèì îòðåçêîì ïðîèçâîëüíóþ âíóòðåííþþ òî÷êó äóãè è âåðøèíó l. Î÷åâèäíî, ýòîò îòðåçîê áóäåò íàõîäèòüñÿ âíóò- ðè îáëàñòè, à çíà÷èò, íå áóäåò ïåðåñåêàòüñÿ ñ äðóãèìè îòðåçêàìè. Ïîëó÷èì èñêîìîå âëîæåíèå â ïëîñêîñòü äåðåâà ñ N =κ+1 ÷èñëîì âåðøèí. 2. Òåïåðü ðàññìîòðèì ñëó÷àé, êîãäà ñòåïåíü âåðøèíû l äî óäàëåíèÿ âèñÿ÷åé âåðøèíû áûëà áîëüøå äâóõ. Òîãäà ñóùåñòâóþò äâà ðåáðà: îäíî ïðåäøåñòâóåò óäàëåííîìó, äðóãîå ïîñëåäóåò çà óäàëåííûì â ñîîòâåòñòâèè ñ öèêëè÷åñêèì ïîðÿäêîì âåðøèíû l . Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò îáëàñòü ýëåìåíò ìíîæåñòâà X, â ãðàíèöó êîòîðîé âõîäÿò ïðåäøåñòâóþùåå è ïîñëåäóþùåå ðåáðà. Ïîñêîëüêó â äåðåâå íåò öèêëîâ, â ãðàíèöó ýòîé îáëàñòè âõîäèò íåêîòîðàÿ äóãà îêðóæíîñòè, âíóòðåííþþ òî÷êó êîòîðîé ìîæíî ñîåäèíèòü îòðåçêîì ñ âåðøèíîé l , ÷òî äàñò èñêîìîå âëîæåíèå. Ïóñòü â ìíîæåñòâå X íå ñóùåñòâóåò çàìêíóòîé îáëàñòè ñ ãðàíèöåé, ñîäåðæàùåé ïðåä- øåñòâóþùåå è ïîñëåäóþùåå ðåáðà. Òîãäà ðàññìàòðèâàåì îáëàñòü, ãðàíèöåé êîòîðîé ÿâëÿþòñÿ ðåáðà äåðåâà, â òîì ÷èñëå ïðåäøåñòâóþùåå (èëè ïîñëåäóþùåå) ðåáðî. Äàííàÿ îáëàñòü àíàëîãè÷íà ðàññìîòðåííîé èç ï. 1. Îíà ñîäåðæèò â êà÷åñòâå ãðàíèöû íåêîòîðóþ äóãó îêðóæíîñòè. Ñîåäèíèâ îòðåçêîì ïðîèçâîëüíóþ âíóòðåííþþ òî÷êó äóãè è âåðøèíó l , â èòîãå ïîëó÷èì èñêîìîå âëîæåíèå. Ëåììà äîêàçàíà. Ïðåïÿòñòâèåì V 1 íàçîâåì ãðàô, ñîñòîÿùèé èç òðåõ ðåáåð Îïðåäåëåíèå. è äâóõ âåðøèí, íà êîòîðûõ çàäàí îðèåíòèðîâàííûé öèêëè÷åñêèé ïîðÿäîê: îäíîé âåðøèíå è òàêîé æå íà âòîðîé ( ðèñ. 6,a). T â ïëîñêîñòü; E îêðóæíîñòü, íà êîòîðîé ëåæàò âåðøèíû äåðåâà T1 . Åñëè äåðåâî T1 íå ñîäåðæèò êðàñíûõ âåðøèí, òî èñêîìîå âëîæåíèå f -ãðàôà F â ïëîñêîñòü ïîëó÷àåòñÿ èç T1 çàìåíîé êàæäîé âåðøèíû îðèåíòèðîâàííûì öèêëîì. Äàëåå ñ÷èòàåì, ÷òî äåðåâî T1 ñîäåðæèò êðàñíûå âåðøèíû. Ïîëó÷èì èç T1 ñâÿçíûé ãðàô G ñëåäóþùèì îáðàçîì: ñîåäèíèì ðåáðîì èäåíòè÷íûå âåðøèíû äåðåâà T1 . Îòìåòèì, ÷òî êàæäàÿ ïàðà èäåíòè÷íûõ âåðøèí â ãðàôå G ëåæèò Ïóñòü T1 l1 , l2 , l3 (l1 , l2 , l3 ) íà îïèñàííîå âëîæåíèå äåðåâà íà íåêîòîðîì öèêëå. Òàêæå ÿñíî, ÷òî ïðîèçâîëüíàÿ íå êðàñíàÿ âåðøèíà íà êàêîì-ëèáî öèêëå â G èìååò ëåæàùèå íà ýòîì öèêëå õâîñòû, êîòîðûå ïîìå÷åíû îäíîé áóêâîé è ïîýòîìó ïðèíàäëåæàò îäíîìó êëàññó. A, B, A1 , B1 äåðåâà T1 , ëåæàùèå íà E â ýòîì öèêëè÷åñêîì ïîðÿäêå, ïðè÷åì âåðøèíà A èäåíòè÷íà A1 , à âåðøèíà B èäåíòè÷íà B1 . Ñîåäèíèì A ñ A1 è B c B1 ïóòÿìè â äåðåâå T1 . Åñëè ýòè ïóòè â äåðåâå ïåðåñåêàþòñÿ ïî íåêîòîðîìó ïóòè u, òî â ãðàôå G âûäåëÿåòñÿ 1 1 ïðåïÿòñòâèå V . Âåðøèíàìè V áóäóò êîíöû u. Íà ðèñ. 8,b ïîêàçàí ïðèìåð, êàê âûäåëÿ1 åòñÿ ïðåïÿòñòâèå V â ãðàôå G. Ïóíêòèðîì îáîçíà÷åíà îêðóæíîñòü E . Ñóùåñòâîâàíèå 1 ïðåïÿòñòâèÿ V â ãðàôå G îçíà÷àåò, ÷òî èñõîäíûé f -ãðàô F ñîäåðæèò ïîä-f -ãðàô, f ãîìåîìîðôíûé ïðåïÿòñòâèþ V , à ýòî ïðîòèâîðå÷èò óñëîâèþ. Ñëåäîâàòåëüíî, ïóòè â äåðåâå T1 , ñîåäèíÿþùèå A ñ A1 è B c B1 , ïåðåñåêàþòñÿ ïî òî÷êå. Ýòó òî÷êó íàçîâåì òî÷êîé ïåðåñå÷åíèÿ è îáîçíà÷èì áóêâîé O. Ïóòü â äåðåâå, ñîåäèíÿþùèé A ñ A1 , áóäåì îáîçíà÷àòü ÷åðåç AA1 , à ñîåäèíÿþùèé B c B1 ÷åðåç BB1 . Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò ïóòü u1 â ãðàôå G, ñîåäèíÿþùèé AA1 è BB1 . È ýòîò ïóòü òî÷êó ïåðåñå÷åíèÿ íå ñîäåðæèò. Áóêâîé K (ñîîòâåòñòâåííî L) îáîçíà÷èì êîíåö ïóòè u1 , ëåæàùèé íà AA1 (ñîîòâåòñòâåííî íà BB1 ). ×åðåç k1 (ñîîòâåòñòâåííî l1 ) îáîÏóñòü ñóùåñòâóþò êðàñíûå âåðøèíû 16

L), ëåæàùèé íà ïóòè u1 . Ðàññìîòðèì äâà ïóòè γ1 , γ2 â ãðàôå G, ñîåäèíÿþùèå K è O : ïóòü γ1 ëåæèò íà BB1 è íå ñîäåðæèò B è B1 , ïóòü γ2 ïðîõîäèò ÷åðåç âåðøèíû B è B1 . ×åðåç k2 (ñîîòâåòñòâåííî k3 ) îáîçíà÷èì õâîñò âåðøèíû K , ëåæàùèé íà γ1 (ñîîòâåòñòâåííî γ2 ). Õâîñòû l2 è l3 âåðøèíû L îïðåäåëÿþòñÿ àíàëîãè÷íî õâîñòàì k2 è k3 . Õâîñòû ki è li , i ∈ {1, 2, 3}, ìîãóò ÷åòûðüìÿ ñïîñîáàìè îáðàçîâûâàòü öèêëè÷åñêèé ïîðÿäîê íà âåðøèíàõ K è L: 1) (k1 , k2 , k3 ) è (l1 , l3 , l2 ) (ðèñ. 8,c); 2) (k1 , k3 , k2 ) è (l1 , l3 , l2 ) (ðèñ. 8,d); 3) (k1 , k3 , k2 ) è (l1 , l2 , l3 ) (ðèñ. 8,e); 4) (k1 , k2 , k3 ) è (l1 , l2 , l3 ). ×åòâåðòûé ñëó÷àé àíàëîãè÷åí âòîðîìó. Íà ðèñ. 8,c,d,e ïóòü u1 èçîáðàæåí ïóíêòèðîì. 1 Âî âñåõ ÷åòûðåõ ñëó÷àÿõ â ãðàôå G âûäåëÿåòñÿ ïðåïÿòñòâèå V . Íà ðèñóíêå 8,f,g,h ðåáðà 1 1 ïðåïÿòñòâèÿ V âûäåëåíû æèðíûìè ïóíêòèðíûìè ëèíèÿìè, à âåðøèíàìè V ÿâëÿþòñÿ O è L. 1 Ñóùåñòâîâàíèå ïðåïÿòñòâèÿ V â ãðàôå G îçíà÷àåò, ÷òî èñõîäíûé f -ãðàô F ñîäåðæèò ïîä-f -ãðàô, f -ãîìåîìîðôíûé ïðåïÿòñòâèþ V , ÷òî ïðîòèâîðå÷èò óñëîâèþ. Òàêèì îáðàçîì, ïðè óäàëåíèè òî÷êè ïåðåñå÷åíèÿ èç ãðàôà G âåðøèíû A è B (òàêæå A1 è B1 ) íå ìîãóò ëåæàòü â îäíîé êîìïîíåíòå ñâÿçíîñòè. Òàêæå êëàññ õâîñòîâ òî÷êè ïåðåñå÷åíèÿ, ëåæàùèõ íà AA1 , îòëè÷àåòñÿ îò êëàññà õâîñòîâ ýòîé òî÷êè, ëåæàùèõ íà BB1 . Èíà÷å íà îðèåíòèðîâàííîì öèêëå â f -ãðàôå F , ñîîòâåòñòâóþùåì òî÷êå ïåðåñå÷åíèÿ, ñóùåñòâîâàëè áû äâå ïàðû âåðøèí (a1 , a2 ) è (b1 , b2 ), èäóùèõ ïî öèêëó â ïîðÿäêå (a1 b1 a2 b2 ) è ïðèíàäëåæàùèõ îäíîìó êëàññó. Ýòî ïðîòèâîðå÷èò ñóùåñòâîâàíèþ îñíàùåíèÿ êàæäîãî îðèåíòèðîâàííîãî öèêëà f -ãðàôà F . Çäåñü áóêâîé a (b) îáîçíà÷åíû õâîñòû òî÷êè ïåðåñå÷åíèÿ, ëåæàùèå íà AA1 (BB1 ) è ñîîòâåòñòâóþùèå õâîñòàì âåðøèíû íà îðèåíòèðîâàííîì öèêëå â f -ãðàôå F . Îòìåòèì òàêæå, ÷òî ïóòü AA1 (BB1 ) ëåæèò íà íåêîòîðîì öèêëå â G. Ïîýòîìó íå ñóùåñòâóåò âåðøèíû íà AA1 (BB1 ) ñ âíåøíèìè õâîñòàìè íà AA1 (BB1 ) èç ðàçíûõ êëàññîâ. Âåðíåìñÿ ê ðàññìîòðåíèþ äåðåâà T1 è âåðøèí A, B, A1 , B1 . Âåðøèíó â T1 íàçîâåì îñîáîé, åñëè îíà èìååò õîòÿ áû äâà âíåøíèõ õâîñòà, ëåæàùèå â ðàçíûõ êëàññàõ. Çàìåòèì, ÷òî òî÷êà ïåðåñå÷åíèé AA1 è BB1 ÿâëÿåòñÿ îñîáîé, åñëè âåðøèíà A out-èäåíòè÷íà âåðøèíå A1 , à âåðøèíà B out-èäåíòè÷íà âåðøèíå B1 . Â çàâèñèìîñòè îò íàëè÷èÿ îñîáûõ âåðøèí â äåðåâå T1 ðàññìîòðèì äâà ñëó÷àÿ. È â êàæäîì ñëó÷àå äîêàæåì, ÷òî ñóùåñòâóåò îðèåíòèðîâàííîå âëîæåíèå f -ãðàôà F â çíà÷èì õâîñò âåðøèíû K (ñîîòâåòñòâåííî ïëîñêîñòü, ïðè÷åì äëÿ êàæäîãî îðèåíòèðîâàííîãî öèêëà áóäåò âåðíî ñëåäóþùåå: õîðäû ñ âåðøèíàìè íà îðèåíòèðîâàííîì öèêëå ëåæàò îäíîâðåìåííî âíóòðè èëè âíå ýòîãî öèêëà òîãäà è òîëüêî òîãäà, êîãäà îíè âõîäÿò â îäèí êëàññ (îòíîñèòåëüíî âåðøèí íà öèêëå). 1. Ïóñòü â äåðåâå T1 íåò îñîáûõ âåðøèí. Òîãäà âñå âíåøíèå õâîñòû ïðîèçâîëüíîé íå êðàñíîé âåðøèíû äåðåâà ïîìå÷åíû îäíèì êëàññîì. Ïðèïèøåì êàæäîé íå êðàñíîé âåðøèíå äåðåâà òîò æå êëàññ, ÷òî è ó åå âíåøíèõ õâîñòîâ. Ðàñïðåäåëèì êðàñíûå âåðøèíû äåðåâà T1 ïî êëàññàì K1 è K2 ñëåäóþùèì îáðàçîì. Î÷åâèäíî, ÷òî êàæäàÿ êðàñíàÿ âåðøèíà ÿâëÿåòñÿ êîíöîì íåêîòîðîãî ðåáðà, âòîðîé êîíåö êîòîðîãî êðàñíûì íå ÿâëÿåòñÿ. Ðàññìîòðèì êàæäîå ðåáðî äåðåâà T1 ñ îäíèì êðàñ- íûì êîíöîì. Åñëè êëàññ õâîñòà íå êðàñíîãî êîíöà îòëè÷åí îò êëàññà ñàìîãî êîíöà, òî êðàñíóþ âåðøèíó ðåáðà îïðåäåëèì â êëàññ K2 , èíà÷å îïðåäåëèì åå â êëàññ K1 . Îòìåòèì, ÷òî èäåíòè÷íûå âåðøèíû îïðåäåëåíû â îäèí êëàññ, ïðè÷åì âñå out-èäåíòè÷íûå âåðøèíû ïðèíàäëåæàò êëàññó K1 . Â êëàññ K2 ïîïàäàþò, î÷åâèäíî, òîëüêî in-èäåíòè÷íûå âåðøèíû. 17

Ðèñ. 8. Âûäåëåíèå ïðåïÿòñòâèÿ Ïóñòü âåðøèíû A, B, A1 , B1 V1 â ãðàôå G ïîïàëè â îäèí êëàññ. Äîêàæåì, ÷òî òàêîå íåâîçìîæíî. Äëÿ ýòîãî ðàññìîòðèì ñëåäóþùèå âàðèàíòû. A out-èäåíòè÷íà âåðøèíå A1 , à âåðøèíà B out-èäåíòè÷íà âåðøèíå B1 . T1 åñòü îñîáàÿ âåðøèíà, ÷òî ïðîòèâîðå÷èò óñëîâèþ. 1.2. Âåðøèíà A out-èäåíòè÷íà âåðøèíå A1 , à âåðøèíà B in-èäåíòè÷íà âåðøèíå B1 . (Ñëó÷àé, êîãäà A in-èäåíòè÷íà âåðøèíå A1 , à âåðøèíà B out-èäåíòè÷íà âåðøèíå B1 , ðàññìàòðèâàåòñÿ àíàëîãè÷íî.) Òîãäà êëàññ òî÷êè ïåðåñå÷åíèÿ AA1 è BB1 ñîâïàäàåò ñ êëàññîì õâîñòîâ a1 è a2 . Íî, êàê ìû ðàíåå âûÿñíèëè, êëàññ õâîñòîâ b1 è b2 îòëè÷åí îò êëàññà õâîñòîâ a1 è a2 . Ïîýòîìó âåðøèíû B è B1 èìåþò êëàññ K2 . Òàê êàê A out-èäåíòè÷íà âåðøèíå A1 , òî A è A1 èìåþò êëàññ K1 . Ïîëó÷èëè ïðîòèâîðå÷èå ñ ïðåäïîëîæåíèåì, ÷òî A, B, A1 , B1 ïîïàëè â îäèí êëàññ. 1.3. Âåðøèíà A in-èäåíòè÷íà âåðøèíå A1 , à âåðøèíà B in-èäåíòè÷íà âåðøèíå B1 . 1.1. Âåðøèíà Òîãäà â äåðåâå 18

Êëàññ òî÷êè ïåðåñå÷åíèÿ ñ êëàññîì õâîñòîâ b1 è AA1 b2 . è BB1 ñîâïàäàåò ëèáî ñ êëàññîì õâîñòîâ a1 è a2 , ëèáî Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî êëàññ òî÷êè ïåðå- a1 è a2 . Äàëåå ïî àíàëîãèè ñ ï. 1.2 ïðèõîäèì ê ïðîòèâîðå÷èþ ñ ïðåäïîëîæåíèåì, ÷òî A, B, A1 , B1 ïîïàëè â îäèí êëàññ. Òàêèì îáðàçîì, ëþáûå ÷åòûðå âåðøèíû A, A1 , B, B1 èç îäíîãî êëàññà, ãäå A èäåíòè÷íà A1 , à B èäåíòè÷íà B1 , ëåæàò íà E â ýòîì öèêëè÷åñêîì ïîðÿäêå. Çíà÷èò, â êàæäîì êëàññå èäåíòè÷íûå âåðøèíû ìîæíî ñîåäèíèòü âíå îêðóæíîñòè E íåïåðåñåêàþùèìèñÿ êðèâîëèíåéíûìè îòðåçêàìè. Ñîåäèíèì èõ â T1 è çàìåíèì êàæäóþ âåðøèíó (íå êðàñ- ñå÷åíèÿ ñîâïàäàåò ñ êëàññîì õâîñòîâ íóþ) îðèåíòèðîâàííîé ïðîòèâ ÷àñîâîé ñòðåëêè îêðóæíîñòüþ (ðèñ. 9). Ðèñ. 9. Çàìåíà âåðøèí îðèåíòèðîâàííûìè öèêëàìè Ïîÿñíèì, ÷òî ìû ïîëó÷èëè èñõîäíûé f -ãðàô (ñ ìåòêàìè íà âñåõ õîðäàõ +1) è åãî ïîãðóæåíèå â ïëîñêîñòü òàêîå, ÷òî âñå îêðóæíîñòè îðèåíòèðîâàíû îäèíàêîâî è ïðîòèâ ÷àñîâîé ñòðåëêè. Ïðè ýòîì âûáîð îðèåíòàöèè "äîáàâëåííûõ" îêðóæíîñòåé ñóùåñòâåí (ïðè äðóãèõ âûáîðàõ îðèåíòàöèè ìåòêè íà íåêîòîðûõ õîðäàõ áóäóò −1, ÷òî ïðîòèâîðå- ÷èò íàøåé äîãîâîðåííîñòè â íà÷àëå ðàçäåëà). Çàìåòèì, ÷òî åñëè ñóùåñòâóþò äâå ïåðåñåêàþùèåñÿ õîðäû â ïîëó÷åííîì f -ãðàôå, òî íà êàæäîé èç íèõ âûäåëåíû êðàñíûå âåðøèíû, ïðè÷åì êëàññ âåðøèí íà îäíîé õîðäå îòëè÷åí îò êëàññà âåðøèí íà äðóãîé. Ïåðåñå÷åíèÿ õîðä óñòðàíèì ñëåäóþùèì îáðàçîì. Êàæäóþ âíóòðåííþþ õîðäó ïîëó÷åííîãî øèíû èç êëàññà K2 , f -ãðàôà, íà êîòîðîé âûäåëåíû êðàñíûå âåð- ïåðåâåäåì âíóòðü ñîîòâåòñòâóþùåãî öèêëà ñ ïîìîùüþ èíâåðñèè. Â èòîãå ïîëó÷èì èñêîìîå îðèåíòèðîâàííîå âëîæåíèå f -ãðàôà F â ïëîñêîñòü. Çàìå- òèì, ÷òî â ýòîì âëîæåíèè âñå îðèåíòèðîâàííûå öèêëû ëåæàò âíå äðóã äðóãà. 2. Ïóñòü â äåðåâå T1 åñòü îñîáûå âåðøèíû. Èíäóêöèåé ïî äîêàæåì, ÷òî ñóùåñòâóåò óêàçàííîå âëîæåíèå Áàçà èíäóêöèè. f -ãðàôà F n ÷èñëó îñîáûõ âåðøèí â ïëîñêîñòü. n = 1. Ðàçîáüåì íà äâà êëàññà ìíîæåñòâî âåðøèí äåðåâà T1 , w, ñëåäóþùèì îáðàçîì. Ñóùåñòâóåò åäèíñòâåííûé ïóòü, ïðîèçâîëüíóþ âåðøèíó v äåðåâà ñ îñîáîé. Îïðåäåëèì âåðøèíó v â òîò Ïóñòü èñêëþ÷àÿ îñîáóþ âåðøèíó ñîåäèíÿþùèé æå êëàññ, â êîòîðîì è õâîñò îñîáîé âåðøèíû, ëåæàùèé íà ýòîì ïóòè. Èäåíòè÷íûå âåðøèíû ïîïàäóò â îäèí êëàññ (èíà÷å â ãðàôå ñ âåðøèíîé G ñóùåñòâîâàë áû öèêë w, T11 õâîñòû êîòîðîé, ëåæàùèå íà öèêëå, èìåëè ðàçíûå êëàññû). 2 (ñîîòâåòñòâåííî T1 ) íàçîâåì ïîääåðåâî äåðåâà T1 , ìíîæåñòâî âåðøèí êîòîðîãî ñîñòîèò èç w è âñåõ âåðøèí êëàññà 0 (ñîîòâåòñòâåííî 1). 1 2 1 Òîãäà âåðøèíà w íå ÿâëÿåòñÿ îñîáîé îòíîñèòåëüíî T1 (ñîîòâåòñòâåííî T1 ). Èç T1 2 è T1 ïîëó÷èì îðèåíòèðîâàííîå âëîæåíèå íåêîòîðûõ f -ãðàôîâ (ñì. ñëó÷àé 1), îðèåíòèðîâàííûå öèêëû êîòîðûõ ëåæàò âíå äðóã äðóãà. Ýòè f -ãðàôû èìåþò îäèí îáùèé Äåðåâîì îðèåíòèðîâàííûé öèêë (êîòîðîìó ñîîòâåòñòâóåò 19 w), ïðè÷åì âñå õîðäû f -ãðàôîâ ëåæàò

f -ãðàôîâ âíóòðü ýòîãî öèêëà. Òåì ñàìûì ïîëó÷èì èñêîìîå îðèåíòèðîâàííîå âëîæåíèå f -ãðàôà F â ïëîñêîñòü. Øàã èíäóêöèè. Ïóñòü ïðè n = k ñóùåñòâóåò îðèåíòèðîâàííîå âëîæåíèå f -ãðàôà F â ïëîñêîñòü. Ðàññìîòðèì ñëó÷àé, êîãäà n = k+1. Âûáåðåì ïðîèçâîëüíóþ îñîáóþ âåðøèíó w äåðåâà T1 . 2 1 Àíàëîãè÷íî îïèñàííîìó â áàçå èíäóêöèè îïðåäåëèì äåðåâüÿ T1 è T1 . Òîãäà âåðøè1 2 1 2 íà w íå ÿâëÿåòñÿ îñîáîé îòíîñèòåëüíî T1 (T1 ). Çíà÷èò, èç T1 è T1 ïî ïðåäïîëîæåíèþ èíäóêöèè ìîæíî ïîëó÷èòü îðèåíòèðîâàííûå âëîæåíèÿ äâóõ f -ãðàôîâ. Ýòè f -ãðàôû èìåþò îäèí îáùèé îðèåíòèðîâàííûé öèêë (êîòîðîìó ñîîòâåòñòâóåò w ). Åñëè îáà f - âíå ýòîãî öèêëà. Èíâåðñèåé ïåðåâåäåì îäèí èç ãðàôà ðåàëèçîâàíû îäíîâðåìåííî âíóòðè èëè âíå îáùåãî öèêëà, ïðèìåíèì èíâåðñèþ (îòíîñèòåëüíî ýòîãî öèêëà) ê îäíîìó èç íèõ. Òåì ñàìûì ïîëó÷èì èñêîìîå îðèåíòèðî- f -ãðàôà F â ïëîñêîñòü. f -ãðàô F îðèåíòèðîâàííî âëîæèì â ïëîñêîñòü. Ñëåäîâàòåëüíî, ïî ñ ñîîòâåòñòâóþùèì f -ãðàôîì F ÿâëÿåòñÿ âûñîòíûì. Äîñòàòî÷íîñòü âàííîå âëîæåíèå Òàêèì îáðàçîì, òåîðåìå 1 àòîì äîêàçàíà. Óòâåðæäåíèå 2 (Â.À. Òðèôîíîâà, ìèíèìàëüíîñòü ñïèñêà ïðåïÿòñòâèé V è V (r), r ≥ 1). Ïðåïÿòñòâèå V è ñåðèÿ ïðåïÿòñòâèé V (r), r ≥ 1 îáðàçóþò ìèíèìàëü- íîå (ïî âêëþ÷åíèþ) ìíîæåñòâî ïðåïÿòñòâèé, äëÿ êîòîðîãî âûïîëíåíî ñâîéñòâî èç òåîðåìû K1 . Çàìå÷àíèå. Ìèíèìàëüíîñòü ñïèñêà ïðåïÿòñòâèé îçíà÷àåò, ÷òî äëÿ ëþáîãî ñîáñòâåí- íîãî ïîäìíîæåñòâà ýòîãî ìíîæåñòâà ïðåïÿòñòâèé íå âûïîëíåíî ñâîéñòâî èç òåîðåìû K1 . Ýòî ðàâíîñèëüíî âûïîëíåíèþ ñëåäóþùåãî óñëîâèÿ: îäíî ïðåïÿòñòâèå íåëüçÿ ïåðå- âåñòè â äðóãîå ñ ïîìîùüþ îïåðàöèè âçÿòèÿ ïîä-f -ãðàôà è ïîñëåäóþùåãî ïðèìåíåíèÿ f -ãîìåîìîðôèçìà. Èç óñëîâèÿ ìèíèìàëüíîñòè ñïèñêà ñëåäóåò (ñ ó÷åòîì êðèòåðèÿ K1 ) ñëåäóþùåå ñâîé- ñòâî: ïîä-f -ãðàô ëþáîãî èç ïðåïÿòñòâèé, íå ñîâïàäàþùèé ñ ïðåïÿòñòâèåì, ñîîòâåòñòâóåò âûñîòíîìó àòîìó. Äîêàçàòåëüñòâî. Ó ïðåïÿòñòâèÿ V åñòü òîëüêî äâà ïîä-f -ãðàôà, íå ñîâïàäàþùèå ñ ýòèì ïðåïÿòñòâèåì: îäèí èç íèõ ñîñòîèò èç äâóõ îêðóæíîñòåé è îäíîé âíåøíåé õîðäû, äðóãîé ñîñòîèò èç äâóõ îêðóæíîñòåé è äâóõ âíåøíèõ õîðä. Çàìåòèì, ÷òî ó f -ãîìåîìîðôíûõ f -ãðàôîâ ñóùåñòâóåò åñòåñòâåííàÿ áèåêöèÿ ìåæäó ìíîæåñòâàìè îêðóæíîñòåé, ÷èñëî âåðøèí ó êîòîðûõ îòëè÷íî îò äâóõ. ×èñëî îêðóæíî- V è ó ëþáîãî åãî ïîä-f -ãðàôà äâà. À ÷èñëî îêðóæíîñòåé ó êàæäîãî èç ïðåïÿòñòâèé V (r), r ≥ 1, òîëüêî îäíî, ïðè÷åì ÷èñëî âåðøèí íà îêðóæíîñòè ó êàæäîãî èç ýòèõ ïðåïÿòñòâèé áîëüøå äâóõ. Òàêèì îáðàçîì, ïðåïÿòñòâèå V íåëüçÿ ïåðåâåñòè â ïðåïÿòñòâèå V (r), r ≥ 1, ñ ïîìîùüþ îïåðàöèè âçÿòèÿ ïîä-f -ãðàôà è ïîñëåäóþùåãî ïðèìåíåíèÿ f -ãîìåîìîðôèçìà. Àíàëîãè÷íî ìîæíî ïîêàçàòü, ÷òî ïðåïÿòñòâèå V (r), r ≥ 1, íåëüçÿ ïåðåâåñòè â ïðåïÿòñòâèå V ñ ïîìîùüþ îïåðàöèè âçÿòèÿ ïîä-f -ãðàôà è ïîñëåäóþùåãî ïðèìåíåíèÿ f -ãîìåîìîðôèçìà. Ïðåïÿòñòâèÿ V (r), r ≥ 1 ïîïàðíî íå èçîìîðôíû, ïîñêîëüêó ÷èñëî âåðøèí íà èõ îêðóæíîñòÿõ ïîïàðíî ðàçëè÷íî. Ãðàôû ïåðåñå÷åíèé ïðåïÿòñòâèé V (k) è V (l), k = ̸ l, ïðåäñòàâëÿþò ñîáîé öèêëû ñîîòâåòñòâåííî èç 2k+1 è 2l+1 âåðøèí. Âçÿòèå ïîä-f -ãðàôà ó ïðåïÿòñòâèÿ V (k) ìîæåò óìåíüøèòü êîëè÷åñòâî âíóòðåííèõ õîðä ýòîãî ïðåïÿòñòâèÿ, ÷òî ïðèâåäåò ê óäàëåíèþ âåðøèí ó åãî ãðàôà ïåðåñå÷åíèé. Çàìåòèì, ÷òî öèêë 2k + 1 íåëüçÿ ïðèâåñòè ê öèêëó 2l + 1 óäàëåíèåì âåðøèí. Ïóñòü ãðàô ïåðåñå÷åíèé íåêîòîðîãî ïîä-f -ãðàôà ïðåïÿòñòâèÿ V (k) íå ÿâëÿåòñÿ öèêëîì. Òîãäà íåîáõîäèìî äîáàâèòü âíóòðåííèå õîðäû ê îêðóæíîñòè L ýòîãî ïîä-f -ãðàôà, ÷òîáû ãðàô ïåðåñå÷åíèé ïîëó÷åííîñòåé ó ïðåïÿòñòâèÿ 20

f -ãîìåîìîðôèçìà íå äîáàâëÿþò íîâûõ âíóòðåííèõ õîðä ê L. Ñëåäîâàòåëüíî ïðåïÿòñòâèå V (k) íåëüçÿ ïåðåâåñòè â ïðåïÿòñòâèå V (l) ñ ïîìîùüþ îïåðàöèè âçÿòèÿ ïîä-f -ãðàôà è ïîñëåäóþùåãî ïðèìåíåíèÿ f -ãîìåîìîðôèçìà. Ñëåäñòâèåì èç òåîðåìû K1 ÿâëÿåòñÿ Òåîðåìà K2 (Â.À. Òðèôîíîâà, êðèòåðèé âûñîòíîñòè àòîìà [15]). Àòîì ÿâëÿåòñÿ âûñîòíûì òîãäà è òîëüêî òîãäà, êîãäà åãî f -ãðàô íå ñîäåðæèò ïîäãðàôà, ãîìåîìîðôíîãî ïîëíîìó äâóäîëüíîìó ãðàôó K3,3 , è íå ñîäåðæèò ïîä-f -ãðàôà, f ãîìåîìîðôíîãî ïðåïÿòñòâèþ V . Äîêàçàòåëüñòâî. Åñëè f -ãðàô F àòîìà ñîäåðæèò ïîäãðàô, ãîìåîìîðôíûé ïîëíîìó äâóäîëüíîìó ãðàôó K3,3 , òî ïî òåîðåìå ÏîíòðÿãèíàÊóðàòîâñêîãî òàêîé f -ãðàô â ïëîñêîñòü íåâëîæèì. Òåì áîëåå íå ñóùåñòâóåò îðèåíòèðîâàííîãî âëîæåíèÿ F â ïëîñêîñòü. Ïóñòü àòîì âûñîòíûì íå ÿâëÿåòñÿ. Ðàññìîòðèì åãî f -ãðàô. Ïî òåîðåìå 2 ýòîò f ãðàô ñîäåðæèò ïîä-f -ãðàô, f -ãîìåîìîðôíûé ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Íî ëþáîå ïðåïÿòñòâèå èç ýòîé ñåðèè ñîäåðæèò ïîäãðàô, ãîìåîìîðôíûé K3,3 (ëåììà 2). Òåîðåìà äîêàçàíà. ãî f -ãðàôà ïðåäñòàâëÿë ñîáîé öèêë. Îäíàêî îïåðàöèè 4. Íîâîå äîêàçàòåëüñòâî ãèïîòåçû Â.À.Âàñèëüåâà Â äàííîì ðàçäåëå ïðèâîäèòñÿ íîâîå äîêàçàòåëüñòâî ãèïîòåçû Â.À. Âàñèëüåâà [21] î êðèòåðèè ïëàíàðíîñòè ãðàôà ñ âåðøèíàìè ñòåïåíè 4 è äîïîëíèòåëüíîé êðåñòîâîé ñòðóêòóðîé. Âïåðâûå ãèïîòåçà áûëà äîêàçàíà Â.Î.Ìàíòóðîâûì [22]. Ãèïîòåçà (Â.À. Âàñèëüåâ [22]). Åñëè 4-âàëåíòíûé ãðàô ñ êðåñòîâîé ñòðóêòóðîé â âåðøèíàõ íå âëîæèì â ïëîñêîñòü ñ ñîõðàíåíèåì ýòîé ñòðóêòóðû, òî ó íåãî íàéäóòñÿ äâà öèêëà, íå èìåþùèå îáùèõ ðåáåð è èìåþùèå ðîâíî îäíó òî÷êó ïåðåêðåñòüÿ1 . Çäåñü ïðèâîäèòñÿ íàøå íîâîå äîêàçàòåëüñòâî, îïèðàþùååñÿ íà òåîðåìó K1 , äîêàçàííóþ â ïðåäûäóùåì ðàçäåëå. Çàìå÷àíèå. Ìû áóäåì ðàññìàòðèâàòü òîëüêî ñâÿçíûå è êîíå÷íûå ãðàôû; ïåòëè è êðàòíûå ðåáðà äîïóñêàþòñÿ. Ïóñòü äàí ãðàô, âñå âåðøèíû êîòîðîãî èìåþò ñòåïåíü 4, è çàäàíà íåêîòîðàÿ âåðøèíà íà íåì. Íàçîâåì êðåñòîâîé ñòðóêòóðîé ïîëóðåáåð â ýòîé âåðøèíå ëþáîå ðàçáèåíèå ÷åêðåñòîâîé ñòðóêòóðîé òûðåõ âõîäÿùèõ â íåå ïîëóðåáåð íà äâå ïàðû. Ïðè ýòîì íàçîâåì ãðàôà êðåñòîâóþ ñòðóêòóðó ïîëóðåáåð â êàæäîé åãî âåðøèíå. Ðåáðà èç êàæäîé ïàðû áóäåì íàçûâàòü êðåñòîâûìè. ïðîòèâîïîëîæíûìè. Ãðàôû ñ êðåñòîâîé ñòðóêòóðîé áóäåì íàçûâàòü Ïîíÿòèå ïðîòèâîïîëîæíîñòè áóäåò âàæíî ïðè âëîæåíèÿõ êðåñòîâûõ ãðàôîâ â ïîâåðõíîñòè: áóäåì ãîâîðèòü, ÷òî ãðàô âëîæèì â äâóìåðíóþ ïîâåðõíîñòü ñ ñîõðàíåíèåì êðå- ñòîâîé ñòðóêòóðû, åñëè ñóùåñòâóåò òàêîå âëîæåíèå, ÷òî ïîëóðåáðà, ïðîòèâîïîëîæíûå â âåðøèíå, ÿâëÿþòñÿ ïðîòèâîïîëîæíûìè íà ïîâåðõíîñòè. Ëþáîé ÷åòûðåõâàëåíòíûé ãðàô, âëîæåííûé â ïîâåðõíîñòü, åñòåñòâåííûì îáðàçîì íàñëåäóåò èç ýòîé ïîâåðõíîñòè êðåñòîâóþ ñòðóêòóðó. Áóäåì íàçûâàòü íå ïðîòèâîïîëîæíûå ïîëóðåáðà, èíöèäåíòíûå îäíîé âåðøèíå, ñîñåäíèìè. Êðåñòîâûé ãðàô íàçûâàåòñÿ X-ïëàíàðíûì, åñëè åãî ìîæíî âëîæèòü â ïëîñêîñòü ñ ñîõðàíåíèåì êðåñòîâîé ñòðóêòóðû. 1 Â ýòîì âèäå (áîëåå òî÷íî, â âèäå êðèòåðèÿ) ãèïîòåçà ñôîðìóëèðîâàíà â ñòàòüå Â.Î.Ìàíòóðîâà [22], à â ðàáîòå Â.À.Âàñèëüåâà [21] ãèïîòåçà ñôîðìóëèðîâàíà (êàê òåîðåìà Ìàíòóðîâà) äëÿ 4-âàëåíòíûõ ãðàôîâ ñ êðåñòîâîé ñòðóêòóðîé, èìåþùèõ ëèøü îäíó óíèêóðñàëüíóþ îêðóæíîñòü. 21

Îáùàÿ âåðøèíà äâóõ ïóòåé íà êðåñòîâîì ãðàôå, íå èìåþùèõ îáùèõ ðåáåð, íàçûâàåòñÿ âåðøèíîé ïåðåêðåñòüÿ, åñëè îäèí èç ýòèõ ïóòåé ïîñëåäîâàòåëüíî ïðîõîäèò ïî ïîëóðåáðàì èç îäíîé ïàðû, âûõîäÿùèì èç ýòîé âåðøèíû, à âòîðîé ïóòü ïîñëåäîâàòåëüíî ïðîõîäèò ïî ïîëóðåáðàì èç äðóãîé ïàðû. Òåîðåìà (Â.Î. Ìàíòóðîâ, êðèòåðèé ïëàíàðíîñòè ãðàôîâ ñ êðåñòîâîé ñòðóêòóðîé. Êðåñòîâûé ãðàô X-ïëàíàðåí òîãäà è òîëüêî òîãäà, êîãäà îí íå ñîäåðæèò äâóõ íåñàìîïåðåñåêàþùèõñÿ öèêëîâ áåç îáùèõ ðåáåð, èìåþùèõ ðîâíî îäíó âåðøèíó ïåðåêðåñòüÿ. Çàìåòèì, ÷òî â ôîðìóëèðîâêå òåîðåìû ñëîâî "íåñàìîïåðåñåêàþùèõñÿ" ìîæíî îïóñòèòü. Òàêæå íå íàêëàäûâàåòñÿ íèêàêèõ îãðàíè÷åíèé íà êîëè÷åñòâî (íåòðàíñâåðñàëüíûõ) ïåðåñå÷åíèé äâóõ öèêëîâ. Äàëåå ìû áóäåì íàçûâàòü ïðåïÿòñòâèåì Âàñèëüåâà äâà öèêëà áåç îáùèõ ðåáåð, èìåþùèå åäèíñòâåííóþ òî÷êó ïåðåêðåñòüÿ. Äîêàçàòåëüñòâî íåîáõîäèìîñòè. Ïðåäïîëîæèì, ÷òî â X-ïëàíàðíîì êðåñòîâîì ãðàôå åñòü äâà öèêëà C1 è C2 , èìåþùèå ðîâíî îäíó âåðøèíó A ïåðåêðåñòüÿ. Ðàññìîòðèì âëîæåíèå òàêîãî ãðàôà â ïëîñêîñòü ñ ñîõðàíåíèåì êðåñòîâîé ñòðóêòóðû. Öèêë C1 äåëèò ïëîñêîñòü íà äâå ÷àñòè. Ïîñêîëüêó òîëüêî âåðøèíà A ÿâëÿåòñÿ äëÿ öèêëîâ C1 è C2 òî÷êîé ïåðåêðåñòüÿ, òî â âåðøèíå A öèêë C2 ïåðåõîäèò èç îäíîé ÷àñòè â äðóãóþ, îñòàâàÿñü â îñòàëüíûõ îáùèõ âåðùèíàõ â òîé æå ÷àñòè. Òàêîãî âëîæåíèÿ áûòü íå ìîæåò, ïîëó÷èì ïðîòèâîðå÷èå. Äîêàçàòåëüñòâî äîñòàòî÷íîñòè. Ïóñòü êðåñòîâûé ãðàô Γ íå ÿâëÿåòñÿ X-ïëàíàðíûì. Ïîêàæåì, ÷òî â íåì ñîäåðæàòñÿ äâà íåñàìîïåðåñåêàþùèõñÿ öèêëà áåç îáùèõ ðåáåð, èìåþùèõ ðîâíî îäíó âåðøèíó ïåðåêðåñòüÿ. Íàì ïîíàäîáèòñÿ ñëåäóþùàÿ òåîðåìà: Òåîðåìà 2 (Â.Î.Ìàíòóðîâ, êðèòåðèé âûñîòíîñòè àòîìà [2]). Àòîì X = (P 2 , K)# ÿâëÿåòñÿ âûñîòíûì òîãäà è òîëüêî òîãäà, êîãäà åãî îñòîâ K ÿâëÿåòñÿ X-ïëàíàðíûì. Çàìå÷àíèå. Îòíîøåíèå ïðîòèâîïîëîæíîñòè â êðåñòîâîé ñòðóêòóðå ãðàôà K îïðå2 äåëÿåòñÿ â ñîîòâåòñòâèè ñ ðàñïîëîæåíèåì ðåáåð íà ïîâåðõíîñòè P . Ëþáîé àòîì ìîæåò áûòü ïîëíîñòüþ âîññòàíîâëåí ïî ñëåäóþùèì êîìáèíàòîðíûì äàííûì: 1. Îñòîâ (÷åòûð¼õâàëåíòíûé ãðàô); 2. Êðåñòîâàÿ ñòðóêòóðà è 3. C-ñòðóêòóðà (â êàæäîé âåðøèíå âûäåëåíû äâå ïàðû ñîñåäíèõ ïîëóðåáåð, êîòîðûå îáðàçóþò ãðàíèöû ÷¼ðíûõ êîëåö). Ñíàáäèì ïðîèçâîëüíûì îáðàçîì C-ñòðóêòóðîé ãðàô Òîãäà ïî òåîðåìå 2 àòîì X Γ. Ïîëó÷èì àòîì íå âûñîòíûé, ïîñêîëüêó åãî îñòîâ Γ X. íå X-ïëàíàðåí. Âîç- íèêàþò äâà ñëó÷àÿ: X íå îðèåíòèðóåìûé; 2) Àòîì X îðèåíòèðóåìûé. Òîãäà èç òåîðåìû K1 ñëåäóåò, ÷òî åãî f -ãðàô ñîäåðæèò ïîä-f -ãðàô, f -ãîìåîìîðôíûé ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. 1) Àòîì Ðàññìîòðèì ïåðâûé ñëó÷àé. Íàïîìíèì, ÷òî çàìêíóòîé öåïüþ ìû íàçûâàëè 1 f -ãðàô s≥ s = 1 çàìêíóòàÿ Ïðåïÿòñòâèåì O íàçîâåì áåç ìåòîê, ñîñòîÿùèé èç îêðóæíîñòåé è öèêëè÷åñêè ñîåäèíÿþùèõ õîðä (ñì.ðèñ. 10). Ïðè öåïü ñîñòîèò èç îäíîé îêðóæíîñòè ñ âíóòðåííåé õîðäîé. çàìêíóòóþ öåïü ñ ìåòêàìè −1 ±1 íà íåîðèåíòèðîâàííûõ ðåáðàõ, ïðè÷åì êîëè÷åñòâî ìåòîê íå÷åòíî. Îïðåäåëåíèå. Íàçîâåì äâà f -ãðàôà ýêâèâàëåíòíûìè, åñëè îäèí èç äðóãîãî ìîæ- íî ïîëó÷èòü ïîñëåäîâàòåëüíîñòüþ ñëåäóþùèõ îïåðàöèé. Ðàçðåøàåòñÿ çàìåíÿòü îðèåíòàöèþ âñåõ ðåáåð êàêîãî-òî öèêëà è îäíîâðåìåííî èçìåíÿòü ìåòêè íà âñåõ íåîðèåí- 22

Ðèñ. 10. Çàìêíóòàÿ öåïü òèðîâàííûõ ðåáðàõ, èíöèäåíòíûõ ýòîìó öèêëó, íà ïðîòèâîïîëîæíûå (åñëè ïðè ýòîì îáà êîíöà íåîðèåíòèðîâàííîãî ðåáðà íå ïðèíàäëåæàò äàííîìó öèêëó). Åñëè îáà êîíöà íåîðèåíòèðîâàííîãî ðåáðà ïðèíàäëåæàò äàííîìó öèêëó, òî ìåòêà íà ýòîì ðåáðå íå ìåíÿåòñÿ. Â ðàáîòå À.Â.Áîëñèíîâà, À.Ò.Ôîìåíêî [1] ïîêàçàíî âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ýêâèâàëåíòíûìè f -ãðàôû, ýêâèâàëåíòíûå f -ãðàôàìè f -ãðàôó è èçîìîðôíûìè àòîìàìè. Â ÷àñòíîñòè, âñå ñ ìåòêàìè +1 íà âñåõ íåîðèåíòèðîâàííûõ ðåáðàõ, çàäàþò îðèåíòèðóåìûå àòîìû. Ëåììà (êðèòåðèé îðèåíòèðóåìîñòè àòîìà). Àòîì îðèåíòèðóåì òîãäà è òîëüêî òîãäà, êîãäà åãî f -ãðàô G íå ñîäåðæèò ïîä-f -ãðàôà, ïðåäñòàâëÿþùåãî ñîáîé ïðåïÿòñòâèå O. Äîêàçàòåëüñòâî. Äîêàæåì íåîáõîäèìîñòü óòâåðæäåíèÿ ëåììû. Ïóñòü àòîì îðèP2 è åíòèðóåì. Âîçüìåì åñòåñòâåííóþ îðèåíòàöèþ ïîâåðõíîñòè òîãäà âñå ìåòêè â ïîëó÷åííîì f -ãðàôå G áóäóò ðàâíû +1. òèì, ÷òî çàìåíà îðèåíòàöèè íà îêðóæíîñòÿõ ïðåïÿòñòâèÿ ìåíÿåò ÷åòíîñòü êîëè÷åñòâà ìåòîê ýêâèâàëåíòíûé f -ãðàôó G, ëÿþùåãî ñîáîé ïðåïÿòñòâèå −1. Ïîýòîìó ëþáîé O. íå f -ãðàô, Íåîáõîäèìîñòü äîêàçàíà. f -ãðàô G ãðàôà, ïðåäñòàâëÿþùåãî ñîáîé ïðåïÿòñòâèå G O íå ñîäåðæèò ïîä-f -ãðàôà, ïðåäñòàâ- Äîêàæåì äîñòàòî÷íîñòü. Ïóñòü Åñëè Çàìå- íå ñîäåðæèò ïîä-f - O. ñîñòîèò òîëüêî èç îäíîé îêðóæíîñòè è âíóòðåííèõ +1. Î÷åâèäíî, ÷òî àòîì ñ òàf -ãðàôîì îðèåíòèðóåì. Ñòÿíåì êàæäóþ îêðóæíîñòü f -ãðàôà â òî÷êó (ñì.ðèñ. 11). Ïîëó÷èì ãðàô Y ñ ìåòêàìè íà ðåáðàõ. (Ïðè ïîñòðîåíèè ãðàôà Y íå ó÷èòûâàåòñÿ îðèåíòàöèÿ îêðóæíîñòåé). Ðàññìîòðèì åãî îñòîâíîå äåðåâî T . Çàìåòèì, ÷òî ïóòåì çàìåíû õîðä, òî âñå ìåòêè íà õîðäàõ ðàâíû êèì Ðèñ. 11. Ñòÿãèâàíèå îêðóæíîñòè â òî÷êó âñåõ ìåòîê ðåáåð, èíöèäåíòíûõ êàêîé-òî âåðøèíå äåðåâà, íà ïðîòèâîïîëîæíûå, ìû âñå- 23

ãäà ñìîæåì ïîëó÷èòü äåðåâî T +1 íà âñåõ ðåáðàõ. Âûáåðåì òàêîé íàáîð îðèìåòêè íà ðåáðàõ äåðåâà T ðàâíû +1. Ïîëó÷èì ñ ìåòêàìè åíòàöèé îêðóæíîñòåé f -ãðàôà, ÷òî âñå f -ãðàô G′ , ýêâèâàëåíòíûé f -ãðàôó G. Ðàññìîòðèì íåïåðåñåêàþùèéñÿ öèêë, îáðàçîâàííûé ïðîèçâîëüíûì ðåáðîì e ãðàôà Y âíå äåðåâà T è íåêîòîðûìè ðåáðàìè äåðåâà. Ðåáðî e èìååò ìåòêó +1, ïîñêîëüêó èíà÷å äàííûé öèêë áû ñîäåðæàë åäèíñòâåííóþ ìåòêó −1, O â f -ãðàôå G. Ââèäó ïðîèçâîëüíîñòè âûáîðà ðåáðà e çàêëþ÷àåì, ÷òî âñå ðåáðà ãðàôà Y èìåþò ìåòêè +1. Ýòî îçíà÷àåò, ÷òî âñå ′ ′ ìåòêè f -ãðàôà G ðàâíû +1. Ïîñêîëüêó f -ãðàôû G è G ýêâèâàëåíòíû, òî îíè çàäàþò îðèåíòèðóåìûå àòîìû. Äîñòàòî÷íîñòü äîêàçàíà. Â ðàáîòå À.Â.Áîëñèíîâà, À.Ò.Ôîìåíêî [1] îïèñàí àëãîðèòì ïîñòðîåíèÿ àòîìà ïî åãî f ãðàôó. Èç äàííîãî àëãîðèòìà ÿñíî, êàê ïî f -ãðàôó âîññòàíîâèòü îñòîâ àòîìà. Íà ðèñ. 12 ÷òî îçíà÷àëî áû ñóùåñòâîâàíèå ïðåïÿòñòâèÿ ïîêàçàíî ïîâåäåíèå îñòîâà àòîìà â çàâèñèìîñòè îò ìåòîê íà íåîðèåíòèðîâàííûõ ðåáðàõ f -ãðàôà. Îñòîâ ïîêàçàí êðàñíûì öâåòîì. Âåðøèíà îñòîâà (ñì.ðèñ. 12a ) ëåæèò íà ðåáðå ñ ìåòêîé +1. Èç âåðøèíû âûõîäÿò ÷åòûðå ëèíèè, êîòîðûå ïðîõîäÿò âäîëü ðåáðà ñ ìåòêîé è âäîëü îðèåíòèðîâàííûõ ðåáåð îêðóæíîñòåé. Íà ðèñ. 12b èç âåðøèíû âûõîäÿò ÷åòûðå ëèíèè, äâå èç êîòîðûõ ïðîõîäÿò âäîëü ðåáðà ñ ìåòêîé, äåëàÿ ïåðåêðóòêó íà ýòîì ðåáðå. Íà ðèñ. 12c ïîêàçàí +1 è −1, f -ãðàô ñ äâóìÿ íåîðèåíòèðîâàííûìè ðåáðàìè, ìå÷åííûìè à òàêæå ñîîòâåòñòâóþùèé f -ãðàôó îñòîâ. +1 +1 a) -1 c) -1 b) Ðèñ. 12. Âîññòàíîâëåíèå îñòîâà àòîìà ïî åãî f -ãðàôó Ìû ðàññìàòðèâàåì ñëó÷àé, êîãäà àòîì X íå îðèåíòèðóåìûé. Òîãäà ïî ëåììå åãî f -ãðàô G ñîäåðæèò ïîä-f -ãðàô, ïðåäñòàâëÿþùèé ñîáîé ïðåïÿòñòâèå O. Ðàññìîòðèì f -ãðàô G. Âîññòàíîâèì îñòîâ Γ ïî f -ãðàôó. Âûáåðåì âåðøèíó A îñòîâà íà ïðîèçâîëüíîì ðåáðå ñ ìåòêîé −1. Ïîñêîëüêó êîëè÷åñòâî −1 íà íåîðèåíòèðîâàííûõ ðåáðàõ ïðåïÿòñòâèÿ O íå÷åòíî, òî ñóùåñòâóþò äâà öèêëà (ïðåïÿòñòâèÿ Âàñèëüåâà) ãðàôà Γ, èìåþùèõ ðîâíî îäíó âåðøèíó ïåðåêðåñòüÿ (âåðøèíó A). Ýòè öèêëû ìîãóò ïåðåñåêàòüñÿ â äðóãèõ âåðøèíàõ ãðàôà Γ, îòëè÷íûõ îò A, è òîãäà ñëó÷àé, êîãäà ïðåïÿòñòâèå O åñòü êàæäûé èç ýòèõ öèêëîâ ïðîõîäèò ïî ñîñåäíèì ïîëóðåáðàì òî÷åê ïåðåñå÷åíèÿ. Íàïðèìåð, íà ðèñ. 13 ïîêàçàíî ïðåïÿòñòâèå ìåòêó −1 O, ñîñòîÿùåå èç ïÿòè îêðóæíîñòåé è èìåþùåå íà òðåõ íåîðèåíòèðîâàííûõ ðåáðàõ. Êðàñíûì è ñèíèì öâåòîì ïîêàçàíû äâà öèêëà - ïðåïÿòñòâèÿ Âàñèëüåâà, òî÷êà ïåðåêðåñòüÿ âûäåëåíà íà îäíîì ðåáðå ñ ìåòêîé −1 è îòìå÷åíà áóêâîé A. 24

-1 -1 +1 +1 -1 Ðèñ. 13. Ïðåïÿòñòâèå Âàñèëüåâà ïî ïðåïÿòñòâèþ O f -ãðàô G íå ÿâëÿåòñÿ ïðåïÿòñòâèåì O, à ñîäåðæèò åãî â êà÷åñòâå ïîä-f -ãðàôà. Íåòðóäíî ïîêàçàòü, ÷òî äîáàâëåíèå íåîðèåíòèðîâàííûõ ðåáåð è îêðóæíîñòåé ê O íå Ïóñòü ìåøàåò ñóùåñòâîâàíèþ ïðåïÿòñòâèÿ Âàñèëüåâà. Â ýòîì ñëó÷àå öèêëû ìîãóò ñàìîïåðåñåêàòüñÿ è èìåòü áîëåå ñëîæíîå ñòðîåíèå. Ïðèìåð ïîêàçàí íà ðèñ. 14. Òàêèì îáðàçîì ìû ïîêàçàëè, ÷òî îñòîâ ëþáîãî íåîðèåíòèðóåìîãî àòîìà ñîäåðæèò ïðåïÿòñòâèå Âàñèëüåâà. Ïåðâûé ñëó÷àé ðàññìîòðåí. X îðèåíòèðóåìûé è íå âûñîòíûé. Ïîñêîëüêó X , à âñå ýêâèâàëåíòíûå f -ãðàôû çàäàþò èçîìîðôíûå àòîìîâ, áóäåì ñ÷èòàòü, ÷òî âñå ìåòêè íà ðåáðàõ f -ãðàôà G Ðàññìîòðèì âòîðîé ñëó÷àé, êîãäà àòîì ìû èññëåäóåì òîëüêî îñòîâ àòîìà îñòîâû ñîîòâåòñòâóþùèõ ðàâíû +1. f -ãðàô G ñîäåðæèò ïîä-f -ãðàô, f -ãîìåîìîðôíûé ïðåïÿòñòâèþ V èëè ïðåïÿòñòâèþ èç ñåðèè V (r), r ≥ 1. Òàê êàê àòîì ñ f -ãðàôîì V èìååò äâîéñòâåííûé f -ãðàô V (1), òî îñòîâû, âîññòàíîâëåííûå ïî V è V (1) ñîâïàäàþò. Íà ðèñ. 15 ïîêàçàíî ïðåïÿòñòâèå Âàñèëüåâà äëÿ f -ãðàôîâ ñåðèè V (r), r ≥ 1. Èç òåîðåìû K1 ñëåäóåò, ÷òî Àíàëîãè÷íî ðàññìîòðåííîìó ñëó÷àþ íåòðóäíî ïîêàçàòü, ÷òî äîáàâëåíèå íåîðèåíòèðîâàííûõ ðåáåð (ñ ìåòêàìè +1) è îêðóæíîñòåé ê êàæäîìó f -ãðàôó ñåðèè V (r), r ≥ 1, íå ìåøàåò ñóùåñòâîâàíèþ ïðåïÿòñòâèÿ Âàñèëüåâà. Îòëè÷èå îò ïåðâîãî ñëó÷àÿ ëèøü â òîì, ÷òî ñ ïîìîùüþ îïåðàöèè ïîäðàçáèåíèÿ íåîðèåíòèðîâàííîãî ðåáðà ê âíóòðåííèì õîðäàì êàæäîãî èç ýòèõ f -ãðàôîâ ìîãóò áûòü äîáàâëåíû îêðóæíîñòè. Òàêèì îáðàçîì, åñëè àòîì îðèåíòèðóåìûé è íå âûñîòíûé, òî åãî îñòîâ ñîäåðæèò ïðåïÿòñòâèå Âàñèëüåâà. Âòîðîé ñëó÷àé ðàññìîòðåí. 25

-1 -1 +1 -1 Ðèñ. 14. Ïðåïÿòñòâèå Âàñèëüåâà ïî Ðèñ. 15. Ïðåïÿòñòâèå Âàñèëüåâà äëÿ 26 f -ãðàôó G f -ãðàôîâ ñåðèè V (r), r ≥ 1

Ñïèñîê ëèòåðàòóðû [1] Áîëñèíîâ À.Â., Ôîìåíêî À.Ò. Èíòåãðèðóåìûå ãàìèëüòîíîâû ñèñòåìû. Ò. 1. Èæåâñê: Èçä. äîì Óäìóðòñêèé óíèâåðñèòåò, 1999. [2] Ìàíòóðîâ Â.Î. Áèôóðêàöèè, àòîìû è óçëû // Âåñòí. Ìîñê. óí-òà. Ìàòåì. Ìåõàí. 2000. 1. 38. [3] Ôîìåíêî À.Ò. Òîïîëîãèÿ ïîâåðõíîñòåé ïîñòîÿííîé ýíåðãèè èíòåãðèðóåìûõ ãàìèëüòîíîâûõ ñèñòåì è ïðåïÿòñòâèÿ ê èíòåãðèðóåìîñòè // Èçâ. ÀÍ ÑÑÑÐ. Ñåð. ìàòåì. 1986. [4] 50, 6. 12761307. Ôîìåíêî À.Ò. Òîïîëîãè÷åñêèå èíâàðèàíòû ãàìèëüòîíîâûõ ñèñòåì, èíòåãðèðóåìûõ ïî Ëèóâèëëþ // Ôóíêö. àíàëèç è åãî ïðèë. 1988. [5] Ôîìåíêî À.Ò. Ñèìïëåêòè÷åñêàÿ òîïîëîãèÿ âïîëíå èíòåãðèðóåìûõ ãàìèëüòîíîâûõ ñèñòåì // Óñïåõè ìàòåì. íàóê. 1989. [6] Ôîìåíêî À.Ò. 22, âûï. 4. 3851. 44, âûï. 1. 145173. Òåîðèÿ áîðäèçìîâ èíòåãðèðóåìûõ ãàìèëüòîíîâûõ íåâûðîæäåííûõ ñèñòåì ñ äâóìÿ ñòåïåíÿìè ñâîáîäû. Íîâûé òîïîëîãè÷åêèé èíâàðèàíò ìíîãîìåðíûõ èíòåãðèðóåìûõ ñèñòåì // Èçâ. ÀÍ ÑÑÑÐ. Ñåð. ìàòåì. 1990. [7] Ôîìåíêî À.Ò. 55, 4. 747779. Òîïîëîãè÷åñêèé èíâàðèàíò, ãðóáî êëàññèôèöèðóþùèé èíòåãðèðóå- ìûå ñòðîãî íåâûðîæäåííûå ãàìèëüòîíèàíû íà ÷åòûðåõìåðíûõ ñèìïëåêòè÷åñêèõ ìíîãîîáðàçèÿõ // Ôóíêö. àíàëèç è åãî ïðèë. 1991. [8] Ôîìåíêî À.Ò., Öèøàíã Õ. 25, âûï.4. 2335. Òîïîëîãè÷åñêèé èíâàðèàíò è êðèòåðèé ýêâèâàëåíòíî- ñòè èíòåãðèðóåìûõ ãàìèëüòîíîâûõ ñèñòåì ñ äâóìÿ ñòåïåíÿìè ñâîáîäû // Èçâ. ÀÍ ÑÑÑÐ. Ñåð. ìàòåì. 1990. [9] 54, 3. 546575. Ilyutko D.P., Manturov V.O. Virtual knots: the state of the art. Series on knots and everything. Vol.51. Singapore: World Scientic, 2012. [10] Íèêîíîâ È. Ì. Âûñîòíûå àòîìû ñ òðàíçèòèâíîé íà âåðøèíàõ ãðóïïîé ñèììåòðèé // Âåñòí. Ìîñê. óí-òà. Ìàòåì. Ìåõàí. 2016. 6. 1725. [11] Òðèôîíîâà Â.À. Âûñîòíûå ÷àñòè÷íî ñèììåòðè÷íûå àòîìû // Âåñòí. Ìîñê. óí-òà. Ìàòåì. Ìåõàí. 2018. 2. 3341. [12] Âîë÷àíåöêèé Í. Â., Íèêîíîâ È. Ì. Ìàêñèìàëüíî ñèììåòðè÷íûå âûñîòíûå àòîìû // Âåñòí. Ìîñê. óí-òà. Ìàòåì. Ìåõàí. 2013. 2. 36. [13] Êóäðÿâöåâà Å. À., Ðåàëèçàöèÿ ãëàäêèõ ôóíêöèé íà ïîâåðõíîñòÿõ â âèäå ôóíêöèé âûñîòû // Ìàòåì. ñá., [14] 190:3 (1999), 2988. Samelson H., Orientability of hypersurfaces in Rn // Proc. Am. Math. Soc. 22, 301-302 (1969). [15] Òðèôîíîâà Â.À., Êðèòåðèè âûñîòíîñòè àòîìà // Âåñòí. Ìîñê. óí-òà. Ìàòåì. Ìå- õàí., 2020, 3, 1224. [16] Îøåìêîâ À. À. Ôóíêöèè Ìîðñà íà äâóìåðíûõ ïîâåðõíîñòÿõ. Êîäèðîâàíèå îñîáåííîñòåé // Òð. Ìàòåì. èí-òà ÐÀÍ. 1994. 205. 131140. 27

[17] Bouchet A. Circle graph obstructions // J. Combin. Theory. Ser. B. 1994. 60. 107144. [18] Chmutov S., Duzhin S., Lando S. Vassiliev knot invariants II. Intersection graph conjecture for trees, singularities and bifurcations // Adv. Sov. Math. 1994. 21. 127 134. [19] Mellor B. The intersection graph conjecture for loop diagrams // J. Knot Theory Ramications. 2000. [20] Chmutov S., Lando S. Topol. 2007. [21] 9. 187211. Mutant knots and intersection graphs // Algebr. and Geom. 7, 15791598. Âàñèëüåâ Â. À. Èíâàðèàíòû è êîãîìîëîãèè ïåðâîãî ïîðÿäêà äëÿ ïðîñòðàíñòâ âëî- æåíèé ñàìîïåðåñåêàþùèõñÿ êðèâûõ â R // Èçâ. ÐÀÍ. Ñåð. ìàòåì. 2005. 69, 5. Ñ. 352. [22] Ìàíòóðîâ Â. Î. Äîêàçàòåëüñòâî ãèïîòåçû Â. À. Âàñèëüåâà î ïëàíàðíîñòè ñèíãó- ëÿðíûõ çàöåïëåíèé // Èçâ. ÐÀÍ. Ñåð. ìàòåì. 2005. 28 69, 5. Ñ. 169178.