Введение в теорию игр (сторонняя методичка) (1184510), страница 46
Текст из файла (страница 46)
Ôóíêöèÿ Ìèíêîâñêîãî è ãîìåîìîðôèçì âûïóêëûõ êîìïàêòîâÏóñòü A − âûïóêëûé êîìïàêò â E m , ñîäåðæàùèé âíóòðè ñåáÿ íóëüâìåñòå ñ ε0 -îêðåñòíîñòüþ íóëÿ Oε0 . Îïðåäåëèì íà E m ôóíêöèþ Ìèíêîâñêîãî ìíîæåñòâà A()xpA (x) = inf t > 0 ∈ A . tÐàññìîòðèì åå ñâîéñòâà. Î÷åâèäíî, ÷òî pA (0) = 0, à ïðè x 6= 0 pA (x) > 0è íèæíÿÿ ãðàíü äîñòèãàåòñÿ, ïîñêîëüêó ìíîæåñòâî A îãðàíè÷åíî è çàìêíóòî.
Êðîìå òîãî, pA (x) ≤ 1 ⇔ x ∈ A. Ôóíêöèÿ pA (x) ïîëîæèòåëüíîîäíîðîäíà, ò.å. äëÿ ëþáîãî λ > 0() λxtpA (λx) = λ inf>0∈ A = λpA (x) ∀x ∈ E m .λtÄîêàæåì, ÷òî ôóíêöèÿ pA (x) ñóáàääèòèâíà, ò.å.pA (x + y) ≤ pA (x) + pA (y) ∀x, y ∈ E m .Äåéñòâèòåëüíî, âîçüìåì x, y 6= 0.
Âåêòîðx+ypA (x)xpA (y)y=·+·pA (x) + pA (y)pA (x) + pA (y) pA (x) pA (x) + pA (y) pA (y)260(Π.1)Ïðèëîæåíèåïðèíàäëåæèò ìíîæåñòâó A, ïîñêîëüêó ÿâëÿåòñÿ âûïóêëîé êîìáèíàöèåéâåêòîðîâ pAx(x) , pAy(y) èç A. Îòñþäà ïîëó÷àåì íåðàâåíñòâî (Ï.1).Äîêàæåì, ÷òî ôóíêöèÿ Ìèíêîâñêîãî íåïðåðûâíà. Äåéñòâèòåëüíî, äëÿëþáîãî x ∈ Oε0x|x||x|∈/ Oε0 ⇒≥ ε0 ⇒ pA (x) ≤.pA (x)pA (x)ε0Îòñþäà ñëåäóåò, ÷òî pA (x) íåïðåðûâíà â íóëå. Íåïðåðûâíîñòü ôóíêöèèpA (x) â ëþáîé òî÷êå x0 âûòåêàåò èç íåðàâåíñòâà ( ñóáàääèòèâíîñòü )|pA (x) − pA (x0 )| ≤ max[pA (x − x0 ), pA (x0 − x)] è åå íåïðåðûâíîñòè â íóëå.Ïóñòü âûïóêëûå êîìïàêòû A è B â E m ñîäåðæàòâíóòðåííèå òî÷êè. Òîãäà íàéäåòñÿ âçàèìíî îäíîçíà÷íîå è íåïðåðûâíîåîòîáðàæåíèå (ãîìåîìîðôèçì) A íà B.Äîêàçàòåëüñòâî.
Áåç ïîòåðè îáùíîñòè áóäåì ñ÷èòàòü, ÷òî íóëü ñîäåðæèòñÿ â A ∩ B âìåñòå ñî ñâîåé îêðåñòíîñòüþ Oε0 . Îïðåäåëèì îòîáðàæåíèåpA (x)τ : A → B, τ (0) = 0, τ (x) =x, x 6= 0,pB (x)Òåîðåìà Ï.2.ãäå pA (x), pB (x) − ôóíêöèè Ìèíêîâñêîãî ìíîæåñòâ A è B. Íåòðóäíîïðîâåðèòü, ÷òîpB (y)τ −1 (y) =ypA (y)− îòîáðàæåíèå, îáðàòíîå ê τ.
Ïîñêîëüêó ôóíêöèè pA (x), pB (x) íåïðåðûâíû, îòîáðàæåíèå τ (x) íåïðåðûâíî ïðè x 6= 0. Ïðîâåðèì íåïðåðûâíîñòüτ (x) â íóëå. Ìíîæåñòâî B îãðàíè÷åíî è ïîýòîìó íàéäåòñÿ òàêîå ÷èñëî α,÷òî äëÿ âñåõ x ∈ B |x| ≤ α. Ïîñêîëüêó pBx(x) ∈ B, pB|x|(x) ≤ α. Äëÿ ëþáîãîâåêòîðà x ∈ Oε0 âûïîëíåíî íåðàâåíñòâî pA (x) ≤ |x|(ñì. âûøå äîêàε0çàòåëüñòâî íåïðåðûâíîñòè ôóíêöèè pA (x)). Ñëåäîâàòåëüíî, äëÿ âñÿêîãîx ∈ Oε0pA (x)α|x||τ (x)| =|x| ≤.pB (x)ε0Ï4. Ñèìïëåêñû è òåîðåìà î íåïîäâèæíîé òî÷êåÏóñòü {x1 , ..., xn+1 } − ìíîæåñòâî âåêòîðîâ èç E m (n ≤ m), âûïóêëàÿ261Ïðèëîæåíèåîáîëî÷êà êîòîðîãîK = {x ∈ Em|x=n+1Xiλi x ,i=1n+1Xλi = 1, λi ≥ 0, i = 1, ..., n + 1}i=1èìååò ðàçìåðíîñòü n.
Òîãäà ìíîæåñòâî K íàçûâàåòñÿ ñèìïëåêñîì, ïîðîæäåííûì âåðøèíàìè x1 , ..., xn+1 . Äëÿ ñèìïëåêñà K áóäåì òàêæå èñïîëüçîâàòü îáîçíà÷åíèå K = x1 · · · xn+1 . Ðàçìåðíîñòü n îçíà÷àåò ëèíåéíóþíåçàâèñèìîñòü âåêòîðîâ xn+1 − x1 , ..., xn+1 − xn . Îòñþäà âûòåêàåò, ÷òîäëÿ âñÿêîãî x ∈ K êîýôôèöèåíòû λi (x), i = 1, ..., n + 1, â ðàçëîæåíèè xïî xi îïðåäåëåíû îäíîçíà÷íî è ÿâëÿþòñÿ íåïðåðûâíûìè ôóíêöèÿìè íàK.Âñÿêîå ìíîæåñòâî, ñîäåðæàùåå r ≤ n + 1 âåðøèí, ïîðîæäàåò (r − 1)ìåðíûé ñèìïëåêñ, íàçûâàåìûé ãðàíüþ ñèìïëåêñà K. Âåðøèíû x1 , ..., xn+1ÿâëÿþòñÿ íóëüìåðíûìè ãðàíÿìè. n-ìåðíàÿ ãðàíü ñîâïàäàåò ñ K. Îäíîìåðíûå ãðàíè xi xj , i 6= j, íàçûâàþòñÿ ðåáðàìè ñèìïëåêñà K.
Äèàìåòðñèìïëåêñà K îïðåäåëÿåòñÿ êàê ìàêñèìàëüíàÿ äëèíà åãî ðåáåð. Ïîäìíîæåñòâî K 0 ñèìïëåêñà K âèäà0K = {x ∈ Em|x=n+1Xi=1iλi x ,n+1Xλi = 1, λi > 0, i = 1, ..., n + 1}i=1íàçûâàåòñÿ îòêðûòûì ñèìïëåêñîì, ïîðîæäåííûì âåðøèíàìèx1 , ..., xn+1 . Äëÿ îòêðûòîãî ñèìïëåêñà áóäåì òàêæå èñïîëüçîâàòü îáîçíà÷åíèå K 0 = x1 · · · xn+1 . Íóëüìåðíûå ñèìïëåêñû ÿâëÿþòñÿ îòêðûòûìè.Îòêðûòûå ðåáðà áóäåì îáîçíà÷àòü ÷åðåç xi xj .Ïóñòü ñèìïëåêñ K òàêèì îáðàçîì ðàçáèò íà îòêðûòûå ïîïàðíî íåïåðåñåêàþùèåñÿ ñèìïëåêñû K1 , ..., Kp , ÷òî ëþáàÿ îòêðûòàÿ ãðàíü êàæäîãîñèìïëåêñà Kj ïðèíàäëåæèò ðàçáèåíèþ.
Òàêîå ðàçáèåíèå íàçûâàåòñÿ ñèìïëèöèàëüíûì. Ñèìïëåêñû Kj , ïðèíàäëåæàùèå K 0 , îáðàçóþò ðàçáèåíèåîòêðûòîãî ñèìïëåêñà.Íà ðèñ. Ï.1 ïðèâåäåí ïðèìåð ñèìïëèöèàëüíîãî ðàçáèåíèÿ äâóìåðíîãîñèìïëåêñà K íà äâà äâóìåðíûõ, ïÿòü îäíîìåðíûõ è ÷åòûðå íóëüìåðíûõîòêðûòûõ ñèìïëåêñà.262Ïðèëîæåíèåb x2@@@@by@@@@bb x3x1Ðèñ. Ï.1Ñîîòâåòñòâóþùèé îòêðûòûé ñèìïëåêñ K 0 ðàçáèò íà äâà äâóìåðíûõ èîäèí îäíîìåðíûé îòêðûòûõ ñèìïëåêñà.
Åñëè óäàëèòü èç ðàçáèåíèÿ íóëüìåðíûé ñèìïëåêñ y, à ðåáðà x2 y è yx3 çàìåíèòü íà ðåáðî x2 x3 , òî ïîëó÷èìïðèìåð íåñèìïëèöèàëüíîãî ðàçáèåíèÿ. Äëÿ ñèìïëèöèàëüíîãî ðàçáèåíèÿπ ÷åðåç δ(π) îáîçíà÷èì ìàêñèìàëüíûé äèàìåòð ñèìïëåêñîâ, âõîäÿùèõ âπ.n+1P i1Òî÷êà n+1x íàçûâàåòñÿ áàðèöåíòðîì ñèìïëåêñà K. Îïðåäåëèìi=1ñèìïëèöèàëüíîå ðàçáèåíèå, íàçûâàåìîå áàðèöåíòðè÷åñêèì, êàæäîå ðåáðî êîòîðîãî ñîåäèíÿåò áàðèöåíòðû ãðàíè è íåêîòîðîé åå ïîäãðàíè ñèìïëåêñà K. Äëÿ ñèìïëåêñà x1 x2 îíî ñîñòîèò èç âåðøèí x1 , x2 , åãî áàðèöåíòðà b = 12 (x1 + x2 ) è äâóõ îòêðûòûõ ðåáåð x1 b è bx2 . Ïðåäïîëîæèì, ÷òîáàðèöåíòðè÷åñêîå ðàçáèåíèå îïðåäåëåíî äëÿ ëþáîãî ñèìïëåêñà ðàçìåðíîñòè k ≤ n − 1.Îïðåäåëèì åãî äëÿ ñèìïëåêñà K ðàçìåðíîñòè n c áàðèöåíòðîì b.Ïóñòü π 0 − ñåìåéñòâî îòêðûòûõ ñèìïëåêñîâ, âõîäÿùèõ â áàðèöåíòðè÷åñêèå ðàçáèåíèÿ âñåõ (n − 1)-ìåðíûõ ãðàíåé ñèìïëåêñà K.
Âîçüìåìïðîèçâîëüíûé ñèìïëåêñ K 0 = y 1 · · · y l , l ≤ n èç π 0 . Ïðåäïîëîæèì ïîèíäóêöèè, ÷òî êàæäîå åãî ðåáðî y i y j ñîåäèíÿåò áàðèöåíòðû íåêîòîðîéãðàíè è åå ïîäãðàíè ñèìïëåêñà K. Íåòðóäíî âèäåòü, ÷òî àíàëîãè÷íûìñâîéñòâîì îáëàäàåò è ñèìïëåêñ y 1 · · · y l b. Ñîâîêóïíîñòü âñåõ òàêèõ ñèìïëåêñîâ y 1 · · · y l b è áàðèöåíòð b äîáàâèì ê ñåìåéñòâó π 0 .  ðåçóëüòàòåïîëó÷èì áàðèöåíòðè÷åñêîå ðàçáèåíèå π1 ñèìïëåêñà K.nÏîêàæåì, ÷òî δ(π1 ) ≤ n+1d, ãäå d − äèàìåòð ñèìïëåêñà K. Äåéñòâèòåëüíî, âîçüìåì ëþáîå ðåáðî b0 b00 ðàçáèåíèÿ π1 , ãäå áåç ïîòåðè îáùíîñòès+1b0 =r+11 X i 001 X jx, b =x , r < s ≤ n.s + 1 i=1r + 1 j=1263ÏðèëîæåíèåÒîãäàs+1 1 X|b0 − b00 | = (xi − b00 ) =s + 1i=1s+1 r+1 11 XX is(r + 1)dndj =(x − x ) ≤≤.s + 1 r + 1 (s + 1)(r + 1)n+1i=1 j=1nÈòàê, δ(π1 ) ≤ n+1d.
Åñëè êàæäûé ñèìïëåêñ, ïðèíàäëåæàùèé ðàçáèåíèþ π1 , ïîäâåðãíóòü áàðèöåíòðè÷åñêîìó ðàçáèåíèþ, ïîëó÷èì ñèìïëèn 2öèàëüíîå ðàçáèåíèå π2 , äëÿ êîòîðîãî δ(π2 ) ≤ ( n+1) d. Ïîâòîðÿÿ àíàëîãè÷íóþ ïðîöåäóðó k ðàç, ïîëó÷èì ñèìïëèöèàëüíîå ðàçáèåíèå πk ñn kδ(πk ) ≤ ( n+1) d.Òåîðåìà Ï.3 (ëåììà Øïåðíåðà). Ïóñòü π − ñèìïëèöèàëüíîåðàçáèåíèå n-ìåðíîãî ñèìïëåêñà K = x1 · · · xn+1 , à ôóíêöèÿ ν : K →{x1 , ..., xn+1 } óäîâëåòâîðÿåò óñëîâèþν(x) ∈ {xi | λi (x) > 0} ∀x ∈ K.Òîãäà íàéäåòñÿ òàêîé n-ìåðíûé ñèìïëåêñ y 1 · · · y n+1 ðàçáèåíèÿ π, ÷òîν(y i ) = xi , i = 1, ..., n + 1. ×èñëî òàêèõ ñèìïëåêñîâ íå÷åòíî.Äîêàçàòåëüñòâî.
Äëÿ n = 0 óòâåðæäåíèå òåîðåìû î÷åâèäíî. Ïðåäïîëîæèì, ÷òî îíà ñïðàâåäëèâà äëÿ (n − 1)-ìåðíûõ ñèìïëåêñîâ. ÏóñòüK1 , ..., Kp − n-ìåðíûå îòêðûòûå ñèìïëåêñû, âõîäÿùèå â ðàçáèåíèå π. Áóäåì ãîâîðèòü, ÷òî (n−1)-ìåðíàÿ ãðàíü y 1 · · · y n ñèìïëåêñà Kj = y 1 · · · y n+1îòìå÷åíà, åñëè ν(y i ) = xi , i = 1, ..., n.Åñëè ñèìïëåêñ Kj óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû, òî, ââèäóðàâåíñòâ ν(y i ) = xi , i = 1, ..., n + 1, îí èìååò ðîâíî îäíó îòìå÷åííóþãðàíü. Äåéñòâèòåëüíî, ëþáàÿ äðóãàÿ (n − 1)-ìåðíàÿ ãðàíü ñèìïëåêñà Kjñîäåðæèò âåðøèíó y n+1 . Íî ν(y n+1 ) = xn+1 è ýòà ãðàíü íå ÿâëÿåòñÿ îòìå÷åííîé. Ïóñòü ñèìïëåêñ Kj íå óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû èèìååò îòìå÷åííóþ ãðàíü y 1 · · · y n . Òîãäà îí èìååò ðîâíî äâå îòìå÷åííûåãðàíè. Äåéñòâèòåëüíî, ïî ïðåäïîëîæåíèþ ν(y i ) = xi , i = 1, ..., n è áåçïîòåðè îáùíîñòè ν(y n+1 ) = x1 .
Òîãäà (n − 1)-ìåðíûå ãðàíè y 1 · · · y n èy 2 · · · y n y n+1 ÿâëÿþòñÿ îòìå÷åííûìè.Ïóñòü σj − ÷èñëî îòìå÷åííûõ ãðàíåé ñèìïëåêñà Kj . Ïî äîêàçàííîìóσj ∈ {0, 1, 2} è σj = 1 òîëüêî â òîì ñëó÷àå, êîãäà ñèìïëåêñ Kj óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû. Ïîýòîìó îñòàëîñü äîêàçàòü, ÷òî îáùååpP÷èñëî îòìå÷åííûõ ãðàíåé χ =σj íå÷åòíî.  ýòîì ñëó÷àå îáÿçàòåëüíîj=1íàéäåòñÿ ñèìïëåêñ Kj , óäîâëåòâîðÿþùèé óòâåðæäåíèþ òåîðåìû.264ÏðèëîæåíèåÏóñòü V = y 1 · · · y n − êàêàÿ-ëèáî (n − 1)-ìåðíàÿ îòìå÷åííàÿ îòêðûòàÿ ãðàíü ñèìïëåêñà Kj .
Åñëè V ⊂ K\K 0 , òî V ïðèíàäëåæèò íåêîòîðîé(n − 1)-ìåðíîé ãðàíè ñèìïëåêñà K è ÿâëÿåòñÿ ãðàíüþ åäèíñòâåííîãî nìåðíîãî ñèìïëåêñà ðàçáèåíèÿ π. Ïðè ýòîì èç ðàâåíñòâ ν(y i ) = xi , i =def1, ..., n, ñëåäóåò, ÷òî V ⊂ W = x1 · · · xn . Äåéñòâèòåëüíî, åñëè áû ãðàíü Vïðèíàäëåæàëà äðóãîé ãðàíè ñèìïëåêñà K, ñêàæåì, x2 · · · xn+1 , òî ïî îïðåäåëåíèþ ôóíêöèè ν ðàâåíñòâî ν(y 1 ) = x1 áûëî áû íåâîçìîæíî.
Ïóñòü V6⊂ K\K 0 . Òîãäà V ÿâëÿåòñÿ îáùåé ãðàíüþ ðîâíî äâóõ n-ìåðíûõ ñèìïëåêñîâ, âõîäÿùèõ â ðàçáèåíèå π è â ñóììå χ îíà ó÷èòûâàåòñÿ äâàæäû.Ñëåäîâàòåëüíî, ÷èñëî χ ñðàâíèìî ïî ìîäóëþ 2 ñ ÷èñëîì (n − 1)-ìåðíûõñèìïëåêñîâ V = y 1 · · · y n ⊂ W, äëÿ êîòîðûõ ν(y i ) = xi , i = 1, ..., n. Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ, ïðèìåíåííîìó ê (n−1)-ìåðíîìó ñèìïëåêñóW, ýòî ÷èñëî íå÷åòíî. Ïîýòîìó ÷èñëî χ òàêæå íå÷åòíî.Òåîðåìà Ï.4 (Êíàñòåð, Êóðàòîâñêèé, Ìàçóðêåâè÷). Ïóñòü çàìêíóòûå ïîäìíîæåñòâà C1 , ..., Cn+1 ñèìïëåêñà K = x1 · · · xn+1 óäîâëåòâîðÿþò óñëîâèþxj1 · · · xjs ⊆ ∪sr=1 Cjr ∀ 1 ≤ j1 < j2 < ... < js ≤ n + 1.Òîãäà ìíîæåñòâà C1 , ..., Cn+1 èìåþò íåïóñòîå ïåðåñå÷åíèå.Äîêàçàòåëüñòâî.
Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü {πk } ïîñòðîåííûõðàíåå ñèìïëèöèàëüíûõ ðàçáèåíèé ñèìïëåêñà K, äëÿ êîòîðîé lim δ(πk ) =k→∞0. Îïðåäåëèì îòîáðàæåíèå ν : K → {x1 , ..., xn+1 } ñëåäóþùèì îáðàçîì.Äëÿ ëþáîãî x ∈ K ïóñòü{xj | λj (x) > 0} = {xj1 , ..., xjs }, j1 < j2 < ...
< js .Òîãäà ïî óñëîâèþ x ∈ ∪sr=1 Cjr . Ïîëîæèì ν(x) = xjt , ãäå t − ìèíèìàëüíîå ÷èñëî, äëÿ êîòîðîãî x ∈ ∪tr=1 Cjr . Îòìåòèì, ÷òî x ∈/ ∪t−1r=1 Cjrè, ñëåäîâàòåëüíî, x ∈ Cjt . Ïî ïðåäûäóùåé òåîðåìå ñóùåñòâóåò ñèìïëåêñy 1 (k) · · · y n+1 (k) ðàçáèåíèÿ πk , äëÿ êîòîðîãî ν(y i (k)) = xi , i = 1, ..., n + 1.Çàìåòèì, ÷òî äëÿ êàæäîãî âåêòîðà y i (k) ïî îïðåäåëåíèþ îòîáðàæåíèÿ νjt = i è ïîýòîìó y i (k) ∈ Ci , i = 1, ..., n + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
