Диссертация (1137405), страница 14
Текст из файла (страница 14)
íÏÖÎÏ ÕÔ×ÅÒÖÄÁÔØ ÌÉÛØ, ÞÔÏ ÔÒÉ ÕÐÏÍÑÎÕÔÙÅ ÔÏÞËÉ ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ (ÉÌÉ, × ÔÅÒÍÉÎÁÈ Rn ÔÒÉ ×ÅËÔÏÒÁ ÌÅÖÁÔ ×ÏÄÎÏÊ ÐÌÏÓËÏÓÔÉ). îÏ ÜÔÏÇÏ ÄÏÓÔÁÔÏÞÎÏ.éÔÁË, ÓÆÏÒÍÕÌÉÒÕÅÍ ÐÏÓÌÅÄÎÀÀ ÁËÓÉÏÍÕ.ðÒÏÅËÔÉ×ÎÁÑ ÁËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ / ProjeÓtive Transfer Axiom (PT).äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn É ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) ÔÏÞËÉ (v), (v−S ) ÉwS ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ.÷ÏÏÂÝÅ ÇÏ×ÏÒÑ, × ÆÏÒÍÕÌÉÒÏ×ËÅ ÄÏÌÖÎÏ ÓÔÏÑÔØ (wS ), ÎÏ ÔÁÍ, ÇÄÅ ÜÔÏ ÎÅÓÏÚÄÁÅÔ ÐÕÔÁÎÉÃÙ, ÍÙ ÎÅ ÂÕÄÅÍ ÒÁÚÌÉÞÁÔØ ×ÅËÔÏÒ wS É ÅÇÏ ÐÒÏÅËÔÉ×ÉÚÁÃÉÀ.4.3.
ïÓÎÏ×ÎÁÑ ÔÅÏÒÅÍÁáËÓÉÏÍÙ NP, WAn É PT ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÐÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ ÐÒÉÄ×ÕÈ ÄÏÐÏÌÎÉÔÅÌØÎÙÈ ÏÇÒÁÎÉÞÅÎÉÑÈ.1. -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÓÌÁÂÏÊ ÁËÓÉÏÍÅ ÁÎÏÎÉÍÎÏÓÔÉ ÔÏÌØËÏ ÄÌÑ ÉÇÒ ÓÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ.2 ÷ÙÐÏÌÎÑÅÔÓÑ ÕÓÌÏ×ÉÅ ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÉÓÈÏÄÁ ÇÏÌÏÓÏ×ÁÎÉÑ.ôÅÐÅÒØ ×ÓÅ ÇÏÔÏ×Ï ÄÌÑ ÏÓÎÏ×ÎÏÊ ÔÅÏÒÅÍÙ ÜÔÏÇÏ ÒÁÚÄÅÌÁ.ôÅÏÒÅÍÁ 12. ðÕÓÔØ | ÐÒÏÅËÔÉ×ÎÙÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ ÍÎÏÖÅÓÔ×Å ÉÇÒ Ó ÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÕÓÌÏ×ÉÀ97ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÇÏÌÏÓÏ×ÁÎÉÑ.
ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn ÉPT, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ (v) = (v) .äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÏËÁÖÅÍ ÓÎÁÞÁÌÁ, ÞÔÏ ÐÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn É PT.óÐÒÁ×ÅÄÌÉ×ÏÓÔØ ÁËÓÉÏÍ NP, WAn ÄÏÓÔÁÔÏÞÎÏ ÐÒÏ×ÅÒÉÔØ ÄÌÑ ÏÂÙÞÎÏÇÏ ÉÎÄÅËÓÁ, ÞÔÏ É ÐÒÏÄÅÌÁÎÏ × ÔÅÏÒÅÍÅ 2 É ÐÒÅÄÌÏÖÅÎÉÉ 2 ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ.PT: ðÏ ÌÅÍÍÅ 1 ÏÂÙÞÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÕÒÁ×ÎÅÎÉÀi(v) − i(v−S ) =f (i; S ); ÅÓÌÉ i ∈ S ; −f (i; S ∪ {i});ÅÓÌÉ i ∈= S;ÉÌÉ, × ×ÅËÔÏÒÎÏÊ ÆÏÒÍÅ,(v) − (v−S ) = wS :óÌÅÄÏ×ÁÔÅÌØÎÏ, ×ÅËÔÏÒÙ (v), (v−S ) É wS ÌÉÎÅÊÎÏ ÚÁ×ÉÓÉÍÙ, Á ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÉÍ ÔÏÞËÉ ÐÒÏÅËÔÉ×ÎÏÇÏ ÐÒÏÓÔÒÁÎÓÔ×Á ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ.äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ. ðÕÓÔØ ÐÒÏÅËÔÉ×ÎÙÊ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔÁËÓÉÏÍÁÍ NP, WAn É PT.
âÕÄÅÍ ÄÏËÁÚÙ×ÁÔØ ÒÁ×ÅÎÓÔ×Ï (v) = P (v) ÉÎÄÕËÃÉÅÊÐÏ ÞÉÓÌÕ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ × v.ðÕÓÔØ × ÉÇÒÅ v ÏÄÎÁ ÍÉÎÉÍÁÌØÎÁÑ ×ÙÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ S , Ô.Å. v = uS . ÷ÜÔÏÍ ÓÌÕÞÁÅ ËÏÁÌÉÃÉÑ T ÂÕÄÅÔ ×ÙÉÇÒÙ×ÁÀÝÅÊ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÎÁÓÏÄÅÒÖÉÔ S , Ô.Å. ÓÏÄÅÒÖÉÔ × ÓÅÂÅ ×ÓÅÈ ÉÇÒÏËÏ× ÉÚ S . ðÏÜÔÏÍÕ, ÅÓÌÉ ÉÇÒÏË j ∈= S ,ÏÔ ÅÇÏ ×ÈÏÖÄÅÎÉÑ ÉÌÉ ÎÅ×ÈÏÖÄÅÎÉÑ × ËÏÁÌÉÃÉÀ T ÎÉÞÅÇÏ ÎÅ ÉÚÍÅÎÉÔÓÑ | T ÉT \ {j } ÂÕÄÕÔ ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÉÌÉ ÐÒÏÉÇÒÙ×ÁÀÝÉÍÉ ÏÄÎÏ×ÒÅÍÅÎÎÏ. úÎÁÞÉÔ,×ÓÅ ÉÇÒÏËÉ, ÎÅ ×ÈÏÄÑÝÉÅ × S , ÂÕÄÕÔ ÂÏÌ×ÁÎÁÍÉ × ÉÇÒÅ v.
ðÏÓËÏÌØËÕ É É PÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÁËÓÉÏÍÅ NP, ÔÏ ÅÓÌÉ i ∈= S , i(uS ) = iP (uS ) = 0.98ðÏ ÁËÓÉÏÍÅ WAn ÄÌÑ ÚÎÁÞÅÎÉÑ ËÏÏÒÄÉÎÁÔ i(uS ), ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÉÇÒÏËÁÍ,×ÈÏÄÑÝÉÍ × S ÒÁ×ÎÙ (É ÎÅ ÒÁ×ÎÙ 0, ÐÏÓËÏÌØËÕ i(uS ) ∈ RPn−1), Ô.Å.i(uS ) =1; ÅÓÌÉ i ∈ S ;0; ÅÓÌÉ i ∈= S:îÏ ÔÏ ÖÅ ÒÁÓÓÕÖÄÅÎÉÅ ÐÒÏÈÏÄÉÔ É ÄÌÑ ÐÒÏÅËÔÉ×ÎÏÇÏ -ÉÎÄÅËÓÁ, ÔÁËÖÅ ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÇÏ ÁËÓÉÏÍÅ WAn. úÎÁÞÉÔ i(uS ) = P (uS ).÷ ÞÁÓÔÎÏÓÔÉ, ÍÙ ÄÏËÁÚÁÌÉ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÌÑ uN | ÅÄÉÎÓÔ×ÅÎÎÏÊ ÉÇÒÙ Ó ÒÏ×ÎÏÏÄÎÏÊ ×ÙÉÇÒÙ×ÁÀÝÅÊ ËÏÁÌÉÃÉÅÊ, Ô.Å.
ÏÓÎÏ×ÁÎÉÅ ÉÎÄÕËÃÉÉ.2) ðÕÓÔØ × ÉÇÒÅ v ËÁË ÍÉÎÉÍÕÍ Ä×Å ÍÉÎÉÍÁÌØÎÙÅ ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉS É T.ðÏÓËÏÌØËÕ ÐÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ T P , ÔÏÞËÉ P (v),P (v−S ) É wS ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ É ÔÏÞËÉ P (v), P (v−T ) É wT ÌÅÖÁÔ ÎÁÏÄÎÏÊ ÐÒÑÍÏÊ. ïÂÏÚÎÁÞÉÍ ÜÔÉ ÐÒÑÍÙÅ ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ lS É lT .îÏ ÔÏÖÅ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ T P , ÐÏÜÔÏÍÕ ÔÏÞËÉ (v ), (v−S ) É wSÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ É ÔÏÞËÉ (v), (v−T ) É wT ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ. ðÏÓËÏÌØËÕ × ÉÇÒÁÈ v−S É v−T ÎÁ ÏÄÎÕ ËÏÁÌÉÃÉÀ ÍÅÎØÛÅ, ÞÅÍ × v ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀÉÎÄÕËÃÉÉ (v−S ) = P (v−S ) É (v−T ) = P (v−T ). ðÏÜÔÏÍÕ ÐÒÑÍÁÑ, ÎÁ ËÏÔÏÒÏÊÌÅÖÁÔ ÔÏÞËÉ (v), (v−S ) É wS | ÜÔÏ lS , Á ÐÒÑÍÁÑ, ÎÁ ËÏÔÏÒÏÊ ÌÅÖÁÔ ÔÏÞËÉ(v), (v−T ) É wT | ÜÔÏ lT .éÔÁË, ÐÒÑÍÙÅ lS É lT ÉÍÅÀÔ Ä×Å ÏÂÝÉÅ ÔÏÞËÉ (v) É P (v).
úÎÁÞÉÔ ÌÉÂÏÓÏ×ÐÁÄÁÀÔ ÔÏÞËÉ (ÔÏÇÄÁ ×ÓÅ ÄÏËÁÚÁÎÏ), ÌÉÂÏ ÐÒÑÍÙÅ (ÒÉÓ. 2.1, Ó. 100).äÏËÁÖÅÍ, ÞÔÏ ÐÒÑÍÙÅ lS É lT ÎÅ ÍÏÇÕÔ ÓÏ×ÐÁÄÁÔØ. äÏÓÔÁÔÏÞÎÏ ÐÒÏ×ÅÒÉÔØ,ÞÔÏ ÔÏÞËÉ P (v), wS É wT ÎÅ ÌÅÖÁÔ ÎÁ ÏÄÎÏÊ ÐÒÑÍÏÊ ÉÌÉ ÔÏ, ÞÔÏ ×ÅËÔÏÒÙ (v),wS É wT ÎÅ ÌÅÖÁÔ × ÏÄÎÏÊ ÐÌÏÓËÏÓÔÉ.ðÏÓËÏÌØËÕ S É T | ÍÉÎÉÍÁÌØÎÙÅ ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉ, ÔÏ ÎÉ ÏÄÎÁ ÉÚÎÉÈ ÎÅ ÍÏÖÅÔ ÓÏÄÅÒÖÁÔØÓÑ × ÄÒÕÇÏÊ.
ëÒÏÍÅ ÔÏÇÏ, ÐÏ ÓÌÅÄÓÔ×ÉÀ ÉÚ ÕÓÌÏ×ÉÑ99wS(v−T ) P (v−T )(v) P (v)wT(v−S ) P (v−S )òÉÓ. 2.1.ÏÄÎÏÚÎÁÞÎÏÓÔÉ ÒÅÛÅÎÉÑ S É T ÐÅÒÅÓÅËÁÀÔÓÑ, Ô.Å. ÓÕÝÅÓÔ×ÕÀÔ ÔÁËÉÅ ÉÇÒÏËÉ i,j É k, ÞÔÏ i ∈ S; T , j ∈ S \ T , k ∈ T \ S . òÁÓÓÍÏÔÒÉÍ ÍÁÔÒÉÃÕ, ÓÏÓÔÁ×ÌÅÎÎÕÀ ÉÚi, j É k-ÙÈ ËÏÏÒÄÉÎÁÔ ×ÅËÔÏÒÏ× (v), wS É wT : (v) −1 −1 i j (v ) −1 1 :k (v) 1 −1åÅ ÏÐÒÅÄÅÌÉÔÅÌØ ÒÁ×ÅÎ 2j (v) + 2k (v) > 0, ÐÏÓËÏÌØËÕ ÉÇÒÏË j ×ÈÏÄÉÔ × ÍÉÎÉÍÁÌØÎÕÀ ×ÙÉÇÒÙ×ÁÀÝÕÀ ËÏÁÌÉÃÉÀ S , É Ñ×ÌÑÅÔÓÑ ËÌÀÞÅ×ÙÍ × ÎÅÊ, ÐÏÜÔÏÍÕÉÍÅÅÔ ÎÅÎÕÌÅ×ÏÊ -ÉÎÄÅËÓ.òÁÚ ÏÐÒÅÄÅÌÉÔÅÌØ ÜÔÏÊ ÍÁÔÒÉÃÙ ÎÅ ÒÁ×ÅÎ 0, ÔÏ ×ÅËÔÏÒÙ, ÓÏÓÔÁ×ÌÑÀÝÉÅ ÅÅÌÉÎÅÊÎÏ ÎÅÚÁ×ÉÓÉÍÙ, ÚÎÁÞÉÔ, É ×ÅËÔÏÒÙ (v), wS É wT ÌÉÎÅÊÎÏ ÎÅÚÁ×ÉÓÉÍÙ ÉÎÅ ÍÏÇÕÔ ÌÅÖÁÔØ × ÏÄÎÏÊ ÐÌÏÓËÏÓÔÉ, ÚÎÁÞÉÔ, ÔÏÞËÉ (v), wS É wT ÎÅ ÌÅÖÁÔ ÎÁÏÄÎÏÊ ÐÒÑÍÏÊ.
äÏËÁÚÁÔÅÌØÓÔ×Ï ÚÁËÏÎÞÅÎÏ. ¥1004.4. áËÓÉÏÍÁÔÉËÉ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ -ÉÎÄÅËÓÁ É ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ÷ÅÒÎÅÍÓÑ ÔÅÐÅÒØ Ë ÎÅÐÒÏÅËÔÉ×ÎÙÍ ÉÎÄÅËÓÁÍ ×ÌÉÑÎÉÑ. óÕÍÍÁ ËÏÏÒÄÉÎÁÔ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ -ÉÎÄÅËÓÁ, ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ ÒÁ×ÎÁ 1, Ô.Å. N(v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ ÜÆÆÅËÔÉ×ÎÏÓÔÉ (E), ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÎÎÏÊ ÄÌÑ ÉÎÄÅËÓÏ× Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ:ÄÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPnnXi=1(v) = 1:úÁÍÅÔÉÍ, ÞÔÏ ÉÚ ×ÓÅÈ "ÐÒÅÄÓÔÁ×ÉÔÅÌÅÊ" ÐÒÏÅËÔÉ×ÎÏÇÏ -ÉÎÄÅËÓÁ N(v) |ÅÄÉÎÓÔ×ÅÎÎÙÊ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ ÜÆÆÅËÔÉ×ÎÏÓÔÉ. æÏÒÍÁÌØÎÏ, ÒÁÓÓÍÏÔÒÉÍ×ÓÅ ÉÎÄÅËÓÙ, ÐÒÏÅËÔÉ×ÉÚÁÃÉÑ ËÏÔÏÒÙÈ ÄÁÅÔ ÐÒÏÅËÔÉ×ÎÙÊ -ÉÎÄÅËÓ, Ô.Å.
∗−1(P ).ìÅÍÍÁ 6. óÒÅÄÉ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ ÉÚ ÍÎÏÖÅÓÔ×Á ∗−1(P ) ÔÏÌØËÏ ÎÏÒÍÉÒÏ×ÁÎÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ å.äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ N É ∗() =P . îÏ É ∗(N) = P . üÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÄÌÑ ÌÀÂÏÊ ÉÇÒÙ v ÚÎÁÞÅÎÉÑ ÉÎÄÅËÓÏ××ÌÉÑÎÉÑ (v) É N(v) ÐÒÏÐÏÒÃÉÏÎÁÌØÎÙ, Ô.Å. ÄÌÑ ËÁÖÄÏÊ ÉÇÒÙ v ÓÕÝÅÓÔ×ÕÅÔÔÁËÏÅ ÞÉÓÌÏ c(v), ÞÔÏ(v) = c(v) · N(v):óÌÏÖÉÍ ×ÓÅ ËÏÏÒÄÉÎÁÔÙ ×ÅËÔÏÒÏ× × ÏÂÅÉÈ ÞÁÓÔÑÈ ÒÁ×ÅÎÓÔ×Á É ×ÙÎÅÓÅÍ ÚÁÓËÏÂËÕ c(v):Xi∈N(v) =Xi∈N(c(v) · N(v)) = c(v)Xi∈NN(v):(2.9)óÕÍÍÙ × ÌÅ×ÏÊ É ÐÒÁ×ÏÊ ÞÁÓÔÉ ÆÏÒÍÕÌÙ (2.9) ÒÁ×ÎÙ ÅÄÉÎÉÃÅ, ÓÌÅÄÏ×ÁÔÅÌØÎÏc(v) = 1, Ô.Å.
(v ) = N(v). ¥101ðÏÜÔÏÍÕ ÄÌÑ ÔÏÇÏ, ÞÔÏÂÙ ÐÏÌÕÞÉÔØ ÁËÓÉÏÍÁÔÉËÕ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ, ÎÕÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ÔÒÉ ÁËÓÉÏÍÙ ÔÁË, ÞÔÏÂÙ ÉÚ ÎÉÈ ÓÌÅÄÏ×ÁÌÉÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÁËÓÉÏÍÙ ÄÌÑ P É ÄÏÂÁ×ÉÔØ ÁËÓÉÏÍÕ ÜÆÆÅËÔÉ×ÎÏÓÔÉ.áËÓÉÏÍÁ NP ÄÏÓÌÏ×ÎÏ ÐÏ×ÔÏÒÑÅÔ ÁËÓÉÏÍÕ NP ÄÌÑ ÏÂÙÞÎÏÇÏ -ÉÎÄÅËÓÁ. áËÓÉÏÍÁ WAn ÐÏ×ÔÏÒÑÅÔ ÁËÓÉÏÍÕ WAn ÄÌÑ P Ó ÔÏÊ ÌÉÛØ ÒÁÚÎÉÃÅÊ, ÞÔÏ ÉÎÄÅËÓÐÒÉÎÉÍÁÅÔ ÚÎÁÞÅÎÉÑ × Rn, Á ÎÅ × RPn−1.óÌÁÂÁÑ ÁËÓÉÏÍÁ ÁÎÏÎÉÍÎÏÓÔÉ / Weak Anonimity (WAn). äÌÑ ÌÀÂÏÊÏÌÉÇÁÒÈÉÞÅÓËÏÊ ÉÇÒÙ uS ∈ SGPn, É ÌÀÂÙÈ ÉÇÒÏËÏ× i; j ∈ S i(uS ) = j (uS ).áÎÁÌÏÇ ÁËÓÉÏÍÙ PT ÆÏÒÍÕÌÉÒÕÅÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ.áËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ (Tn).
äÌÑ ÌÀÂÏÊÉÇÒÙ v ∈ SGPn ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÏÅ ÐÏÌÏÖÉÔÅÌØÎÏÅ ÞÉÓÌÏ c(v), ÞÔÏ ÄÌÑ ÌÀÂÏÊËÏÁÌÉÃÉÉ S ∈ M (v)c(v)(v) − Ó(v−S )(v−S ) = wSóÌÅÄÕÀÝÁÑ ÔÅÏÒÅÍÁ ÈÁÒÁËÔÅÒÉÚÕÅÔ ÎÏÒÍÉÒÏ×ÁÎÎÙÊ -ÉÎÄÅËÓ.ôÅÏÒÅÍÁ 13. ðÕÓÔØ | ÉÎÄÅËÓ ×ÌÉÑÎÉÑ, ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ ÍÎÏÖÅÓÔ×Å ÉÇÒ ÓÓÉÍÍÅÔÒÉÞÎÙÍÉ ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÉÈ ÕÓÌÏ×ÉÀ ÏÄÎÏÚÎÁÞÎÏÓÔÉÇÏÌÏÓÏ×ÁÎÉÑ. ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn É Tn É E, ÅÓÌÉ ÉÔÏÌØËÏ ÅÓÌÉ (v) = (v).äÏËÁÚÁÔÅÌØÓÔ×Ï. äÌÑ ËÁÖÄÏÊ ÉÇÒÙ v ÎÏÒÍÉÒÏ×ÁÎÎÙÊ -ÉÎÄÅËÓ ÏÔÌÉÞÁÅÔÓÑÏÔ ÎÅÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÕÍÎÏÖÅÎÉÅÍ ÎÁ ËÏÎÓÔÁÎÔÕ.
÷ ×ÅËÔÏÒÎÏÊ ÆÏÒÍÅ(v):(2.10)N(v) = Pn(v)ii=1ðÏÓËÏÌØËÕ ÁËÓÉÏÍÙ NP É WAn ÏÓÔÁÎÕÔÓÑ ÓÐÒÁ×ÅÄÌÉ×Ù ÐÒÉ ÕÍÎÏÖÅÎÉÉ ÉÎ-ÄÅËÓÁ ×ÌÉÑÎÉÑ ÎÁ ËÏÎÓÔÁÎÔÕ, ÚÁ×ÉÓÑÝÕÀ ÔÏÌØËÏ ÏÔ ÉÇÒÙ, ÔÏ ÉÈ ÄÏÓÔÁÔÏÞÎÏ102ÐÒÏ×ÅÒÉÔØ ÄÌÑ ÏÂÙÞÎÏÇÏ -ÉÎÄÅËÓÁ. üÔÏ ÓÄÅÌÁÎÏ ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ × ÔÅÏÒÅÍÅ 2 ÉÐÒÅÄÌÏÖÅÎÉÉ 2.ðÅÒÅÊÄÅÍ Ë ÁËÓÉÏÍÅ Tn: ÐÏ ÌÅÍÍÅ 1 ÏÂÙÞÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÕÒÁ×ÎÅÎÉÀ(v) − (v−S ) = wS :(2.11)÷ÙÒÁÚÉÍ (v) ÉÚ ÕÒÁ×ÎÅÎÉÑ (2.10) É ÐÏÄÓÔÁ×ÉÍ × (2.11):N(v)à nXi=1!i(v) − N(v−S )à nXi=1!i(v−S ) = wS :óÌÅÄÏ×ÁÔÅÌØÎÏ, N(v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÅ Tn ÐÒÉ c(v) =Pni=1 i (v ).îÁËÏÎÅÃ, ÁËÓÉÏÍÅ ÎÏÒÍÉÒÏ×ËÉ ÎÏÒÍÉÒÏ×ÁÎÎÙÊ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÐÏÏÐÒÅÄÅÌÅÎÉÀ.ïÂÒÁÔÎÏ, ÐÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn É Tn. ÷ÜÔÏÍ ÓÌÕÞÁÅ ∗() ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, WAn É TP, Ô.Å.
ÐÏ ÔÅÏÒÅÍÅ 13ÓÏ×ÐÁÄÁÅÔ Ó ÐÒÏÅËÔÉ×ÎÙÍ -ÉÎÄÅËÓÏÍ. îÏ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ É ÁËÓÉÏÍÅ E, ÚÎÁÞÉÔ,ÐÏ ÌÅÍÍÅ 6 ÍÏÖÅÔ ÂÙÔØ ÔÏÌØËÏ ÎÏÒÍÉÒÏ×ÁÎÎÙÍ -ÉÎÄÅËÓÏÍ. ¥4.4.1. óÌÅÄÓÔ×ÉÅ: ÁËÓÉÏÍÁÔÉËÁ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ âÁÎÃÁÆÁëÁË É × ÓÌÕÞÁÅ ÏÂÙÞÎÏÇÏ -ÉÎÄÅËÓÁ, ÐÒÉ ÐÏÄÓÔÁÎÏ×ËÅ f (i; S ) = 1 ÉÚ ÏÂÙÞÎÏÇÏÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ -ÉÎÄÅËÓÁ ÐÏÌÕÞÁÅÔÓÑ ÎÏÒÍÉÒÏ×ÁÎÎÙÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ. ðÏÜÔÏÍÕ ÐÏÄÓÔÁ×É× f (i; S ) = 1 × ÁËÓÉÏÍÙ É ÓÕÚÉ× ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ (v) ÎÁÐÒÏÓÔÙÅ ÉÇÒÙ, ÐÏÌÕÞÉÍ ÁËÓÉÏÍÁÔÉËÕ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ.áËÓÉÏÍÙ NP, E É WAn ËÒÏÍÅ ÏÂÌÁÓÔÉ ÏÐÒÅÄÅÌÅÎÉÑ ÎÅ ÉÚÍÅÎÑÔÓÑ ÎÉËÁË. áËÓÉÏÍÕ WAn ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ ÂÏÌÅÅ ÓÉÌØÎÕÀ (ÓÍ.
ÕÔ×ÅÒÖÄÅÎÉÅ 1), ÚÁÔÏ ÏÂÝÅÐÒÉÎÑÔÕÀ ÁËÓÉÏÍÕ An. áËÓÉÏÍÁ Tn ÐÅÒÅÐÉÓÙ×ÁÅÔÓÑ ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ.103áËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ ÄÌÑ ÎÏÒÍÉÒÏ×ÁÎÎÏÇÏ ÉÎÄÅËÓÁ (Tn). äÌÑ ÌÀÂÏÊÉÇÒÙ v ∈ SGn ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÏÅ ÐÏÌÏÖÉÔÅÌØÎÏÅ ÞÉÓÌÏ c(v), ÞÔÏ ÄÌÑ ÌÀÂÏÊËÏÁÌÉÃÉÉ S ∈ M (v)c(v)(v) − Ó(v−S )(v−S ) = wS ;ÇÄÅ w | ×ÅËÔÏÒ ÄÏÈÏÄÏ× É ÐÏÔÅÒØ, ËÏÏÒÄÉÎÁÔÙ ËÏÔÏÒÏÇÏ ÒÁ×ÎÙwiS =1; ÅÓÌÉ i ∈ S ; −1;ÅÓÌÉ i ∈= SóÌÅÄÕÀÝÁÑ ÔÅÏÒÅÍÁ ÎÁÐÒÑÍÕÀ ÓÌÅÄÕÅÔ ÉÚ ÔÅÏÒÅÍÙ 13 É ÒÁÓÓÕÖÄÅÎÉÊ ÜÔÏÇÏÐÁÒÁÇÒÁÆÁ.ôÅÏÒÅÍÁ 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
