Характеристики конечных метрических пространств, порожденных графами (1105193), страница 6
Текст из файла (страница 6)
Èç îïðåäåëåíèÿ ôóíêöèè f âòîðîå ðàâåíñòâî äëÿ i ̸= 1 ïåðåïèøåòñÿ òàê:f (xi )−f (yi ) = d(xi , y)+d(y, yi ) = d(xi , yi ), ò.ê. â ðàññìàòðèâàåìîì äåðåâå âåðøèíûxi , y è yi ïîñëåäîâàòåëüíûå âåðøèíû â ïóòè xi yiÒðåòüå ðàâåíñòâî äîêàçûâàåòñÿ àíàëîãè÷íî âòîðîìó, ïîñêîëüêó xi ∈ X , ym+l ∈Y , è òàê êàê y ëåæèò â ïóòè xi ym+l äëÿ i = 1, . . . m, l = 2, . . . n−m, ïî îïðåäåëåíèþôóíêöèè f èìååì f (xi ) − f (ym+l ) = d(xi , y) + d(ym+l , y) = d(xi , yj ).Ëåììà äîêàçàíà.33Âåðíåìñÿ ê äîêàçàòåëüñòâó òåîðåìû.
Ââåäåì íîâûå êîýôôèöèåíòû kv , êîòîðûåðàâíû 1 , åñëè ðåáðî vx âõîäèò â ïóòü xy , è −1, åñëè íå âõîäèò, òîãäà äëÿ ëþáûõ âåðøèí xi , ñìåæíûõ ñ x, è âåðøèí yj , ñìåæíûõ ñ y , âûïîëíÿåòñÿ ðàâåíñòâîd(xi , yj ) = d(x, y) − kxi d(xi , x) − kyj d(yj , y).Èñïîëüçóÿ ýòî ðàâåíñòâî, ââåäåííóþ 1-ëèïøèöåâó ôóíêöèþ, ìàêñèìèçèðóþùóþ ïî ëåììå 6 âûðàæåíèå (2.3.1), è ëåììó 4, ïîëó÷àåì:1−α∑kx d(x, xi )−= α d(x, y) −n i=1 imW (mαx , mαy )1−α∑m(1 − α)−kyj d(y, yj ) +d(x, y)−n j=1nm(n − m)(1 − α) ∑−kxi d(x, xi )−nmi=1mn1−α ∑(n − m)(1 − α)−kyj d(y, yj ) +d(x, y).n j=m+1n∑mÂòîðîå ñëàãàåìîå ñ ïÿòûì äàþò 1−αi=1 kxi d(x, xi ), òðåòüå ñ øåñòûì ñëàãàåm∑nìûå äàþò 1−αj=1 kyj d(y, yj ), ÷åòâåðòîå è ñåäüìîå (1 − α) d(x, y). Òàêèì îáðànçîì, ïîëó÷àåì:W (mαx , mαy ) = d(x, y)−1−α∑1−α∑−kx d(x, xi ) −ky d(y, yj ).m i=1 in j=1 jmnÏîäñòàâëÿåì ïîëó÷åííîå âûðàæåíèå â ôîðìóëó äëÿ α-êðèâèçíû Ðè÷÷è:∑m1−αi=1 kxi d(x, xi ) + nkα (x, y) =d(x, y)Òîãäà êðèâèçíà Ðè÷÷è ìåæäó òî÷êàìè x è y ðàâíà1−αm∑nkα (x, y)=α→1 1 − αk(x, y) = lim34j=1 kyjd(y, yj )( ∑)mn111∑=kx d(x, xi ) +ky d(y, yj ) .d(x, y) m i=1 in j=1 jÒàêèì îáðàçîì, ïîëó÷èëè ôîðìóëó:)1 ( 1 ∑1 ∑k(x, y) =kz · d(z, x) +kz · d(z, y) ,d(x, y) deg(x) z∼xdeg(y) z∼yãäå kz = 1 , åñëè ðåáðî xz âõîäèò â ïóòü xy , è kz = −1, åñëè íå âõîäèò.Òåîðåìà äîêàçàíà.2.4Ñëåäñòâèÿ èç ôîðìóëû êðèâèçíû Ðè÷÷è äëÿ âçâåøåííîãî äåðåâà2.4.1 Ñëó÷àé áèíàðíîãî äåðåâà ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé.Ñëåäñòâèå 1.
([1.4])Ðàññìîòðèì áèíàðíîå äåðåâî G = (V, E) ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé, ðàâíîé 1. Òîãäà2(1) êðèâèçíà Ðè÷÷è ìåæäó âåðøèíàìè x è y ñòåïåíè 1 ðàâíà k(x, y) = d(x,y);(2) êðèâèçíà Ðè÷÷è ìåæäó âåðøèíàìè x è y ñòåïåíè 1 è 3 ñîîòâåòñòâåííî2ðàâíà k(x, y) = 3 d(x,y);(3) êðèâèçíà Ðè÷÷è ìåæäó âåðøèíàìè x è y ñòåïåíè 3 ðàâíà k(x, y) =2− 3 d(x,y).2.4.2 Ñâÿçü ñòðóêòóðû áèíàðíîãî äåðåâà ñ êðèâèçíàìè Ðè÷÷è íà åãîâåðøèíàõ.Äëÿ ôîðìóëèðîâêè âòîðîãî ñëåäñòâèÿ èç òåîðåìû 2 ïîíàäîáÿòñÿ ñëåäóþùèå îïðåäåëåíèÿ:Îïðåäåëåíèå. Ðàññìîòðèì áèíàðíîå äåðåâî G ñ ïîñòîÿííîé âåñîâîé ôóíêöèåé,ðàâíîé 1, è çàíóìåðîâàííûìè âåðøèíàìè v1 , .
. . , vn .Ìàòðèöåé êðèâèçí Ðè÷÷èK = (kij ) äëÿ ýòîãî äåðåâà G íàçîâåì ìàòðèöó, ýëåìåíòàìè êîòîðîé ÿâëÿþòñÿêðèâèçíû Ðè÷÷è kij íà ïàðå âåðøèí äåðåâà G ñ íîìåðàìè i è j .35Îïðåäåëåíèå. Ãîâîðÿò, ÷òî äâå âåðøèíû áèíàðíîãî äåðåâà ñòåïåíè 1 îáðàçóþòóñû, åñëè îíè ñìåæíû îáùåé âåðøèíå ñòåïåíè 3.Î÷åâèäíî, ó ëþáîãî áèíàðíîãî äåðåâà ñ êîëè÷åñòâîì âåðøèí íå ìåíüøå 3 åñòüóñû.Ñëåäñòâèå 2. ([1.4]) Áèíàðíûåäåðåâüÿ èçîìîðôíû òîãäà è òîëüêî òîãäà, êîãäàïðè ïîñòîÿííîé âåñîâîé ôóíêöèè íà ðåáðàõ ìàòðèöû êðèâèçí Ðè÷÷è ðàâíû ïðèïîäõîäÿùåé íóìåðàöèè âåðøèí.2.4.3 Îöåíêà ñóììû êðèâèçí Ðè÷÷è íà ïàðàõ ñìåæíûõ âåðøèí äåðåâà.Ðàññìîòðèì åùå îäíî ñëåäñòâèå èç òåîðåìû 2.Ñëåäñòâèå 3. ([1.4])Ïóñòü (G, ω) âçâåøåííîå äåðåâî.
Òîãäà ñóììà êðèâèçííà âñåõ ïàðàõ ñìåæíûõ âåðøèí ýòîãî äåðåâà íå ïðåâîñõîäèò 2. Ðàâåíñòâî äîñòèãàåòñÿ, åñëè è òîëüêî åñëè âåñà âñåõ ðåáåð äåðåâà ðàâíû ìåæäó ñîáîé.2.5Äîêàçàòåëüñòâà ñëåäñòâèé2.5.1 Äîêàçàòåëüñòâî ñëåäñòâèÿ 1.Äîêàçàòåëüñòâî. (1) Åñëè x, y âåðøèíû ñòåïåíè 1, x′ âåðøèíà, ñìåæíàÿ ñx, y ′ âåðøèíà, ñìåæíàÿ ñ y , òî d(x, x′ ) = d(y, y ′ ) = 1. Ïî ôîðìóëå èç òåîðåìû2, èìååìk(x, y) =d(x, x′ ) + d(y, y ′ )2=.d(x, y)d(x, y)(2) Åñëè x, y âåðøèíû ñòåïåíè 1 è 3 ñîîòâåòñòâåííî, x′ âåðøèíà, ñìåæíàÿ ñx, à y1 , y2 , y3 âåðøèíû, ñìåæíûå ñ y , òî d(x, x′ ) = d(y, y1 ) = d(y, y2 ) = d(y, y3 ) =1.
Ïî ôîðìóëå èç òåîðåìû 2, èìååì3 d(x, x′ ) + d(y, y1 ) − d(y, y2 ) − d(y, y3 )2k(x, y) ==.3 d(x, y)3 d(x, y)36(3) Åñëè x, y âåðøèíû ñòåïåíè 3, x1 , x2 , x3 âåðøèíû, ñìåæíûå ñ x, à y1 , y2 , y3 âåðøèíû, ñìåæíûå ñ y , òî d(x, xi ) = d(y, yj ) = 1 äëÿ i, j = 1, 2, 3. Ïî ôîðìóëåèç òåîðåìû 2, èìååì(k(x, y) =1d(x, x1 ) + d(y, y1 ) − d(x, x2 ) − d(x, x3 )−3 d(x, y))2− d(y, y2 ) − d(y, y3 ) = −.3 d(x, y)Ñëåäñòâèå 1 äîêàçàíî.2.5.2 Äîêàçàòåëüñòâî ñëåäñòâèÿ 2.Äîêàçàòåëüñòâî. Ïóñòü äàíà ìàòðèöà K = (kij ) êðèâèçí Ðè÷÷è äåðåâà G.
Îáîçíà÷èì âåðøèíû äåðåâà íàòóðàëüíûìè ÷èñëàìè 1, . . . , n.Ðàññìîòðèì ñíà÷àëà ñëó÷àé, êîãäà â äåðåâå äâå âåðøèíû ñòåïåíè 1, òî åñòüäåðåâî ñîñòîèò èç îäíîãî ðåáðà.  ýòîì ñëó÷àå ìàòðèöà êðèâèçí Ðè÷÷è áóäåòñîäåðæàòü òîëüêî íåîòðèöàòåëüíûå âåëè÷èíû è èìåòü âèä:(0 2)2 0.Ðàññìîòðèì âòîðîé ñëó÷àé, êîãäà â äåðåâå òðè âåðøèíû ñòåïåíè 1, òîãäà â ýòîìäåðåâå ðîâíî îäíà âåðøèíà ñòåïåíè 3.  ýòîì ñëó÷àå, â ñèëó ñëåäñòâèÿ 1, ìàòðèöàáóäåò ñîäåðæàòü òîëüêî íåîòðèöàòåëüíûå âåëè÷èíû.
Êðèâèçíû íà ïàðå âåðøèíñòåïåíè 1 ðàâíû 1, à íà ïàðå âåðøèí, îäíà èç êîòîðûõ ñòåïåíè 3, à âòîðàÿ ñòåïåíè1, ðàâíû 2/3. Òîãäà, ñ òî÷íîñòüþ äî íóìåðàöèè âåðøèí, ìàòðèöà K áóäåò èìåòüñëåäóþùèé âèä:0 1 11 0 11 1 0232323372323.230Î÷åâèäíî, ÷òî âåðøèíà ñòåïåíè 3 òà, ó êîòîðîé â ñòîëáöå è ñòðîêå ñòîÿò 2/3.Åñëè âåðøèí ñòåïåíè 1 áîëüøå òðåõ, òî âåðøèí ñòåïåíè 3 áîëüøå îäíîé, è âìàòðèöå K ïîÿâëÿþòñÿ îòðèöàòåëüíûå ýëåìåíòû.
Ïðåäúÿâèì àëãîðèòì, ïîçâîëÿþùèé îïðåäåëèòü äëÿ êàæäîé âåðøèíû ñòåïåíè 1 åäèíñòâåííóþ ñìåæíóþ ñ íåéâåðøèíó ñòåïåíè 3, à äëÿ êàæäîé âåðøèíû ñòåïåíè òðè ñìåæíûå ñ íåé âåðøèíû,òàêèì îáðàçîì âîññòàíàâëèâàÿ ìàòðèöó ñìåæíîñòè.Ñíà÷àëà íàõîäèì â ìàòðèöå ýëåìåíò kij = 1. Ýòîò ýëåìåíò ñóùåñòâóåò, òàê êàêâ áèíàðíîì äåðåâå åñòü óñû. Ñîãëàñíî ñëåäñòâèþ 1, èìååì ëèáî k(x, y) =ëèáî k(x, y) =23 d(x,y)2d(x,y)= 1,2= 1, ëèáî k(x, y) = − 3 d(x,y)= 1. Âòîðîé è òðåòèé ñëó÷àéíåâîçìîæíû, èíà÷å d(x, y) = ±2/3.  ïåðâîì ñëó÷àå d(x, y) = 2, ýòî îçíà÷àåò,÷òî x è y , âåðøèíû ñòåïåíè 1, ñîåäèíåíû äâóìÿ ðåáðàìè.
Èòàê, íîìåðà i è j íîìåðà âåðøèí ñòåïåíè 1, îáðàçóþùèõ óñû. Òåïåðü íàäî íàéòè âåðøèíó ñòåïåíè 3, ñìåæíóþ âåðøèíàì óñîâ i è j . Êðèâèçíà íà ïàðå âåðøèí i è ñìåæíîé ñíåé âåðøèíå ñòåïåíè 3, ïî ôîðìóëå èç Ñëåäñòâèÿ 1, ðàâíà 2/3. ×òîáû íàéòè ýòóâåðøèíó íàéäåì â i-ñòðîêå ýëåìåíòû, ðàâíûå 2/3. Êðèâèçíå, ðàâíîé 2/3, ñîîòâåòñòâóåò âåðøèíà ñòåïåíè 3, ðàññòîÿíèå äî êîòîðîé îò âåðøèíû i ðàâíî 1 ðåáðó, ëèáîâåðøèíû ñòåïåíè 1, ðàññòîÿíèå äî êîòîðûõ îò âåðøèíû i ðàâíî 3. Äëÿ óñîâ i è jòàêàÿ âåðøèíà ñòåïåíè 1 åäèíñòâåííà, ïîýòîìó íàäî îòëè÷èòü âåðøèíó ñòåïåíè 1îò âåðøèíû ñòåïåíè 3.
Ïî ïðåäïîëîæåíèþ, äåðåâî G èìååò íå ìåíåå äâóõ âåðøèíñòåïåíè 3, ïîýòîìó ñóùåñòâóåò åùå õîòÿ áû îäíà âåðøèíà ñòåïåíè 3, ñìåæíàÿ ñäàííîé. Ñëåäîâàòåëüíî, â ñòîëáöå, ñîîòâåòñòâóþùåì âåðøèíå ñòåïåíè òðè, åñòü îòðèöàòåëüíûå ÷èñëà (êàê ìèíèìóì îäíî, ðàâíîå −2/3). Òàêèì îáðàçîì, îïðåäåëèëèíîìåð (ïóñòü m) âåðøèíû ñòåïåíè 3, ñîñåäíåé ñ âåðøèíàìè i è j . Äëÿ óäîáñòâàîòìåòèì â ìàòðèöå ñòîëáöû è ñòðîêè, ñîäåðæàùèå ýëåìåíòû kij , kji , kim , kmi , kjm ,kmj , òî åñòü ñîîòâåòñòâóþùèå âåðøèíàì i, j , m.Äàëåå, ðàññìîòðèì âåðøèíó ñòåïåíè 3, ñîñåäíþþ ñ m.
Îáîçíà÷èì åå l. Íàéäåìñîñåäíèå âåðøèíû ñ âåðøèíîé l. Âñåãî òàêèõ âåðøèí òðè. Îäíà èç íèõ ýòîâåðøèíà m, âîçìîæíû òðè âàðèàíòà: îáå îñòàâøèåñÿ ñìåæíûå âåðøèíû ñòåïåíè 1;îáå îñòàâøèåñÿ âåðøèíû ñòåïåíè 3; îäíà èç îñòàâøèõñÿ âåðøèí ñòåïåíè 1, äðóãàÿ ñòåïåíè 3.  ïåðâîì ñëó÷àå ýòî äåðåâî ñ ÷åòûðüìÿ âåðøèíàìè ñòåïåíè 138è äâóìÿ âåðøèíàìè ñòåïåíè 3. Ýòîìó ñëó÷àþ ñîîòâåòñòâóåò äâà ýëåìåíòà 2/3 âñòðîêå ñ íîìåðîì l è ìàòðèöà 5 × 5.Åñëè â ñòðîêå ñ íîìåðîì l ñîäåðæàòñÿ ðîâíî äâà ýëåìåíòà −2/3, òî ðåàëèçîâàëñÿ òðåòèé ñëó÷àé.  ýòîì ñëó÷àå, èùåì â ñòðîêå ñ íîìåðîì l êðèâèçíó, ðàâíóþ2/3 ýòî êðèâèçíà íà ïàðå âåðøèí äàííîé âåðøèíå l è ñîñåäíåé ñ íåé âåðøèíåñòåïåíè 1, è êðèâèçíó, ðàâíóþ −2/3 è ñòîÿùóþ â íåïîìå÷åííîì ñòîëáöå, ýòîêðèâèçíà íà ïàðå âåðøèí âåðøèíå l è ñîñåäíåé âåðøèíå ñòåïåíè 3.
Òàêèå ýëåìåíòû â ñòðîêå l åäèíñòâåííû. Äåéñòâèòåëüíî, ïîñìîòðèì ÷åìó ìîæåò ðàâíÿòüñÿêîëè÷åñòâî ðåáåð n ìåæäó âåðøèíàìè (îäíà èç êîòîðûõ l), äëÿ êîòîðûõ êðèâèçíàðàâíà 2/3. Ïîñêîëüêó deg l = 3, òî ïðèìåíèìû 2 è 3 ôîðìóëû èç ñëåäñòâèÿ 1, òîåñòü 2/3 = ±(2/3)n, ñëåäîâàòåëüíî, n = ±1. Ñëó÷àé n = −1 íåâîçìîæåí, ñëåäîâàòåëüíî, êðèâèçíà, ðàâíàÿ 2/3, äîñòèãàåòñÿ íà âåðøèíå ñòåïåíè 1, ñìåæíîé ñ l.Ìû ðàññìàòðèâàëè ñëó÷àé, êîãäà ó âåðøèíû l ñìåæíàÿ âåðøèíà ñòåïåíè 1 åäèíñòâåííàÿ, ïîýòîìó ñîîòâåòñòâèå ñìåæíîé ñ l âåðøèíû ñòåïåíè 1 è ýëåìåíòà 2/3â ìàòðèöå, ñòîÿùåãî â l-îé ñòðîêå, îïðåäåëåíî îäíîçíà÷íî. Àíàëîãè÷íî, ïîñìîòðèì ÷åìó ìîæåò ðàâíÿòüñÿ êîëè÷åñòâî ðåáåð ìåæäó âåðøèíàìè (îäíà èç êîòîðûõl), äëÿ êîòîðûõ êðèâèçíà ðàâíà −2/3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
