Распределение количества компонент связности дополнения к наборам замкнутых геодезических (1104603), страница 3
Текст из файла (страница 3)
Êîìáèíàòîðíûé àíàëîã íåðàâåíñòâà Õèðöåáðóõà. Äëÿ íåòðèâèàëüíûõ íàáîðîâ ïñåâäîïðÿìûõ íà ïëîñêîñòè RP2 ïðè m < n − 2:)∑(132i − 7t2 + t3 > 8 +ti .(2.5)22i>410Ðèñ. 2: n = 9, t2 = 6, t3 = 4, t4 = 3Ðàâåíñòâî â (2.5) äîñòèãàåòñÿ äëÿ åäèíñòâåííîãî ñ òî÷íîñòüþ äî èçîìîðôèçìà íàáîðà ñåìè ïñåâäîïðÿìûõ.
Ýòîò íàáîð çàäàåòñÿ äâóìÿ òî÷êàìè A è B , ÷åðåç êàæäóþèç êîòîðûõ ïðîõîäèò ïî 4 ïñåâäîïðÿìûå íàáîðà (îäíà èç ïñåâäîïðÿìûõ ïðîõîäèò÷åðåç îáå òî÷êè A è B ). Òîãäà t4 = 2, t2 = 9, t3 = ti = 0 ïðè i > 5. Äëÿ âñåõîñòàëüíûõ íàáîðîâ ïñåâäîïðÿìûõ èìååì)∑(31t2 + t3 > 9 +2i − 7ti .22i>4Öåëü äàííîãî ïàðàãðàôà äîêàçàòü êîìáèíàòîðíûé àíàëîã (2.5) íåðàâåíñòâà Ô.
Õèðöåáðóõà, äëÿ ÷åãî íàì ïîòðåáóþòñÿ ñëåäóþùèå ëåììû.Äëÿ íåòðèâèàëüíûõ íàáîðîâ ïñåâäîïðÿìûõ ÷èñëà v, e è f êëåòî÷íîãîêîìïëåêñà âûðàæàþòñÿ ÷åðåç ti :∑∑∑v=ti , e =iti ,f =1+(i − 1)ti .Ëåììà 2.1.i>2i>2i>2Äîêàçàòåëüñòâî. ×èñëî v âûðàæàåòñÿ óêàçàííûì ñïîñîáîì ïî îïðåäåëåíèþ ÷èñåëti . Èç êàæäîé∑òî÷êè ïåðåñå÷åíèÿ i ïñåâäîïðÿìûõ âûõîäèò 2i ðåáåð êîìïëåêñà, ïîýòîìó ñóììà i>2 2iti ñóòü êîëè÷åñòâî ðåáåð, ïîñ÷èòàííûõ äâàæäû. Èç ýéëåðîâîéõàðàêòåðèñòèêè ïðîåêòèâíîé ïëîñêîñòè èìååì v −e+f = 1, îòêóäà ñëåäóåò ôîðìóëàäëÿ ÷èñëà f .Ëåììà 2.2.Å. Ìåëüõèîð, [27]. Äëÿ íåòðèâèàëüíûõ íàáîðîâ ïñåâäîïðÿìûõ∑∑(3 − i)ti = 3 +(j − 3)pj .i>2j>311(2.6)Äîêàçàòåëüñòâî. ×èñëà âåðøèí v , ðåáåð e è îáëàñòåé f êîìïëåêñà ðàâíû∑∑∑1∑v=ti , e =iti =jpj , f =pj .2 j>3i>2i>2j>3Íàïîìíèì, ÷òî äëÿ íåòðèâèàëüíûõ íàáîðîâ p2 = 0.
Ïî ôîðìóëå Ýéëåðà äëÿ ïðîåêòèâíîé ïëîñêîñòè ïîëó÷àåì()∑∑∑∑3 = 3f − (2e + e) + 3v = 3pj −jpj +iti + 3ti =j>3j>3i>2i>2∑∑(3 − j)pj +(3 − i)ti .j>3i>2Äàëåå óäîáíåå ðàññìàòðèâàòü îáúåäèíåíèå ïñåâäîïðÿìûõ (íåòðèâèàëüíîãî íàáîðà) êàê ãðàô, âëîæåííûé â ïðîåêòèâíóþ ïëîñêîñòü. Âåðøèíàìè è ðåáðàìè ýòîãîãðàôà ñîîòâåòñòâåííî ÿâëÿþòñÿ òî÷êè ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ è äóãè ïñåâäîïðÿìûõ, íå ñîäåðæàùèå îòëè÷íûõ îò ñâîèõ êîíöîâ òî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ.Ñòåïåíü ëþáîé âåðøèíû (ò.å.
÷èñëî èñõîäÿùèõ ðåáåð) ÷åòíà, òàê êàê òî÷êà ïåðåñå÷åíèÿ i ïñåâäîïðÿìûõ ÿâëÿåòñÿ âåðøèíîé ñòåïåíè 2i. Ñëåäîâàòåëüíî, ÷èñëî âåðøèíñòåïåíè 2i ðàññìàòðèâàåìîãî ãðàôà ðàâíî ti äëÿ i = 2, . . . , n. Ëþáîå ðåáðî ãðàôàäëÿ íåòðèâèàëüíîãî íàáîðà ïñåâäîïðÿìûõ ïðèìûêàåò ê äâóì ðàçëè÷íûì îáëàñòÿìíà ïðîåêòèâíîé ïëîñêîñòè.  ãðàôå íåò ïåòåëü è êðàòíûå ðåáðà ìåæäó ïàðîé âåðøèí, åñëè îíè åñòü, ëåæàò íà îäíîé ïñåâäîïðÿìîé.(ëåììà î ïðîñòîì ðåáðå) Ïóñòü äëÿ íàáîðà n ïñåâäîïðÿìûõ âåðíî m <n − 1.
Ïóñòü ñòåïåíè îáîèõ êîíöîâ íåêîòîðîãî ðåáðà ñîîòâåòñòâóþùåãî ãðàôàðàâíû ÷åòûðåì. Òîãäà èç äâóõ ïðèìûêàþùèõ ê ýòîìó ðåáðó îáëàñòåé õîòÿ áûîäíà îãðàíè÷åíà íå ìåíåå ÷åì ÷åòûðüìÿ ðåáðàìè ãðàôà.Ëåììà 2.3.Äîêàçàòåëüñòâî. Îáîçíà÷èì êîíöû ýòîãî ðåáðà ÷åðåç A è B , à ïñåâäîïðÿìûå, ïðîõîäÿùèå ÷åðåç òî÷êè A è B è îòëè÷íûå îò ïñåâäîïðÿìîé AB , ÷åðåç l1 è l2 ñîîòâåòñòâåííî. Îáîçíà÷èì òî÷êó ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ l1 è l2 ÷åðåç C . Ïðåäïîëîæèì,÷òî îáå ïðèìûêàþùèå ê ðåáðó AB îáëàñòè îãðàíè÷åíû òðåìÿ ðåáðàìè. Îäíî èç ýòèõðåáåð ýòî AB , à äâà äðóãèõ (äëÿ êàæäîé îáëàñòè) íàõîäÿòñÿ íà ïñåâäîïðÿìûõ l1è l2 è èìåþò îáùóþ òî÷êó.
Òî÷êà C ýòî åäèíñòâåííàÿ îáùàÿ òî÷êà ïñåâäîïðÿìûõl1 è l2 , ïîýòîìó êàæäàÿ èç äâóõ ïðèìûêàþùèõ ê ðåáðó AB îáëàñòåé îãðàíè÷åíàðåáðîì ñ êîíöàìè â òî÷êàõ A è C , ðåáðîì ñ êîíöàìè â òî÷êàõ B è C è ñàìèì ðåáðîìAB . Ñëåäîâàòåëüíî, íà ïñåâäîïðÿìîé l1 åñòü ðîâíî äâå òî÷êè ïåðåñå÷åíèÿ ñ îñòàëüíûìè ïñåâäîïðÿìûìè íàáîðà, è ýòî òî÷êè A è C . Íà ïðîåêòèâíîé ïëîñêîñòè ëþáûåäâå ðàçëè÷íûå ïñåâäîïðÿìûå ïåðåñåêàþòñÿ â åäèíñòâåííîé òî÷êå, ïîýòîìó êàæäàÿïñåâäîïðÿìàÿ èç íàáîðà, êðîìå l1 , ïðîõîäèò èëè ÷åðåç òî÷êó A, èëè ÷åðåç òî÷êó C .Ñòåïåíü òî÷êè A ðàâíà ÷åòûðåì, ò.å. ÷åðåç òî÷êó A ïðîõîäèò, íå ñ÷èòàÿ l1 , òîëüêîïñåâäîïðÿìàÿ AB .
Òîãäà ÷åðåç òî÷êó C âìåñòå ñ ïñåâäîïðÿìîé l1 ïðîõîäèò n − 1ïñåâäîïðÿìûõ, ÷òî ïðîòèâîðå÷èò óñëîâèþ tn−1 = 0. Ñëåäîâàòåëüíî, îáå ïðèìûêàþùèå ê ðåáðó AB îáëàñòè íå ìîãóò áûòü îãðàíè÷åíû òðåìÿ ðåáðàìè ãðàôà êàæäàÿ.12Ëåììà 2.4.(ëåììà îá îöåíêå t2 ñâåðõó). Äëÿ íàáîðîâ n ïñåâäîïðÿìûõ ñ m < n − 2)∑∑(32t2 6 1 + 3p4 +jpj +i−ti .(2.7)2j>5i>3Äîêàçàòåëüñòâî. Äëÿ ñîîòâåòñòâóþùåãî íàáîðó ïñåâäîïðÿìûõ ãðàôà îáîçíà÷èì÷åðåç x ÷èñëî ðåáåð, îáà êîíöà êîòîðûõ èìåþò ñòåïåíü 4, à ÷åðåç y ÷èñëî ðåáåð, îáà êîíöà êîòîðûõ èìåþò∑ ñòåïåíü íå ìåíåå ÷åì 6.Øàã 1.
Âñåãî â ãðàôå i>2 iti ðåáåð, ïîýòîìó ÷èñëî ðåáåð, îäèí êîíåö êîòîðûõèìååò ñòåïåíü 4, à äðóãîé íå ìåíüøóþ ÷åì 6, ðàâíî∑(iti ) − x − y.i>2Êàæäàÿ âåðøèíà ãðàôà ñòåïåíè 4 ÿâëÿåòñÿ êîíöîì ÷åòûðåõ ðåáåð, õîòÿ áû îäèíêîíåö êàæäîãî èç êîòîðûõ èìååò ñòåïåíü 4. Ïîýòîìó ñóììàðíîå ïî âñåì ðåáðàì÷èñëî èõ êîíöîâ ñòåïåíè 4 ðàâíî 4t2 è ðàâíî∑∑4t2 = 2x +iti − x − y=⇒x = 2t2 + y −iti .(2.8)i>2i>3Øàã 2. Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò äâå ðàçëè÷íûå òî÷êè A è B , òàêèå ÷òîëþáàÿ ïñåâäîïðÿìàÿ èç íàáîðà ïðîõîäèò ÷åðåç õîòÿ áû îäíó èç íèõ.
Îáîçíà÷èì ÷åðåça è b ÷èñëî ïñåâäîïðÿìûõ íàáîðà, ïðîõîäÿùèõ ÷åðåç òî÷êè A è B ñîîòâåòñòâåííî.Âîçìîæíû äâà ñëó÷àÿ.(i)  íàáîðå íåò ïñåâäîïðÿìîé, ïðîõîäÿùåé ÷åðåç òî÷êè A è B . Òîãäà a + b = nè èç óñëîâèÿ tn−2 = 0 ñëåäóåò, ÷òî a > 3 è b > 3.  ýòîì ñëó÷àå)∑ (3• t2 = ab,i−ti = a + b − 3,i>32• p4 = ab − a − b + 3,pi = 0 ïðè i > 5.Òåïåðü íåðàâåíñòâî (2.7) ïðîâåðÿåòñÿ íåïîñðåäñòâåííî:2ab 6 1 + 3(ab − a − b + 3) + a + b − 3⇔(a − 2)(b − 2) + 3 > 0.(ii)  íàáîðå åñòü ïñåâäîïðÿìàÿ, ïðîõîäÿùàÿ ÷åðåç òî÷êè A è B . Òîãäà a+b = n+1è èç óñëîâèÿ tn−2 = 0 ñëåäóåò, ÷òî a > 4 è b > 4.
 ýòîì ñëó÷àå)∑ (3• t2 = ab − a − b + 1,i>3 i − 2 ti = a + b − 3,• p4 = ab − 2a − 2b + 4,pi = 0 ïðè i > 5.Òåïåðü íåðàâåíñòâî (2.7) ïðîâåðÿåòñÿ íåïîñðåäñòâåííî:2(ab − a − b + 1) 6 1 + 3(ab − 2a − 2b + 4) + a + b − 3⇔(a − 3)(b − 3) − 1 > 0. äàëüíåéøåì äîêàçàòåëüñòâå ëåììû (à èìåííî, â øàãàõ 5 è 6) áóäåì ñ÷èòàòü, ÷òî íåñóùåñòâóåò äâóõ ðàçëè÷íûõ òî÷åê, òàêèõ ÷òî ëþáàÿ ïñåâäîïðÿìàÿ íàáîðà ïðîõîäèò÷åðåç õîòÿ áû îäíó èç íèõ.13Øàã 3. Äëÿ äàííîãî ãðàôà ðàññìîòðèì ìíîæåñòâî F îáëàñòåé (ò.å. êîìïîíåíòñâÿçíîñòè äîïîëíåíèÿ ê ïðÿìûì), êàæäàÿ èç êîòîðûõ îãðàíè÷åíà íå ìåíåå ÷åì÷åòûðüìÿ ðåáðàìè è ãðàíèöà êîòîðîé ñîäåðæèò õîòÿ áû îäíó âåðøèíó ñòåïåíè 4(âíóòðè îáëàñòåé òî÷åê ãðàôà íåò).
Äëÿ îáëàñòè Γ ∈ F îáîçíà÷èì ÷åðåç x(Γ) ÷èñëîîãðàíè÷èâàþùèõ Γ ðåáåð, îáà êîíöà êîòîðûõ èìåþò ñòåïåíü 4. Äëÿ îáëàñòè Γ ∈ Fîáîçíà÷èì ÷åðåç s(Γ) ÷èñëî åå âåðøèí (ò.å. âåðøèí íà ãðàíèöå Γ) ñòåïåíè íå ìåíåå÷åì 6. Ïîëîæèì{0, åñëè s(Γ) > 1;δ(Γ) =1, åñëè s(Γ) = 0.Äîêàæåì, ÷òî åñëè îáëàñòü Γ îãðàíè÷åíà j ðåáðàìè, òîs(Γ) 6 (j − 1) − x(Γ) + δ(Γ).(2.9)Ðàññìîòðèì òðè ñëó÷àÿ.(i) x(Γ) = 0. Òîãäà s(Γ) 6 j − 1, òàê êàê íà ãðàíèöå Γ åñòü âåðøèíà ñòåïåíè 4.(ii) x(Γ) = j . Òîãäà s(Γ) = 0 è δ(Γ) = 1.(iii) 0 < x(Γ) < j . Ðàññìîòðèì îòäåëüíî ãðàíèöó Γ, ñîñòîÿùóþ èç j ðåáåð. Ñðåäèíèõ âûáåðåì x(Γ) ðåáåð, îáà êîíöà êîòîðûõ èìåþò ñòåïåíü 4.
Ïóñòü ýòè x(Γ) ðåáåðîáðàçóþò íà ãðàíèöå Γ ðîâíî z(Γ) êîìïîíåíò ñâÿçíîñòè, êàæäàÿ êîìïîíåíòà ýòîíåñêîëüêî ïîäðÿä èäóùèõ âûáðàííûõ ðåáåð. Èç x(Γ) > 0 ñëåäóåò, ÷òî z(Γ) > 1, à èçx(Γ) < j ñëåäóåò, ÷òî êàæäàÿ êîìïîíåíòà íå çàìêíóòà (ò.å. ãîìåîìîðôíà îòðåçêó). êàæäîé êîìïîíåíòå ÷èñëî âåðøèí ñòåïåíè 4 íà åäèíèöó áîëüøå ÷èñëà ðåáåð ýòîéêîìïîíåíòû.
Âñå âåðøèíû è ðåáðà ðàçëè÷íûõ êîìïîíåíò ñâÿçíîñòè ðàçëè÷íû, ïîýòîìó ãðàíèöà îáëàñòè Γ ñîäåðæèò íå ìåíåå x(Γ) + z(Γ) âåðøèí ñòåïåíè 4. Òàê êàêz(Γ) > 1, òîs(Γ) 6 j − 1 − x(Γ).∑Îáîçíà÷èì ÷åðåç s ñóììó s = Γ∈F s(Γ). Ñóììèðóÿ (2.9) ïî âñåì îáëàñòÿì Γ ∈ F ,ïîëó÷èì∑∑∑s6(j − 1)pj −x(Γ) +δ(Γ).(2.10)j>4Γ∈FΓ∈FØàã 4. Ïîêðàñèì â êðàñíûé öâåò ðåáðà ãðàôà, îáà êîíöà êîòîðûõ èìåþò ñòåïåíü 4 è îáå ïðèìûêàþùèå îáëàñòè ê êîòîðûì îãðàíè÷åíû íå ìåíåå ÷åì ÷åòûðüìÿðåáðàìè êàæäàÿ (ò.å. îáå ïðèìûêàþùèå îáëàñòè èç F ).
Îáîçíà÷èì ÷èñëî êðàñíûõðåáåð ÷åðåç a. Òîãäà ïî ëåììå 2.3 (î ïðîñòîì ðåáðå) ÷èñëî x − a ðàâíî ÷èñëó ðåáåð,îáà êîíöà êîòîðûõ èìåþò ñòåïåíü 4 è ðîâíî îäíà èç äâóõ ïðèìûêàþùèõ îáëàñòåéîãðàíè÷åíà íå ìåíåå ÷åì ÷åòûðüìÿ ðåáðàìè (ò.å. îäíà ïðèìûêàþùàÿ îáëàñòü èç F ).Ñëåäîâàòåëüíî,∑x(Γ) = x + a.(2.11)Γ∈FÏîêðàñèì â ñèíèé öâåò ÷åòûðåõóãîëüíûå îáëàñòè, âñå âåðøèíû êîòîðûõ èìåþòñòåïåíü 4.
Äîêàæåì, ÷òî ê êàæäîé ñèíåé îáëàñòè ïðèìûêàåò íå ìåíåå äâóõ êðàñíûõðåáåð. Äëÿ ýòîãî âûâåäåì èç óñëîâèÿ tn−2 = 0 àíàëîãè÷íî ëåììå 2.3 (î ïðîñòîì ðåáðå), ÷òî â êàæäîé ïàðå ïðîòèâîïîëîæíûõ ðåáåð ëþáîé ñèíåé îáëàñòè åñòü õîòÿ áûîäíî êðàñíîå ðåáðî. Ïðåäïîëîæèì ïðîòèâíîå, ÷òî îáà ðåáðà AB è CD íåêîòîðîé ñèíåé îáëàñòè ABCD íå êðàñíûå. Òîãäà ê ðåáðàì AB è CD ïðèìûêàþò òðåóãîëüíûå14îáëàñòè ABH è CDG, ïðè÷åì òî÷êà ïåðåñå÷åíèÿ ïðÿìûõ BC è AD ñîâïàäàåò è ñòî÷êîé H , è ñ òî÷êîé G.
Ñëåäîâàòåëüíî, ÷åðåç ýòó òî÷êó G = H ïðîõîäÿò n − 2 ïñåâäîïðÿìûå íàáîðà (âñå ïñåâäîïðÿìûå êðîìå AB è CD), ÷òî ïðîòèâîðå÷èò óñëîâèþtn−2 = 0.∑Îáîçíà÷èì ÷èñëî ñèíèõ îáëàñòåé ÷åðåç p. ÑóììàΓ∈F δ(Γ) ðàâíà êîëè÷åñòâóîáëàñòåé, êàæäàÿ èç êîòîðûõ îãðàíè÷åíà íå ìåíåå ÷åì ÷åòûðüìÿ ðåáðàìè è âñåâåðøèíû êîòîðîé èìåþò ñòåïåíü 4.
Ïîýòîìó∑∑δ(Γ) 6 p +pj .(2.12)j>5Γ∈FÎáîçíà÷èì ÷åðåç φ ÷èñëî ïàð (C, κ) ñèíèõ îáëàñòåé C è êðàñíûõ ðåáåð κ íàãðàíèöå îáëàñòè C . Òàê êàê ê ëþáîé èç p ñèíèõ îáëàñòåé ïðèìûêàåò íå ìåíåå äâóõêðàñíûõ ðåáåð, òî φ > 2p. Ñ äðóãîé ñòîðîíû, êàæäîå êðàñíîå ðåáðî ïðèìûêàåò ê íåáîëåå ÷åì äâóì ñèíèì îáëàñòÿì è ïîýòîìó 2a > φ. Ñëåäîâàòåëüíî, a > p.
Èòàê, èç(2.10), (2.11), (2.12) è íåðàâåíñòâà a > p ñëåäóåò, ÷òî∑s 6 3p4 − x +jpj .(2.13)j>5Øàã 5. Ðàññìîòðèì ïðîèçâîëüíóþ âåðøèíó V ñòåïåíè íå ìåíåå 6 è óäàëèì èçãðàôà âñå ðåáðà, ëåæàùèå íà ïðîõîäÿùèõ ÷åðåç òî÷êó V ïñåâäîïðÿìûõ (ñîîòâåòñòâåííî èçìåíÿòñÿ ñòåïåíè îñòàâøèõñÿ âåðøèí, à íåêîòîðûå âåðøèíû, âîçìîæíî,èñ÷åçíóò). Îáîçíà÷èì ïîëó÷åííûé ãðàô ÷åðåç G(V ), à èñõîäíûé ãðàô ÷åðåç G. Ïîñëå øàãà 2 äîñòàòî÷íî ðàññìàòðèâàòü òîëüêî òå íàáîðû ïñåâäîïðÿìûõ, äëÿ êîòîðûõíå ñóùåñòâóåò äâóõ òî÷åê, òàêèõ ÷òî ëþáàÿ ïñåâäîïðÿìàÿ íàáîðà ïðîõîäèò ÷åðåç õîòÿ áû îäíó èç íèõ. Äëÿ òàêèõ íàáîðîâ ïñåâäîïðÿìûõ ãðàô G(V ) èìååò õîòÿ áû äâåðàçëè÷íûå âåðøèíû è êàæäàÿ îáëàñòü ïðîåêòèâíîé ïëîñêîñòè, îáðàçîâàííàÿ ãðàôîì G(V ), îãðàíè÷åíà íå ìåíåå ÷åì òðåìÿ ðåáðàìè ãðàôà G(V ). Çíà÷èò, òî÷êà Víàõîäèòñÿ âíóòðè íåêîòîðîé îáëàñòè, îáðàçîâàííîé ãðàôîì G(V ), ãðàíèöà êîòîðîéåñòü d óãîëüíèê ñ âåðøèíàìè A1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
