Распределение количества компонент связности дополнения к наборам замкнутых геодезических, страница 5

Îáîçíà÷èì ýòè òî÷êè ÷åðåç P èQ. Ðàññìîòðèì êîíå÷íóþ ïîñëåäîâàòåëüíîñòü A0 , A1 , . . . , Ai ñåìåéñòâ ïñåâäîïðÿìûõ,â êîòîðîé êàæäîå ñëåäóþùåå ñåìåéñòâî Aj ïîëó÷àåòñÿ èç ïðåäûäóùåãî ñåìåéñòâàAj−1 äîáàâëåíèåì îäíîé ïñåâäîïðÿìîé èç èñõîäíîãî íàáîðà A, íå ïðèíàäëåæàùåéñåìåéñòâó Aj−1 (ïðè ýòîì íå âàæíî, êàêàÿ èìåííî èç îñòàâøèõñÿ ïñåâäîïðÿìûõíàáîðà A äîáàâëÿåòñÿ ê ñåìåéñòâó Aj−1 ). Âîçìîæíû äâà ñëó÷àÿ, â çàâèñèìîñòè îòêîòîðûõ ìû îïðåäåëèì A0 è Ai .(à)  ñåìåéñòâå A íåò ïñåâäîïðÿìîé, ïðîõîäÿùåé ÷åðåç òî÷êè P è Q.

 êà÷åñòâåA0 âîçüìåì 2k ýëåìåíòíîå ìíîæåñòâî ïñåâäîïðÿìûõ, êàæäàÿ èç êîòîðûõ ïðîõîäèò22÷åðåç õîòÿ áû îäíó èç òî÷åê P è Q, à â êà÷åñòâå Ai ñåìåéñòâî A. Òîãäà ïîëó÷àåòñÿI = n − 2k .(á)  ñåìåéñòâå A åñòü ïñåâäîïðÿìàÿ, ïðîõîäÿùàÿ ÷åðåç òî÷êè P è Q. Òàêàÿïñåâäîïðÿìàÿ â ñåìåéñòâå åäèíñòâåííàÿ, íàçîâåì åå ïñåâäîïðÿìîé P Q. Çà êîíôèãóðàöèþ A0 âîçüìåì 2k − 2 ïñåâäîïðÿìûõ, îòëè÷íûõ îò ïñåâäîïðÿìîé P Q, êàæäàÿèç êîòîðûõ ïðîõîäèò ÷åðåç îäíó èç òî÷åê P è Q.

Ïóñòü ñåìåéñòâî Ai îáðàçóþò âñåïñåâäîïðÿìûå èç A, êðîìå ïñåâäîïðÿìîé P Q.  ýòîì ñëó÷àå I = n − 2k + 1.Áóäåì ðàññìàòðèâàòü îáà ñëó÷àÿ îäíîâðåìåííî, ïîêà íå ïîëó÷èì íåðàâåíñòâî íàf (Ai ). Îáîçíà÷èì ÷åðåçR(Ai ) = 2e(Ai ) − 3f (Ai )ðàçíîñòü ìåæäó óäâîåííûì ÷èñëîì ðåáåð è óòðîåííûì ÷èñëîì îáëàñòåé êîíôèãóðàöèè Ai . Äëÿ âñåõ i âåðíî R(Ai ) > 0, òàê êàê êàæäàÿ èç îáëàñòåé îãðàíè÷åíà õîòÿáû òðåìÿ äóãàìè. Ïóñòü ñåìåéñòâî Ai ïîëó÷àåòñÿ èç Ai−1 äîáàâëåíèåì ïñåâäîïðÿìîé li . Ïóñòü ïñåâäîïðÿìàÿ li ïðîõîäèò ÷åðåç vi òî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìûõêîíôèãóðàöèè Ai−1 è åùå ïåðåñåêàåò ui ïñåâäîïðÿìûõ èç Ai−1 â ui òî÷êàõ. Òîãäàâ êîíôèãóðàöèè Ai íà ïñåâäîïðÿìîé li ëåæèò ui òî÷åê ïåðåñå÷åíèÿ êðàòíîñòè äâàè vi òî÷åê ïåðåñå÷åíèÿ êðàòíîñòè õîòÿ áû òðè. Ñëåäîâàòåëüíî, ïñåâäîïðÿìàÿ li ñîñòîèò (â êîíôèãóðàöèè Ai ) èç ui + vi äóã, êàæäàÿ èç êîòîðûõ äåëèò íåêîòîðóþ îáëàñòü, âûñåêàåìóþ ñåìåéñòâîì Ai−1 , íà äâå ÷àñòè.

