Диссертация (1103424), страница 8
Текст из файла (страница 8)
Íàçîâ¼ì âåðøèíó ïðàâîé äîëè ïëîõîé äëÿ S , åñëè îíà èìååò áîëüøå2DK/M ñîñåäåé âíóòðè S , òî åñòü õîòÿ áû â 2 ðàçà áîëüøå, ÷åì â ñðåäíåì(ñì. ðèñ. 3.5). Íàçîâ¼ì âåðøèíó x ∈ S îïàñíîé äëÿ S , åñëè âñå å¼ ñîñåäèïëîõèå äëÿ S (ñì. ðèñ. 3.6). Íàêîíåö, íàçîâ¼ì ãðàô β -áåçîïàñíûì, åñëè âëþáîì S ðàçìåðà íå áîëüøå K íàéä¼òñÿ íå áîëüøå ÷åì βK îïàñíûõ äëÿ Sâåðøèí.
Áåçîïàñíîñòü ãðàôà è áóäåò ïðîìåæóòî÷íûì ñâîéñòâîì.Ñëåäóÿ ðàáîòå [12], äîêàæåì ñëåäóþùóþ ëåììó:37,S |S| < 2kÏëîõèå âåðøèíû{0, 1}<nÓ êàæäîé âåðøèíû D ñîñåäåé{0, 1}kÎïàñíàÿ âåðøèíàÐèñ. 3.6: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà: îïàñíûå âåðøèíû â ëåâîé äîëå ãðàôà.Ëåììà 3.2. Ïóñòü G ÿâëÿåòñÿ ãðàôîì-ýêñòðàêòîðîì ñ ïàðàìåòðàìè n,m, d, k , ε. Òîãäà ãðàô G ÿâëÿåòñÿ 2ε-áåçîïàñíûì.Äîêàçàòåëüñòâî. Âî-ïåðâûõ, çàìåòèì, ÷òî áåç îãðàíè÷åíèÿ îáùíîñòèìîæíî ñ÷èòàòü ðàçìåð S â òî÷íîñòè ðàâíûì K : ïîñêîëüêó îïàñíàÿ âåðøèíàäëÿ ïîäìíîæåñòâà ÿâëÿåòñÿ òàêæå îïàñíîé äëÿ îáúåìëþùåãî ìíîæåñòâà,òî âåðõíÿÿ îöåíêà íà ÷èñëî îïàñíûõ âåðøèí â îáúåìëþùåì ìíîæåñòâå ÿâëÿåòñÿ âåðíîé è äëÿ ïîäìíîæåñòâà.Âî-âòîðûõ, çàìåòèì, ÷òî èç ïðîñòûõ ñîîáðàæåíèé (ïðèíöèïà Äèðèõëå)ìîæíî âûâåñòè, ÷òî ÷èñëî ïëîõèõ âåðøèí íå ïðåâûøàåò ïîëîâèíû ðàçìåðà ïðàâîé äîëè.
Èñïîëüçîâàíèå ñâîéñòâà ýêñòðàêòîðà ïîçâîëÿåò óìåíüøèòü ýòó îöåíêó äî ε. Äåéñòâèòåëüíî, îáîçíà÷èâ ìíîæåñòâî ïëîõèõ âåðøèí çà Y è ïðåäïîëîæèâ, ÷òî |Y | = δM , ìû ïîëó÷èì, ÷òî äîëÿ ïëîõèõâåðøèí ðàâíà |Y |/M = δ , à äîëÿ ð¼áåð, èäóùèõ â ïëîõèå âåðøèíû, ò.å.|E(S, Y )|/|E(S, R)|, ïî îïðåäåëåíèþ ïëîõîé âåðøèíû íå ìåíüøå 2δ . Äàëåå,ïî îïðåäåëåíèþ ýêñòðàêòîðà èìååì, â ÷àñòíîñòè:|E(S, Y )| |Y |−< ε,|E(S, R)|Mîòêóäà 2δ − δ < ε è δ < ε, êàê è áûëî çàÿâëåíî.Íàêîíåö, ïîëó÷èì îöåíêó íà êîëè÷åñòâî îïàñíûõ âåðøèí.
Ïóñòü T ⊂ Såñòü ìíîæåñòâî âñåõ îïàñíûõ âåðøèí â S . Îáîçíà÷èì ÷åðåç β îòíîøåíèå|T |K . Âñå ð¼áðà èç T ïî îïðåäåëåíèþ âåäóò â ìíîæåñòâî ïëîõèõ âåðøèí Y ,ïîýòîìó |E(S, Y )| > |E(T, Y )| = |T | · D = βDK = β|E(S, R)|, îòêóäà38|E(S, Y )|/|E(S, R)| > β . Ïî îïðåäåëåíèþ ýêñòðàêòîðà ýòî îòíîøåíèå îòëè÷àåòñÿ îò |Y |/M = δ ìåíüøå, ÷åì íà ε, îòêóäà β < δ + ε < 2ε.
Òàêèìîáðàçîì, ÷èñëî îïàñíûõ âåðøèí â ìíîæåñòâå S íå ïðåâûøàåò 2εK , îòêóäàãðàô ÿâëÿåòñÿ 2ε-áåçîïàñíûì, ÷òî è òðåáîâàëîñü.Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà. Íàïîìíèì, ÷òî ìû ñ÷èòàåì, ÷òî äëèíà a ìåíüøå n, à C(a|b) = k − 1. Òàêæå áóäåì ñ÷èòàòü, ÷òî k < n, èíà÷åäëÿ âûïîëíåíèÿ òåîðåìû ìîæíî âçÿòü p = a.Ïî òåîðåìå 2.19 ñóùåñòâóåò ýêñòðàêòîð ñ ïàðàìåðàìè n, k , d = O(log n),m = k è ε = 1/n3 .
Ïðè÷èíû òàêîãî âûáîðà ε ñòàíóò ÿñíû ïîçäíåå. Îäèí èçòàêèõ ýêñòðàêòîðîâ èìååò ñëîæíîñòü íå áîëüøå 2 log n + O(1), ïîñêîëüêóäëÿ åãî îïèñàíèÿ äîñòàòî÷íî çàäàòü n è k : îñòàëüíûå ïàðàìåòðû ÿâëÿþòñÿ ôóíêöèÿìè îò ýòèõ, à ñâîéñòâî ýêñòðàêòîðà ÿâëÿåòñÿ ðàçðåøèìûì.Âñå ãðàôû ñ ïàðàìåòðàìè (n, m, d) ìîæíî ïåðåáðàòü â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå è ïðîâåðèòü íà ñâîéñòâî ýêñòðàêòîðà.
Ïåðâûé ïîëó÷åííûéýêñòðàêòîð áóäåò èìåòü çàÿâëåííóþ ñëîæíîñòü. Ðàçóìååòñÿ, òàêîé ïåðåáîðòðåáóåò îãðîìíûõ ðåñóðñîâ, ïîýòîìó ýêñòðàêòîð íå áóäåò ÿâíûì.Çàôèêñèðóåì íàéäåííûé ýêñòðàêòîð G. Áóäåì ñ÷èòàòü, ÷òî åãî ëåâàÿ÷àñòü èíäåêñèðóåòñÿ ñëîâàìè äëèíû ìåíüøå n (âêëþ÷àÿ a),2 à ïðàâàÿ÷àñòü ñëîâàìè äëèíû m = k (ñðåäè êîòîðûõ ìû áóäåì èñêàòü p).
Íàïîìíèì, ÷òî ìû îáîçíà÷àåì ÷åðåç Sb ìíîæåñòâî {x ∈ {0, 1}<n | C(x|b) < k}, èa ∈ Sb .Ïîñêîëüêó |Sb | < K , à ãðàô G ÿâëÿåòñÿ 2ε-áåçîïàñíûì, òî â ìíîæåñòâåSb ñîäåðæèòñÿ íå áîëüøå 2εK îïàñíûõ âåðøèí. Ìû äîêàæåì, ÷òî âåðøèíàa íå ìîæåò áûòü îïàñíîé, èíà÷å îíà èìååò ñëèøêîì ìàëåíüêóþ ñëîæíîñòü,à ðàç îíà íå îïàñíà, òî ó íå¼ åñòü õîðîøèé (ò.å. íå ïëîõîé) ñîñåä p, êîòîðûéóäîâëåòâîðÿåò âñåì òðåáîâàíèÿì.Áîëåå ïîäðîáíî, ïðåäïîëîæèì, ÷òî a íå ÿâëÿåòñÿ îïàñíîé âåðøèíîéäëÿ Sb .
Òîãäà ó íå¼ åñòü ñîñåä p, êîòîðûé íå ÿâëÿåòñÿ ïëîõèì äëÿ Sb(ñì. ðèñ. 3.7). Ïîêàæåì, ÷òî âñå òðåáîâàíèÿ òåîðåìû âûïîëíåíû.Äåéñòâèòåëüíî, äëèíà p ðàâíà k ïî ïîñòðîåíèþ, ïîýòîìó åãî ñëîæíîñòüíå ïðåâûøàåò k + O(1).Óñëîâíàÿ ñëîæíîñòü C(p|a) ëîãàðèôìè÷åñêàÿ: ïðè èçâåñòíîì a ñëîâî pçàäà¼òñÿ îïèñàíèåì ãðàôà G è íîìåðîì p ñðåäè ñîñåäåé a â ýòîì ãðàôå.Ñóùåñòâóåò 2n −1 ñëîâ òàêîé äëèíû, ïîýòîìó îäíà âåðøèíà îñòàíåòñÿ íå ïðîèíäåêñèðîâàííîé. Ýòîíå ïîâëèÿåò íà äàëüíåéøåå èçëîæåíèå.239Sb = {x | C(x|b) < k}Ïëîõèå âåðøèíû{0, 1}<nÓ êàæäîé âåðøèíû D ñîñåäåéa{0, 1}k íåîïàñíàÿ âåðøèíàp õîðîøèé ñîñåä aÐèñ.
3.7: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà: âûáîð p.Îïèñàíèå ãðàôà, êàê ìû óæå îòìå÷àëè, òðåáóåò 2 log n + O(1) áèòîâ, àçàïèñü íîìåðà p ñðåäè ñîñåäåé íå áîëüøå, ÷åì d = O(log n) áèòîâ.Íàêîíåö, ïîëó÷èì îöåíêó íà C(a|p, b). Ïîñêîëüêó m = k , à p íå ÿâëÿåòñÿ ïëîõèì äëÿ Sb , òî p èìååò ìåíüøå 2D ñîñåäåé â Sb . Ïðè èçâåñòíûõ n èb ìíîæåñòâî Sb ìîæíî ïåðå÷èñëÿòü, ïàðàëëåëüíî çàïóñêàÿ âñå ïðîãðàììûäëèíû ìåíüøå k è âûâîäÿ ïîëó÷åííûå ñëîâà äëèíû ìåíüøå n.
Åñëè òàêæå èçâåñòåí ãðàô, òî ìîæíî ïåðå÷èñëèòü è ìíîæåñòâî ïðîîáðàçîâ p âíóòðèSb . Òàêèì îáðàçîì, ñëîâî a çàäà¼òñÿ îïèñàíèåì ãðàôà (2 log n + O(1) áèòîâ,÷òî òàêæå âêëþ÷àåò îïèñàíèå n) è íîìåðîì a â ïîñëåäíåì ïåðå÷èñëåíèè(log(2D) = O(log n) áèòîâ).  ñóììå ïîëó÷àåòñÿ O(log n) áèòîâ, ÷òî è çàÿâëåíî â òåîðåìå.Òåïåðü äîêàæåì, ÷òî a íå ìîæåò áûòü îïàñíîé âåðøèíîé â Sb . Íàïîìíèì, ÷òî áåç îãðàíè÷åíèÿ îáùíîñòè ìû ñ÷èòàåì, ÷òî C(a|b) = k−1.
Ïî ëåììå 3.2 îïàñíûõ âåðøèí â Sb íå áîëüøå 2εK =2K/n3 . Ïðè èçâåñòíîì ãðàôå èèçâåñòíîì b ìíîæåñòâî îïàñíûõ âåðøèí ìîæíî ïåðå÷èñëèòü: çàïóñòèì ïåðå÷èñëåíèå Sb , è ïîñëå êàæäîãî íîâîãî ñëîâà áóäåì ïðîâåðÿòü (ïî îïðåäåëåíèþ) âñå óæå ïîëó÷åííûå ñëîâà íà îïàñíîñòü â äàííîì ãðàôå äëÿ òåêóùåãîïðèáëèæåíèÿ ê Sb . Åñëè êàêîå-òî ñëîâî îêàçàëîñü îïàñíûì äëÿ ïðèáëèæåíèÿ, òî îíî áóäåò îïàñíûì è äëÿ âñåãî Sb , ïîñêîëüêó ìíîæåñòâî îïàñíûõñëîâ ðàñò¼ò ñ ðîñòîì îáúåìëþùåãî ìíîæåñòâà. Òàêèì îáðàçîì, ïðè èçâåñòíîì b êàæäàÿ îïàñíàÿ âåðøèíà çàäà¼òñÿ îïèñàíèåì ãðàôà (2 log n + O(1)áèòîâ) è ñâîèì íîìåðîì â ïåðå÷èñëåíèè (log(2K/n3 ) = k − 3 log n + O(1)áèòîâ).
 ñóììå ïîëó÷àåòñÿ k − log n + O(1) áèòîâ, òàêèì îáðàçîì a íå ìîæåò áûòü îïàñíîé âåðøèíîé, ïîñêîëüêó å¼ ñëîæíîñòü îòíîñèòåëüíî b ðàâíà40k − 1, ÷òî áîëüøå k − log n + O(1) ïðè äîñòàòî÷íî áîëüøèõ n. Çàìåòèì, ÷òîçíà÷åíèå ε áûëî âûáðàíî èìåííî òàê, ÷òîáû ýòîò âûâîä áûë ñïðàâåäëèâ.Íà ýòîì äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà ïðè ïîìîùè ýêñòðàêòîðîâçàâåðøåíî.3.3Òåîðåìà Ìó÷íèêà äëÿ íåñêîëüêèõ óñëîâèé è ïðåôèêñíûå ýêñòðàêòîðû îðèãèíàëüíîé ñòàòüå [30] Àí.À. Ìó÷íèê äîêàçàë òàêæå ñëåäóþùååîáîáùåíèå òåîðåìû 3.1 íà ñëó÷àé íåñêîëüêèõ óñëîâèé:Òåîðåìà 3.3.
