Теормин (2012) (1133351), страница 3
Текст из файла (страница 3)
. . , xn )íàçûâàåòñÿöåïíîé (öèêëè÷åñêîé)ôóíêöèåé äëèíût,åñëè ååñîêðàùåííàÿ ÄÍÔ ñ ãåîìåòðè÷åñêîé òî÷êè çðåíèÿ ïðåäñòàâëÿåò ñîáîé öåïü (ñîîòâåòñòâåííîN1 , N2 , . . . , Nt êóáà Bn .n ∈ N, n ≥ 3, â P2 (n) ñóùåñòâóþò ÔÀË f 0 è f 00 ,èìåþùèå îáùóþ ïðîñòóþ èìïëèêàíòó K , êîòîðàÿ âõîäèò â ÄÍÔ ΣM îäíîé, íî íå âõîäèò â000ÄÍÔ ΣM äðóãîé èç ýòèõ ÔÀË è äëÿ êîòîðîé Sn−3 (NK , f ) = Sn−3 (NK , f ).Ýòàïû äîêàçàòåëüñòâà. Ïîñòðîèì öåïíóþ ôóíêöèþ f ÷åòíîé äëèíû t = 2k ≥ 2n − 2 ≥ 4,000äàëåå ïîëó÷èì öåïíûå ÔÀË f , fíå÷åòíîé äëèíû 2k − 1 óäàëåíèåì ïåðâîé è ïîñëåäíåéâåðøèíû èç ÔÀË f . Òîãäà êàæäîå ðåáðî Ni , ãäå i = 2, . . .
, t − 1, âõîäèò â ÄÍÔ ΣM îäíîé èçíèõ, íî íå âõîäèò â ÄÍÔ ΣM äðóãîé.  êà÷åñòâå NK âîçüìåì Nk . êà÷åñòâå f íàäî áðàòü ÔÀË äëèíû (2n − 2), ó êîòîðîé Nf èç òàêèõ íàáîðîâ, ãäå ïåðâûåi ïåðåìåííûõ ðàâíû 1, îñòàëüíûå íóëè, i ∈ [1, n] è îòðèöàíèé ê ýòèì íàáîðàì (âñåãî 2n − 1íàáîðîâ). Åå ðåáðà, (2n − 2) øòóêè, áóäóò èìåòü âèä {aj , aj+1 }. öèêë) èçtïîñëåäîâàòåëüíî ñîåäèíåííûõ ðåáåðÒåîðåìà (Æóðàâëåâà).Ïðè ëþáîì721Ïàðó(V, E),ãäåE ñî÷åòàíèå (ñ âîçìîæíûìè ïîâòîðåíèÿìè) íàä ìíîæåñòâîì óïîðÿäî-÷åííûõ è íåóïîðÿäî÷åííûõ ïàð èçâåðøèíV = V (G)V,áóäåì, êàê îáû÷íî, íàçûâàòüè ìíîæåñòâîì ðåáåðãðàôîìñ ìíîæåñòâîìE = E(G).îðèåíòèðîâàííûìè ðåáäóãàìè (ñîîòâåòñòâåííî íåîðèåíòèðîâàííûìè ðåáðàìè), îäèíàêîâûåïàðû ïàðàëëåëüíûìè ðåáðàìè (äóãàìè), äóãè, îòëè÷àþùèåñÿ ïîðÿäêîì âåðøèí, ïðîòèâîïîëîæíûìè äóãàìè, à ïàðû èç ñîâïàäàþùèõ âåðøèí ïåòëÿìè.
Ãðàô èç îðèåíòèðîâàííûõ (íåîðèåíòèðîâàííûõ) ðåáåð ñ÷èòàåòñÿ îðèåíòèðîâàííûì (ñîîòâåòñòâåííî íåîðèåíòèðîâàííûì).Áóäåì ãîâîðèòü, ÷òî îðèåíòèðîâàííîå (íåîðèåíòèðîâàííîå) ðåáðî èíöèäåíòíî ñîñòàâëÿÓïîðÿäî÷åííûå (íåóïîðÿäî÷åííûå) ïàðû âåðøèí íàçûâàþòñÿðàìèèëè, èíà÷å,(u, v) èñõîäèò èëè, èíà÷å, âûõîäèò èç âåðøèíû u è çàõîäèò èëè,v . ×èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå v (âõîäÿùèõ â v , âûõîäÿùèõþùèì åãî âåðøèíàì, à äóãàèíà÷å, âõîäèò â âåðøèíóèçv)â ãðàôåG,íàçûâàåòñÿèñõîäà) âåðøèíûvÂåðøèíà v íàçûâàåòñÿdG (v) = 0(ñîîòâåòñòâåííîñòåïåíüþGâ ãðàôå(ñîîòâåòñòâåííî ïîëóñòåïåíüþ çàõîäà, ïîëóñòåïåíüþè îáîçíà÷àåòñÿ ÷åðåçdG (v).èçîëèðîâàííîé âåðøèíîé (ñòîêîì, èñòîêîì)ãðàôàG,åñëè+d−G (v) = 0, dG (v) = 0).G0 = (V 0 , E 0 ) íàçûâàåòñÿ ïîäãðàôîì ãðàôà G = (V, E), åñëè V 0 ⊆ V è E 0 ⊆ E .000Ïðè ýòîì G ñ÷èòàåòñÿ ïîäãðàôîì ãðàôà G, íàòÿíóòûì íà ìíîæåñòâî âåðøèí V , åñëè E0âêëþ÷àåò â ñåáÿ âñå âõîäÿùèå â E ïàðû âåðøèí èç V .Ãðàôîñòîâíûì ïîäãðàôîì,Ïîäãðàô íàçûâàåòñÿåñëè îí ñîäåðæèò âñå âåðøèíû èñõîäíîãîãðàôà.e1 , e2 , .
. . , en , ãäå ei = (vi , vi+1 ) ∈ E(G) ïðè(v1 − vn+1 )-ïóòåì ãðàôà G. Ïðè ýòîì âåðøèíà v1 (vn+1 ) ñ÷èòàåòñÿ íà÷àëüíîé (ñîîòâåòñòâåííî êîíå÷íîé) âåðøèíîé ýòîãî ïóòè, âåðøèíû v2 , . . . , vn åãîâíóòðåííèìè âåðøèíàìè, à ÷èñëî n åãî äëèíîé. Åñëè âñå ðåáðà ïóòè ðàçëè÷íû (êàêÏîñëåäîâàòåëüíîñòüâñåõi, i ∈ [1, n],C,ñîñòîÿùàÿ èç ðåáåðíàçûâàåòñÿöåïüþ, à åñëè, êðîìå òîãî, ðàçëè÷ïðîñòîé öåïüþ. Åñëè íà÷àëüíàÿ è êîíå÷íàÿ âåðøèíû ïóòè (öåïè)C ñîâïàäàþò, òî C ñ÷èòàåòñÿ çàìêíóòûì ïóòåì (ñîîòâåòñòâåííî öèêëîì).
Öèêë, â êîòîðîìâñå âåðøèíû, êðîìå íà÷àëüíîé è êîíå÷íîé, ðàçëè÷íû, íàçûâàåòñÿ ïðîñòûì öèêëîì.Âåðøèíà u äîñòèæèìà èç âåðøèíû v â ãðàôå G, ãäå u, v ∈ V (G), åñëè u = v èëè â Gýëåìåíòû ñîîòâåòñòâóþùåãî ñî÷åòàíèÿ), òî îí íàçûâàåòñÿíû âñå åãî âåðøèíû, òî ñóùåñòâóåò(v − u)-öåïü.Câÿçíîé êîìïîíåíòîéãðàôà íàçûâàåòñÿ ãðàô, íàòÿíóòûé íà êëàññ ýêâèâàëåíòíîñòè ïîîòíîøåíèþ äîñòèæèìîñòè.|E(G)| − |V (G)| + |c(G)| ≥ 0.Ëåâàÿ ÷àñòü íàçûâàåòñÿöèêëîìàòè÷åñêèì ÷èñëîìãðàôàG.S , êîòîðîå ñîñòîèò èç ðåáåð ãðàôà G = (V, E) è îáëàäàåò òåì ñâîéñòâîì, ÷òîu, u ∈ V , äîñòèæèìà èç âåðøèíû v, v ∈ V , â ãðàôå G, íî íå äîñòèæèìà èç íåå â(V, E S), íàçûâàåòñÿ (u|v)-ñå÷åíèåì ãðàôà G.ÌíîæåñòâîâåðøèíàãðàôåÑå÷åíèå, êîòîðîå íå èìååò ñîáñòâåííûõ ïîäìíîæåñòâ, ÿâëÿþùèõñÿ ñå÷åíèåì, íàçûâàåòñÿòóïèêîâûì.Íåîðèåíòèðîâàííûé (îðèåíòèðîâàííûé) ãðàô, íå èìåþùèé öèêëîâ (ñîîòâåòñòâåííî îðè-àöèêëè÷åñêèì.Ãëóáèíà âåðøèíû v (ñîîòâåòñòâåííî èñõîäÿùàÿ ãëóáèíà) ìàêñèìàëüíàÿ äëèíà (u−v)-åíòèðîâàííûõ öèêëîâ), íàçûâàåòñÿ(ñîîòâåòñòâåííî(v − u)-)ïóòåé ãðàôàG,ãäåu îäèí èç èñòîêîâ (ñîîòâåòñòâåííî ñòîêîâ)Íåîðèåíòèðîâàííûé ñâÿçíûé àöèêëè÷åñêèé ãðàô íàçûâàåòñÿíîé âåðøèíîé (êîðíåì) íàçûâàåòñÿêîðíåâûì äåðåâîì,ëèñòüÿìè.äåðåâîìG.Äåðåâî ñ âûäåëåí-à âñå îòëè÷íûå îò êîðíÿ âåðøèíûñòåïåíè 1 ýòîãî äåðåâà ñ÷èòàþòñÿ åãîÎðèåíòèðîâàííûì äåðåâîìíàçûâàåòñÿ ãðàô, ïîëó÷àþùèéñÿ çàìåíîé â äåðåâå ðåáåðíà îðèåíòèðîâàííûå, âåäóùèå ê êîðíþ.Äåðåâî (îðèåíòèðîâàííîå äåðåâî)åòñÿ åãîîñòîâíûì ïîääåðåâîì,D,ÿâëÿþùååñÿ îñòîâíûì ïîäãðàôîì ãðàôàà äåðåâîD0 ,8êîòîðîå ïîëó÷àåòñÿ èçDG,íàçûâà-â ðåçóëüòàòå ¾ïîä-ñîåäèíåíèÿ¿ âñåõ íå âîøåäøèõ â íåãî ðåáåð G ê ñâîèì ¾íà÷àëüíûì¿ âåðøèíàì, íàääåðåâîìãðàôàîñòîâíûìG.Ãðàô, âåðøèíàì è (èëè) ðåáðàì êîòîðîãî ñîïîñòàâëåíû îïðåäåëåííûå ñèìâîëû (ïîìåòêè),ñ÷èòàåòñÿÃðàôûïîìå÷åííûì ãðàôîì.G0 = (V 0 , E 0 )G00 = (V 00 , E 00 ) íàçûâàþòñÿ èçîìîðôíûìè, åñëè ñóùåñòâóþò òà000000îòîáðàæåíèÿ ϕ : V → Vè ψ : E → E , ïðè êîòîðûõ âåðøèíû èèêèå âçàèìíîîäíîçíà÷íûåíåîðèåíòèðîâàííûå ðåáðà (äóãè) G' ïåðåõîäÿò â âåðøèíû è íåîðèåíòèðîâàííûå ðåáðà (ñîîòâåòñòâåííî äóãè)G00 ñ ñîõðàíåíèåì îòíîøåíèÿ èíöèäåíòíîñòè (ñîîòâåòñòâåííî èñõîäà, çàõîäà)âåðøèí è ðåáåð, à òàêæå âñåõ ïîìåòîê.|D(q)| ≤ 4q ,ãäå D(q) ìíîæåñòâî óïîðÿäî÷åííûõ îðèåíòèðîâàííûõ êîðíåq ðåáðàìè.000000Íàáîð âèäà G = (G; V ; V ), ãäå G ãðàô, à V è V âûáîðêè èç ìíîæåñòâà V (G) äëèíû p0è q ñîîòâåòñòâåííî, ïðè÷åì âûáîðêà V ÿâëÿåòñÿ âûáîðêîé áåç ïîâòîðåíèé, íàçûâàåòñÿ (p, q)ñåòüþ.
Ïðè ýòîì âûáîðêà V 0 (âûáîðêà V 00 ) ñ÷èòàåòñÿ âõîäíîé (ñîîòâåòñòâåííî âûõîäíîé)âûáîðêîé, à åå i-ÿ âåðøèíà íàçûâàåòñÿ i-ì âõîäíûì (ñîîòâåòñòâåííî âûõîäíûì) ïîëþñîìèëè, èíà÷å, i-ì âõîäîì (ñîîòâåòñòâåííî âûõîäîì).Èçâåñòíî, ÷òîâûõ äåðåâüåâ ñ íå áîëåå, ÷åìÑåòü, â êîòîðîé âõîäíàÿ è âûõîäíàÿ âûáîðêè ñîâïàäàþò (íå ñîâïàäàþò), íàçûâàåòñÿòüþ ñ íåðàçäåëåííûìè (ñîîòâåòñòâåííî ñ ðàçäåëåííûìè) ïîëþñàìè.Ìàòðèöà äîñòèæèìîñòè âûáîðêè V 0 èç âûáîðêè V 00 ìàòðèöà M , M ∈ B p,q ,êîòîðîéMij = 1,vj00åñëèÇàìåòèì òàêæå, ÷òîäîñòèæèìà èçvj00èäëÿèíà÷å.òðàíçèòèâíîñòü ðåôëåêñèâíîé ìàòðèöû M , M ∈ B m,m ,ìåñòî òîãäà è òîëüêî òîãäà, êîãäàñå-èìååòM2 = M.Ìàòðèöà äîñòèæèìîñòè âûõîäíîé âûáîðêè ñåòè èç åå âõîäíîé âûáîðêè íàçûâàåòñÿìàò-ðèöåé äîñòèæèìîñòè ýòîé ñåòè.Cèñòåìà èç âñåõ ÝÊ (ÝÄ), óïîðÿäî÷åííûõ ïî èõ íîìåðàì, íàçûâàåòñÿ êîíúþíêòèâíûì(ñîîòâåòñòâåííî äèçúþíêòèâíûì)Ôóíêöèÿ âèäàäåøèôðàòîðîìïîðÿäêà n._µn (x1 , .
. . , xn , y0 , . . . , y2n −1 ) =αn1xα1 · · · xn yν(α)íàçûâàåòñÿ ìóëü-α=(α1 ,...,αn )òèïëåêñîðíîé, ïåðåìåííûåxîòâåòñòâåííîy èíôîðìàöèîííûìè.Qn (Jn , µn ) áóäåì íàçûâàòü äåøèôðàòîðîì (ñî-íàçûâàþòñÿ àäðåñíûìè,Ñõåìó, êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀËäèçúþíêòèâíûì äåøèôðàòîðîì, ìóëüòèïëåêñîðîì)ýêâèâàëåíòíûìè.ïîðÿäêà n. Ñõåìû,ðåàëèçóþùèå ðàâíûå ñèñòåìû ôóíêöèé, íàçûâàþòñÿÈçîìîðôíûå ñõåìû âñåãäà ýêâèâàëåíòíû, è ïîýòîìó äëÿ ëþáîãî êîíå÷íîãî ìíîæåñòâà ñõåìUâûïîëíÿåòñÿ íåðàâåíñòâî||U|| ≤ |U|,ãäå||U|| ÷èñëî ïîïàðíî íåýêâèâàëåíòíûõ ñõåì âU.2Ëþáàÿ ïåðåìåííàÿxjèçXãëóáèíû 0ñ÷èòàåòñÿ ôîðìóëîéôîðìóëîé íàä áàçèñîì Á, êîòîðàÿ ðåàëèçóåò ôóíêöèþxj .èëè, èíà÷å, òðèâèàëüíîéÔîðìóëà ãëóáèíûq ðåêóðñèâíî.èçîìîðôíûìè, à ôîðìóëû F 0 è F 00 ,000ðåàëèçóþùèå ðàâíûå ôóíêöèè f è f , íàçûâàþòñÿ ðàâíûìè èëè, èíà÷å, ýêâèâàëåíòíûìè.000Ðàâåíñòâî âèäà t : F = F ñ÷èòàåòñÿ òîæäåñòâîì.Ðàíã R(F) ôîðìóëû F ðàâåí ÷èñëó ëèñòüåâ ñâÿçàííîãî ñ íåé äåðåâà D , åå ñëîæíîñòüL(F) ðàâíà ÷èñëó îñòàëüíûõ âåðøèí D, à åå ãëóáèíà D(F) ãëóáèíå åãî êîðíÿ.Ëåììà.
Äëÿ ôîðìóëû F, F ∈ U Φ , âûïîëíÿþòñÿ íåðàâåíñòâà R(F) = L&,∨ (F) + 1 ≤¾Ãðàôè÷åñêè¿ ñîâïàäàþùèå ôîðìóëû ñ÷èòàþòñÿL(F) + 1 ≤ 2D(F ) ,ãäåL&,∨ (F) ÷èñëî ÔÑ&è∨â ôîðìóëåF.Ýòàïû äîêàçàòåëüñòâà. Âû÷èñëèòü ÷èñëî ðåáåð, âõîäÿùèõ â âåðøèíû äåðåâà è âûõîäÿ-ùèõ èç âåðøèí è ïðèðàâíÿòü èõ. Âòîðîå ñîîòíîøåíèå èíäóêöèåé (íàèáîëüøèé ðàíã áóäåòïðè ïîëíîì äåðåâå èç áèíàðíûõ îïåðàöèé, è îí áóäåò2D ). Ñëåäñòâèå. D(F) ≥ dlog(L(F) + 1)e.Åñëè ïîçèöèîííóþ ïîäôîðìóëó ôîðìóëût,òî ýòî íàçûâàåòñÿÔîðìóëû èçíîâå òîæäåñòâU Φ,tKFçàìåíèòü ýêâèâàëåíòíîé, ó÷èòûâàÿ òîæäåñòâîýêâèâàëåíòíûì ïðåîáðàçîâàíèåì Fíà îñíîâåt.ïîëó÷àþùèåñÿ äðóã èç äðóãà ýêâèâàëåíòíûìè ïðåîáðàçîâàíèÿìè íà îñ-à òàêæå òîæäåñòâtAíàçûâàþòñÿ9ïîäîáíûìè.Ôîðìóëà, â êîòîðîé âñå ÔÑïîäíÿòûìè îòðèöàíèÿìè.Àëüòåðíèðîâàíèå Alt(F)&èçìåíåíèé òèïîâ ÔÑÒåîðåìà.åé ôîðìóëàè∨¬âñòðå÷àþòñÿ òîëüêî íàä ÁÏ, íàçûâàåòñÿFôîðìóëûñ ïîäíÿòûìè îòðèöàíèÿìè ìàêñèìàëüíîå ÷èñëîâ öåïÿõ äåðåâà, ñîîòâåòñòâóþùåãî ôîðìóëåF ñ ïîäíÿòûìè îòðèöàíèÿìèD(F 0 ) ≤ dlog(L(F) + 1)e + Alt(F).Äëÿ ëþáîé ôîðìóëûF0òàêàÿ, ÷òîôîðìóëîé ñèçUΦF.ñóùåñòâóåò ïîäîáíàÿÝòàïû äîêàçàòåëüñòâà.
Ïðîâåäåì äîêàçàòåëüñòâî èíäóêöèåé ïî ðàíãó. Äëÿ òðèâèàëüíîéôîðìóëû ïðèôîðìóëàFR=1óòâåðæäåíèå âûïîëíåíî. Ïóñêàé îíî âûïîëíåíî äëÿ ðàíãàrèìååò ðàíãa.è àëüòåðíèðîâàíèåêîíúþíêöèè ôîðìóë ìåíüøåãî ðàíãà, ó êîòîðûõ àëüòåðíèðîâàíèå íå áîëüøå1)}. dðàâíî ñóììå ãëóáèíûFèa − a0 . dir − 1.ÏóñòüÏðåäñòàâèì ôîðìóëó â âèäå äèçúþíêöèè èëè ãëóáèíàFi .tP2di ≤ 2d .a0 = max{0, (a −Äëÿ êàæäîé ôîðìóëûFii=1F̌iïîñòðîèì ïîäîáíóþ åéD(F̌i ) ≤ di + a0 . Óïîðÿäî÷èì ôîðìóëû ïî âîçðàñòàíèþäâîè÷íîå d-ÿðóñíîå äåðåâî, óäàëèâ íå èñïîëüçóåìûå ÔÑ.òàêóþ, ÷òîãëóáèíû è ïîäñòàâèì èõ â ïîëíîåÒîãäàD(F̌) ≤ d + a0 ,Ñëåäñòâèå.÷òî è òðåáîâàëîñü äîêàçàòü.Äëÿ ëþáîé ÝÊ èëè ÝÄD(K) = dlog(L(K) + 1)e,Kñóùåñòâóåò ïîäîáíàÿ ôîðìóëàK0òàêàÿ, ÷òîêîòîðàÿ ìèíèìàëüíà ïî ãëóáèíå.Ñëåäñòâèå.
Äëÿ ëþáîé ÄÍÔ èëè ÊÍÔ Uñóùåñòâóåò ôîðìóëàU 0 , ÷òî D(U 0 ) = dlog(L(U)+1) + 1e.3Ñèñòåìà òîæäåñòâτíàçûâàåòñÿ ïîëíîé, åñëè äëÿ ëþáûõ ýêâèâàëåíòíûõ ôîðìóëíàä Á èìååò ìåñòî âûâîäèìîñòü00F ⇒FF 00èF00.τÏðîèçâîëüíóþ êîíúþíêöèþ áóêâ, ñîäåðæàùóþ, â îáùåì ñëó÷àå, ïîâòîðÿþùèåñÿ èëè ïðî-òèâîïîëîæíûå áóêâû, áóäåì íàçûâàòüîáîáùåííîé ÝÊ (ÎÝÊ),à äèçúþíêöèþ òàêèõ êîíú-îáîáùåííîé ÄÍÔêàíîíè÷åñêîé ÎÝÊ (ñîîòâåòñòâåííî êàíîíè÷åñêîé ÎÄÍÔ), à ñîâåðøåííóþ ÄÍÔ è ôîðìóëó x1 x̄1 ñîâåðøåííûìèÎÄÍÔ.Ëåììà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