Ïîýòîìó f (Ai ) − f (Ai−1 ) = ui + vi .Êðîìå òîãî, ïñåâäîïðÿìàÿ li äåëèò íàäâîå ui ðåáåð èç êîíôèãóðàöèè Ai−1 , ïîýòîìóe(Ai ) − e(Ai−1 ) = 2ui + vi . Èç äâóõ ïîñëåäíèõ ôîðìóë ñëåäóåò íåðàâåíñòâîR(ti ) − R(Ai−1 ) = ui − vi .Ïóñòü ïñåâäîïðÿìàÿ li ïðîõîäèò ÷åðåç wi òî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ ñåìåéñòâàA0 .

Òîãäà ïñåâäîïðÿìàÿ li ïåðåñåêàåò ïñåâäîïðÿìûå ñåìåéñòâà A0 â n(A0 ) − wi òî÷êàõ. Ïóñòü zi è xi îáîçíà÷àþò êîëè÷åñòâà íå ëåæàùèõ íà ïñåâäîïðÿìûõ ñåìåéñòâà A0òî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìîé li ñ ïñåâäîïðÿìûìè ñåìåéñòâà Ai−1 , êîòîðûå ïðèíàäëåæàò ðîâíî îäíîé è õîòÿ áû äâóì ïñåâäîïðÿìûì ñåìåéñòâà Ai−1 ñîîòâåòñòâåííî.Âñå îñòàâøèåñÿ òî÷êè ïåðåñå÷åíèÿ ïñåâäîïðÿìîé li ñ ðîâíî îäíîé ïñåâäîïðÿìîé èçAi−1 ëåæàò íà ïðÿìûõ èç A0 , ïîýòîìó îñòàâøèõñÿ òî÷åê íå áîëåå n(A0 ) − 2wi .

Ñëåäîâàòåëüíî, ui 6 n(A0 ) − 2wi + zi . Çàìåòèì, ÷òî vi > wi + xi . ÒîãäàR(Ai ) − R(Ai−1 ) 6 ui − wi − xi 6 n(A0 ) − 3wi + zi − xi .(2.25)Íà ïñåâäîïðÿìîé li íàõîäèòñÿ zi + xi òî÷åê ïåðåñå÷åíèÿ, íå ïðèíàäëåæàùèõ ïñåâäîïðÿìûì èç A0 . Ïîýòîìóf (Ai ) − f (Ai−1 ) = n(A0 ) − wi + zi + xi .(2.26)Ñëîæèâ ôîðìóëû (2.25) è (2.26) ïî âñåì i = 1, 2, .

. . , I ïîëó÷èìR(Ai ) − R(A0 ) 6 In(A0 ) − 3I∑wi +i=1f (Ai ) − f (A0 ) = In(A0 ) −I∑i=123wi +I∑zi −i=1I∑i=1zi +I∑xi .(2.27)i=1I∑i=1xi .(2.28)∑IÂûðàçèìi=1 wi èç íåðàâåíñòâà (2.27) è ïîäñòàâèì â ðàâåíñòâî (2.28), ó÷èòûâàÿR(Ai ) > 0:IIR(A0 ) 4 ∑2∑2f (Ai ) > f (A0 ) + In(A0 ) −+xi +zi .(2.29)333 i=13 i=1Òåïåðü ðàññìîòðèì äâà ñëó÷àÿ ïî îòäåëüíîñòè.Ñëó÷àé (à).

Ïñåâäîïðÿìàÿ P Q íå ïðèíàäëåæèò ñåìåéñòâó A. Òîãäà, ïîäñòàâëÿÿâ íåðàâåíñòâî (2.29) ïàðàìåòðûn(A0 ) = 2k, I = n − 2k, f (A0 ) = k 2 + 2k − 1, R(A0 ) = (k − 1)2 + 2, xi > 0, zi > 0,ïîëó÷àåì íåðàâåíñòâîf (Ai ) >4kn − 6k 2 + 8k − 6.32Îñòàëîñü çàìåòèòü, ÷òî f (A) = f (Ai ) è ÷òî íåðàâåíñòâî 4kn−6k3 +8k−6 > (k + 1)(n − k)ðàâíîñèëüíî íåðàâåíñòâó (k − 3)(n − (3k − 2)) > 0, êîòîðîå âûïîëíÿåòñÿ ïðè äàííûõóñëîâèÿõ íà n è k .