Ïóñòü äàíû äâîè÷íûå ñëîâà a, b è c è ÷èñëà n, k è l, äëÿêîòîðûõ âûïîëíåíî C(a) < n, C(a|b) < k è C(a|c) < l. Òîãäà ñóùåñòâóþòñëîâà p è q , îäíî èç êîòîðûõ ÿâëÿåòñÿ íà÷àëîì äðóãîãî, äëÿ êîòîðûõâûïîëíåíû íåðàâåíñòâà:••••••C(a|p, b) 6 O(log n);C(a|q, c) 6 O(log n);C(p) 6 k + O(log n);C(q) 6 l + O(log n);C(p|a) 6 O(log n);C(q|a) 6 O(log n).Ýòà òåîðåìà åù¼ áîëåå íåòðèâèàëüíà, ÷åì èñõîäíàÿ. Äåéñòâèòåëüíî, òåîðåìà ãëàñèò, ÷òî èíôîðìàöèÿ îá a, îòñóòñòâóþùàÿ â b è c, ìîæåò áûòü ïðåäñòàâëåíà äâóìÿ ñòðîêàìè, îäíà èç êîòîðûõ áóäåò ïðåôèêñîì äðóãîé, äàæååñëè b è c íèêàê íå ñâÿçàíû. Êîììóíèêàöèîííàÿ ñõåìà ïðîèëëþñòðèðîâàíàíà ðèñóíêå 3.8.
Èç òåîðåìû òàêæå ñëåäóåò, ÷òî ñóùåñòâóåò ïðîãðàììà äëèíû íå áîëüøå max{C(a|b), C(a|c)} + O(log n), ïåðåâîäÿùàÿ îäíîâðåìåííîb â a è c â a. Ýòîò ôàêò èíòåðåñåí äàæå áåç äîáàâëåíèÿ î òîì, ÷òî òàêàÿïðîãðàììà ìîæåò áûòü ïðîñòîé îòíîñèòåëüíî a.Îñîáåííî óäèâèòåëüíûì ïîñëåäíåå óòâåðæäåíèå ïðåäñòàâëÿåòñÿ â òàêîéñèòóàöèè: ïóñòü b è c ñóòü íåçàâèñèìûå (ò.å. dep(b, c) = 0) ñëîâà äëèíû nè ñëîæíîñòè òîæå n, à ñëîâî a ÿâëÿåòñÿ èõ ïîáèòîâîé ñóììîé: a = b ⊕ c.Òîãäà C(a|b) ≈ C(c|b) ≈ n (ïî îïðåäåëåíèþ íåçàâèñèìîñòè) è C(a|c) ≈C(b|c) ≈ n.
Íà ïåðâûé âçãëÿä êàæåòñÿ, ÷òî íåò èíîãî ñïîñîáà äîáèòüñÿ,÷òîáû C(a|p, b) 6 O(log n) è C(a|q, c) 6 O(log n), êðîìå êàê âûáðàòü p = c è41d1 O(log n)and3 O(log n)qlÀëèñà×àðëèad2 O(log n)Áîáp−qk−labcÐèñ. 3.8: Èëëþñòðàöèÿ ê òåîðåìå Ìó÷íèêà äëÿ íåñêîëüêèõ óñëîâèé. Áåç îãðàíè÷åíèÿîáùíîñòè k > l.
Àëèñà ïîëó÷àåò ïîäñêàçêó d1 è ïîñûëàåò ñîîáùåíèå q Áîáó è ×àðëè, àñîîáùåíèå p − q òîëüêî Áîáó. Áîá, ïîëó÷èâ ñîîáùåíèÿ b, p è ïîäñêàçêó d2 , âîññòàíàâëèâàåò a, à ×àðëè ïî ñîîáùåíèÿì c, q è ïîäñêàçêå d3 òîæå âîññòàíàâëèâàåò a.q = b, èëè ÷òî-òî î÷åíü ïîõîæåå. Îäíàêî, ñ ëîãàðèôìè÷åñêèìè ïîäñêàçêàìèìîæíî âûáðàòü îäíî è òî æå ñëîâî äëèíû ïðèìåðíî n â êà÷åòâå p è q .Àíàëîãè÷íûå óòâåðæäåíèÿ ìîãóò áûòü äîêàçàíû íå òîëüêî äëÿ äâóõ, íîè äëÿ íåñêîëüêèõ, è äàæå äëÿ ïîëèíîìèàëüíîãî ÷èñëà óñëîâèé. Ìû ïðèâåä¼ì ïîäðîáíîå äîêàçàòåëüñòâî òåîðåìû äëÿ äâóõ óñëîâèé ïðè ïîìîùèýêñòðàêòîðîâ, à çàòåì íàáðîñàåì ïëàí äîêàçàòåëüñòâà äëÿ ìíîãèõ óñëîâèé. Äëÿ äîêàçàòåëüñòâà íàì ïîòðåáóåòñÿ ñëåäóþùàÿ ìîäèôèêàöèÿ ïîíÿòèÿ ýêñòðàêòîðà (ñîîòâåòñòâóþùåå ñâîéñòâî íåîäíîêðàòíî óïîìèíàëîñü âëèòåðàòóðå, íî òåðìèí ââåä¼í òîëüêî â [63]):Îïðåäåëåíèå 3.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