Ïîýòîìó â ñëó÷àå (à) ïîëó÷àåì f > (k + 1)(n − k).Ñëó÷àé (á). Ïñåâäîïðÿìàÿ P Q ïðèíàäëåæèò ñåìåéñòâó A. Îáîçíà÷èì ÷åðåç bjêîëè÷åñòâî òî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ ñåìåéñòâà A êðàòíîñòè j , ëåæàùèõíà ïñåâäîïðÿìîé P Q è îòëè÷íûõ îò òî÷åê P è Q. Òîãäà êîëè÷åñòâîïñåâäîïðÿìûõ∑kñåìåéñòâà A, íå ïðîõîäÿùèõ ÷åðåç òî÷êè P è Q, ðàâíî I = j=2 (j − 1)bj = n − 2k + 1.Èç îïðåäåëåíèÿ ÷èñåë xi è zi ñëåäóåòI∑zi > b 3 + . . . + b kèi=1I∑i=1xi >k∑(j − 3)bj .(2.30)j=3Âû÷èñëèì ïàðàìåòðû ñåìåéñòâà A0 :n(A0 ) = 2k − 2, f (A0 ) = k 2 − 2, R(A0 ) = (k − 2)2 + 2.(2.31)∑kÏîäñòàâèì (2.30), (2.31) è ôîðìóëó f (A) − f (ti ) = 2 + j=2 bj â íåðàâåíñòâî (2.29):∑(4k − 4)n − 6k 2 + 16k − 10f (A) >+ b2 +bj3j=3k(4j − 73).Òàê êàêk∑(j − 1)bj = n − 2k + 154j − 7> (j − 1)36èj=2òîb2 +k∑j=3(bj4j − 73)5> (n − 2k + 1).6Ó÷èòûâàÿ ïîñëåäíåå íåðàâåíñòâî, ïðåîáðàçóåì (2.32) ê âèäóf (A) >(8k − 3)n − 12k 2 + 22k − 15.624ïðè j > 3,(2.32)Îñòàëîñü äîêàçàòü íåðàâåíñòâî(8k − 3)n − 12k 2 + 22k − 15> (k + 1)(n − k)6êîòîðîå èìååò ìåñòî ïðè n >k2 +k2⇔n(2k − 9) > 6k 2 − 28k + 15,+ 3 > 3k + 3 è ïðè k > 6.

Ñëó÷àé (á) ðàçîáðàí. Åùå îäíà íèæíÿÿ îöåíêà ÷èñëà îáëàñòåéÏîä (n, m, f ) êîíôèãóðàöèåé áóäåì èìåòü â âèäó íàáîð èç n ïñåâäîïðÿìûõ íàïðîåêòèâíîé ïëîñêîñòè ñ ìàêñèìàëüíîé êðàòíîñòüþ òî÷åê ïåðåñå÷åíèÿ m, ïðè÷åìäîïîëíåíèå ê èõ îáúåäèíåíèþ ñîñòîèò èç f îáëàñòåé.Ëåììà 2.6.Äëÿ (n, m, f ) êîíôèãóðàöèé ïñåâäîïðÿìûõf >1+n(n − 1) m − 2+(t2 + . . . + tm−1 ).mmÄîêàçàòåëüñòâî.

Ïî ëåììå 2.1f =1+m∑(i − 1)ti .i=2×èñëî ïàð ïñåâäîïðÿìûõ ðàâíîn(n − 1) ∑ i(i − 1)=ti .22i=2mÓìíîæèì ðàâåíñòâî ÷èñëà ïàð íàïîëó÷èì2mè âûäåëèì ñóììó èç ðàâåíñòâà ëåììû 2.1,)mmm (∑∑i(i − 1)n(n − 1) ∑ i(i − 1)=ti =(i − 1)ti −i−1−ti .mmmi=2i=2i=2Ìíîæèòåëè â ïîñëåäíåé ñóììå ðàâíûi−1−Ïîýòîìói(i − 1)(i − 1)(m − i)m−2=>mmmïðè 2 6 i 6 m − 1.n(n − 1) ∑m−26(i − 1)ti −(t2 + .

. . + tm−1 )mmi=2mèf >1+n(n − 1) m − 2+(t2 + . . . + tm−1 ).mmÒåîðåìà 2.4.Äëÿ (n, f, m) êîíôèãóðàöèé ïñåâäîïðÿìûõ ïðè m > 4 è n > m + 1( 2)n + (m2 − 2m − 1)n − m3 + 3m2f >2.(2.33)3m − 125Äîêàçàòåëüñòâî. Âîçüìåì òî÷êó O ïåðåñå÷åíèÿ m ïñåâäîïðÿìûõ l1 , . . . , lm , îáîçíà÷åííûõ â ïîðÿäêå ñëåäîâàíèÿ. Ïñåâäîïðÿìûå l1 , . . . , lm áåç ó÷åòà îñòàëüíûõ ïñåâäîïðÿìûõ íàáîðà äåëÿò ïðîåêòèâíóþ ïëîñêîñòü íà m îáëàñòåé. Îáîçíà÷èì ÷åðåç Di îáëàñòü ìåæäó ïñåâäîïðÿìûìè li è li+1 , ñ÷èòàÿ lm+1 = l1 .

Êàæäàÿ èç îñòàâøèõñÿ n − mïñåâäîïðÿìûõ lm+1 , . . . , ln ïåðåñåêàåò îáëàñòü Di ïî ïðîñòîé äóãå. Âûáåðåì ìàêñèìàëüíîå ïî êîëè÷åñòâó ìíîæåñòâî Mi äóã îáëàñòè Di , ïîïàðíî íå ïåðåñåêàþùèõñÿ âîâíóòðåííèõ òî÷êàõ. Îáîçíà÷èì ÷åðåç ai ÷èñëî äóã ìíîæåñòâà Mi . Îáúåäèíåíèå äóãìíîæåñòâî îòðåçêîâ îáðàçóåò ãðàô áåç öèêëîâ (òî åñòü ëåñ íåñâÿçíîå îáúåäèíåíèåäåðåâüåâ).

Äåéñòâèòåëüíî, ÷åðåç òî÷êó O è ÷åðåç äîëþ ìîæíî ïðîâåñòè ìûñëåííóþïñåâäîïðÿìóþ è óïîðÿäî÷èòü îòðåçêè ïîäìíîæåñòâà ïî ïîðÿäêó (ëþáîìó èç äâóõ,ñ÷èòàÿ îò òî÷êè O) ñëåäîâàíèÿ èõ òî÷åê ïåðåñå÷åíèÿ ñ ìûñëåííîé ïñåâäîïðÿìîé.Òîãäà îáà êîíöà ïåðâîãî ïî ïîðÿäêó îòðåçêà ïðåäïîëàãàåìîãî öèêëà ñóòü êîíöûäâóõ äðóãèõ îòðåçêîâ öèêëà, ðàñïîëàãàþùèõñÿ ïî îäíó ñòîðîíó äîëè îò ïåðâîãî îòðåçêà è, ñëåäîâàòåëüíî, ïåðåñåêàþùèõñÿ âî âíóòðåííåé òî÷êå.  ãðàôå áåç öèêëîâ÷èñëî ðåáåð íå ïðåâîñõîäèò óìåíüøåííîãî íà åäèíèöó ÷èñëà âåðøèí.

Âåðøèíû ãðàôà ðàñïîëàãàþòñÿ íà ïñåâäîïðÿìûõ li è li+1 , ïîýòîìó ai + 1 íå ïðåâîñõîäèò ÷èñëàòî÷åê ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ li è li+1 ñ îñòàâøèìèñÿ (n − m) ïðÿìûìè. Çà cj äëÿj = 2, . . . , m îáîçíà÷èì êîëè÷åñòâî òî÷åê ïåðåñå÷åíèÿ êðàòíîñòè j, ðàñïîëîæåííûõíà ïðÿìûõ l1 , . . . , lm , êðîìå òî÷êè O. Èòàê,m+m∑ai 6 2i=1m∑cj .(2.34)j=2Êàæäàÿ èç n − m − ai äóã, íå âîøåäøèõ â ìíîæåñòâî Mi , ïåðåñåêàåò õîòÿ áûîäíó èç åãî äóã âî âíóòðåííåé òî÷êå. Ïîýòîìó n − m − ai íå ïðåâîñõîäèò ñóììû(ïî òî÷êàì ïåðåñå÷åíèÿ ïñåâäîïðÿìûõ, ðàñïîëîæåííûõ ñòðîãî âíóòðè îáëàñòè Di )óìåíüøåííûõ íà åäèíèöó êðàòíîñòåé, òî åñòün − m − ai 6m∑tij (j − 1),(2.35)j=2ãäå ÷åðåç tij îáîçíà÷åíî êîëè÷åñòâî òî÷åê ïåðåñå÷åíèÿ êðàòíîñòè j â îáëàñòè Di .Òîãäàm ∑mm∑∑if=tj (j − 1) +cj (j − 1) + m,(2.36)∑mi=1 j=2j=2 ýòî êîëè÷åñòâî òî÷åê ïåðåñå÷åíèÿ íà ïëîñêîñòè RP2 êðàòíîñòèòàê êàê cj +j, îòëè÷íûõ îò òî÷êè O.

Çàìåòèì, ÷òîii=1 tjm∑cj (j − 1) = m(n − m),(2.37)j=2òàê êàê êàæäàÿ èç îñòàâøèõñÿ ïñåâäîïðÿìûõ ïåðåñåêàåòñÿ ñ êàæäîé èç m ïñåâäîïðÿìûõ l1 . . . , lm . Èç ðàâåíñòâ (2.36) è (2.37) ñëåäóåò:f − m(n − m + 1) =m ∑m∑i=1 j=226tij (j − 1).(2.38)Ñëîæèì íåðàâåíñòâà (2.35) ïî âñåì i = 1, . . . , m è ñëîæèì c (2.34):m(n − m + 1) 6m ∑m∑tij (j − 1) + 2(c2 + . . . + cm ).(2.39)i=1 j=2Ïîäñòàâèì â (2.39) ðàâåíñòâî (2.38) è âûðàçèì f :f > 2m(n − m + 1) − 2(c2 + . .

. + cm ).(2.40)Îáîçíà÷èì ÷åðåç s ñóììó c2 + . . . + cm−1 . Èç ðàâåíñòâà (2.37) è íåðàâåíñòâàc2 + 2c3 + . . . + (m − 2)cm−1 > sèìååì:m(n − m) − s.m−1Ïîäñòàâèì (2.41) â (2.40), èñïîëüçóÿ ñóììó s :cm 6(2.41)2m(n − m)2s2m(n − m)(m − 2)m−2+=+ 2m − 2s.m−1m−1m−1m−1(2.42)Ïî ëåììå 2.6 âåðíî íåðàâåíñòâîf > 2m(n − m + 1) − 2s −f >1+n(n − 1) m − 2+s.mm(2.43)Óìíîæèì íåðàâåíñòâî (2.42) íà m − 1, íåðàâåíñòâî (2.43) íà 2m è ñëîæèì:(3m − 1)f > 2m(n − m)(m − 2) + 2m2 + 2n(n − 1).Îòñþäà ïîëó÷àåì òðåáóåìîå íåðàâåíñòâî.Íàéäåì âñå ïàðû ÷èñåë (n, m) ñ m > 4 è n > m + 1, ïðè êîòîðûõòåîðåìà 2.4 ñèëüíåå íåðàâåíñòâà (2.19) òåîðåìû 2.3.

Ñðàâíèì ïðàâûå ÷àñòè ñîîòâåòñòâóþùèõ íåðàâåíñòâ íà ÷èñëà îáëàñòåé fÇàìå÷àíèå 2.3.n2 + (m2 − 2m − 1)n − m3 + 3m2n2 − n + 2m>⇔ (m−2)(n−m−1)(2n−m2 −m) < 0.3m − 1m+3Ñëåäîâàòåëüíî, ïðè m + 1 < n <ðåìû 2.3.m2 +m2òåîðåìà 2.4 ñèëüíåå íåðàâåíñòâà (2.19) òåî-Åñëè äëÿ (n, m, f ) êîíôèãóðàöèè ïñåâäîïðÿìûõ f = 2òî êîíôèãóðàöèÿ ïðèíàäëåæèò îäíîìó èç ñëåäóþùèõ òèïîâ.Çàìå÷àíèå 2.4.1.(n2 −n+2mm+3n = m + 1, m > 2, f = 2n − 2, t2 = m, t3 = . . .