Диссертация (Индексы влияния, зависящие от предпочтений участников - аксиоматическое построение и методы вычисления), страница 10

äÌÑ ÌÀÂÙÈ ÉÇÒ v; w ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉS ∈ M (v) ∩ M (w) É ÌÀÂÏÇÏ i ∈ Ni(v) − i(v−S ) = i(w) − i(w−S ):áËÓÉÏÍÁ ÜË×É×ÁÌÅÎÔÎÁ ÏÂÙÞÎÏÊ ÁËÓÉÏÍÅ T É ÏÚÎÁÞÁÅÔ, ÞÔÏ ÐÏÔÅÒÉ ÉÇÒÏËÁ iÏÔ ×ÙÞÅÒËÉ×ÁÎÉÑ ËÏÁÌÉÃÉÉ ÎÅ ÚÁ×ÉÓÑÔ ÏÔ ÉÇÒÙ, × ËÏÔÏÒÏÊ ÜÔÏ ÐÒÏÉÓÈÏÄÉÔ.õÓÌÏ×ÉÅ ÓÉÍÍÅÔÒÉÞÎÏÓÔÉ ÄÏÈÏÄÏ×/ÐÏÔÅÒØ / Symmetric Gain-Loss(SymGL). 1) äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÙÈi; j ∈ S :i(v) − i(v−S ) = j (v) − j (v−S ):2) äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÙÈ i; j ∈= S :i(v) − i(v−S ) = j (v) − j (v−S ):áËÓÉÏÍÁ ÐÏÈÏÖÁ ÎÁ T É ÚÁÍÅÎÑÅÔ ÅÅ × ÎÅËÏÔÏÒÙÈ ÁËÓÉÏÍÁÔÉËÁÈ.

ïÎÁ ÏÚÎÁÞÁÅÔ, ÞÔÏ × ÒÁÍËÁÈ ËÏÎËÒÅÔÎÏÊ ÉÇÒÙ (× ÏÔÌÉÞÉÅ ÏÔ T, ÇÄÅ ÒÁÓÓÍÁÔÒÉ×ÁÀÔÓÑ ×ÓÅÉÇÒÙ ÓÒÁÚÕ) ÐÏÔÅÒÉ ÏÔ ×ÙÞÅÒËÉ×ÁÎÉÑ ËÏÁÌÉÃÉÉ S ÏÄÉÎÁËÏ×Ù ÄÌÑ ×ÓÅÈ ÉÇÒÏËÏ×,× S ×ÈÏÄÑÝÉÈ (ÞÁÓÔØ 1), Á ÄÌÑ ÉÇÒÏËÏ×, × S ÎÅ ×ÈÏÄÑÝÉÈ, ÏÄÉÎÁËÏ×Ù ÄÏÈÏÄÙ(ÞÁÓÔØ 2).õÓÌÏ×ÉÅ ÓÏÈÒÁÎÅÎÉÑ ÏÂÝÅÇÏ ÄÏÈÏÄÁ/ÐÏÔÅÒØ / Total Gain-Loss Balance (AGLB). äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v)1X1 X( (v) − i(v−S )) =( (v ) − j (v)) :s i∈S in − s j ∈= S j −S67õÓÌÏ×ÉÅ ÓÏÈÒÁÎÅÎÉÑ ÓÒÅÄÎÅÇÏ ÄÏÈÏÄÁ/ÐÏÔÅÒØ / Average Gain-LossBalance (AGLB). äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v)1 X1X( (v) − i(v−S )) =( (v ) − j (v)) :s i∈S in − s j ∈= S j −SðÏÓÌÅÄÎÉÅ 2 ÁËÓÉÏÍÙ ÐÒÉÚ×ÁÎÙ ÚÁÍÅÎÉÔØ ÁËÓÉÏÍÙ E (TP). ðÅÒ×ÁÑ ÉÚ ÎÉÈÇÏ×ÏÒÉÔ, ÞÔÏ ÐÒÉ ×ÙÞÅÒËÉ×ÁÎÉÉ ËÏÁÌÉÃÉÉ ÓÕÍÍÁÒÎÏÅ ×ÌÉÑÎÉÅ ÎÅ ÍÅÎÑÅÔÓÑ, Á×ÔÏÒÁÑ | ÞÔÏ ÓÒÅÄÎÉÅ ÐÏÔÅÒÉ ÏÔ ×ÙÞÅÒËÉ×ÁÎÉÑ ËÏÁÌÉÃÉÉ S ÓÒÅÄÉ ÉÇÒÏËÏ×,×ÈÏÄÑÝÉÈ × S , ÒÁ×ÎÙ ÓÒÅÄÎÅÍÕ ÄÏÈÏÄÕ ÉÇÒÏËÏ×, × S ÎÅ ×ÈÏÄÑÝÉÈ.äÌÑ ËÁÖÄÏÇÏ ÉÚ ÉÎÄÅËÓÏ× âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ × [65] ÐÏÓÔÒÏÅÎÙ ÐÏ Ä×ÅÓÉÓÔÅÍÙ ÁËÓÉÏÍ (ÔÅÏÒÅÍÙ 3 É 4).

ðÒÉ ÜÔÏÍ ÐÒÅÄÐÏÌÁÇÁÅÔÓÑ, ÞÔÏ ÉÎÄÅËÓ ×ÌÉÑÎÉÑÍÏÖÅÔ ÐÒÉÎÉÍÁÔØ É ÏÔÒÉÃÁÔÅÌØÎÙÅ ÚÎÁÞÅÎÉÑ, Ô.Å. : SGn → Rn. ïÂÏÚÎÁÞÉÍÞÅÒÅÚ 1 ×ÅËÔÏÒ (1; : : : ; 1) ∈ Rn.ôÅÏÒÅÍÁ 3. éÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP∗, An, SymGL ÉTGLB, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ = a · SS + b1, ÇÄÅ a ∈ R+, b ∈ R.éÎÄÅËÓ ×ÌÉÑÎÉÑ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP∗, An, SymGL É AGLB, ÅÓÌÉÉ ÔÏÌØËÏ ÅÓÌÉ = a · T Bz + b1, ÇÄÅ a ∈ R+, b ∈ R.ôÅÏÒÅÍÁ 4. ðÕÓÔØ : SGn → Rn.

ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP∗, An,T∗ É TGLB, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ = a · SS + b1, ÇÄÅ a ∈ R+, b ∈ R.ðÕÓÔØ : SGn → Rn. ôÏÇÄÁ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP∗, An, T∗ ÉAGLB, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ = a · T Bz + b1, ÇÄÅ a ∈ R+, b ∈ R.ðÏÓËÏÌØËÕ ÔÅÏÒÅÍÙ 3|4 ÏÐÒÅÄÅÌÑÀÔ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ÐÒÏÐÏÒÃÉÏÎÁÌØÎÏÓÔÉ, ÔÏ ÁËÓÉÏÍÁÔÉËÅ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ É ÉÎÄÅËÓðÅÎÒÏÕÚÁ.682. áËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×ðÒÅÄÌÁÇÁÅÍÙÅ ÁËÓÉÏÍÙ ÕÄÏÂÎÅÅ ÆÏÒÍÕÌÉÒÏ×ÁÔØ × ÓÔÉÌÅ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ. éÚ ÁËÓÉÏÍÁÔÉËÉ äÕÂÉ|ûÅÐÌÉ ×ÚÑÔÙ ÚÁ ÏÓÎÏ×Õ ÁËÓÉÏÍÁ NP, ÐÏÓËÏÌØËÕÏÎÁ ËÁÖÅÔÓÑ Á×ÔÏÒÕ ÂÏÌÅÅ ÐÒÏÓÔÏÊ, É ÁËÓÉÏÍÁ BzTP, ÔÁË ËÁË ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁÜÔÏÊ ÁËÓÉÏÍÙ × ÓÔÉÌÅ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ ÄÌÑ ÉÎÄÅËÓÏ× Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ×ÙÇÌÑÄÉÔ ÎÅÓËÏÌØËÏ ÉÓÓËÕÓÔ×ÅÎÎÏÊ.áËÓÉÏÍÁ ÂÏÌ×ÁÎÁ/Null Player (NP).

÷ÙÉÇÒÙÛ ÂÏÌ×ÁÎÁ ÎÅ ÚÁ×ÉÓÉÔ ÏÔÉÎÔÅÎÓÉ×ÎÏÓÔÅÊ ÐÒÅÄÐÏÞÔÅÎÉÊ É ×ÓÅÇÄÁ ÒÁ×ÅÎ 0.ôÒÁÎÓÆÅÒ/Transfer (T). äÌÑ ÌÀÂÙÈ ÉÇÒ v; w ∈ SGPn, ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉS ∈ M (v) ∩ M (w) É ÌÀÂÏÇÏ ii(v) − i(v−S ) = i(w) − i(w−S ):õÓÉÌÅÎÎÁÑ ÁËÓÉÏÍÁ ÔÒÁÎÓÆÅÒÁ/Strong Transfer (ST). äÌÑ ÌÀÂÏÊ ÉÇÒÙv ∈ SGPn, ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÏÇÏ i ∈ Si(v) − i(v−S ) = f (i; S ):åÓÌÉ i ∈ S , ÔÏ ST | ÕÓÉÌÅÎÉÅ ÁËÓÉÏÍÙ T: × T ÕËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÒÁÚÎÏÓÔØi(v) − i(v−S ) ÐÏÓÔÏÑÎÎÁ ÐÏ v, Á ST ÄÏÐÏÌÎÉÔÅÌØÎÏ ÇÏ×ÏÒÉÔ, ÞÅÍÕ ÜÔÁ ÒÁÚÎÏÓÔØÒÁ×ÎÁ.îÏ ÅÓÌÉ i ∈= S , ÁËÓÉÏÍÁ ST, × ÏÔÌÉÞÉÅ ÏÔ T, ÎÅ ÕÔ×ÅÒÖÄÁÅÔ ÎÉÞÅÇÏ.õÓÌÏ×ÉÅ ÓÉÍÍÅÔÒÉÞÎÏÓÔÉ ÄÏÈÏÄÏ×/ÐÏÔÅÒØ / Symmetric Gain-Loss(SymGL). 1) äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÙÈi; j ∈ S :69i(v) − i(v−S ) = j (v) − j (v−S ):2) äÌÑ ÌÀÂÏÊ ÉÇÒÙ v ∈ SGPn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÙÈ i; j ∈= S :i(v) − i(v−S ) = j (v) − j (v−S ):ðÅÒ×ÁÑ É ×ÔÏÒÁÑ ÞÁÓÔÉ SymGL × ÏÔÌÉÞÉÅ ÏÔ ÁËÓÉÏÍÁÔÉËÉ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏÉÓÐÏÌØÚÕÀÔÓÑ ÎÅ ÔÏÌØËÏ ×ÍÅÓÔÅ, ÎÏ É ÐÏÒÏÚÎØ É ÏÂÏÚÎÁÞÁÀÔÓÑ ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏËÁË SymGL1 É SymGL2.áËÓÉÏÍÙ T É SymGL | ÐÒÑÍÙÅ ÁÎÁÌÏÇÉ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ ÁËÓÉÏÍ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ.ïÂÝÁÑ ÓÕÍÍÁ/Total Power (TP).nXi=1i(v) =nXXi=1 S ∈Wi (v)f (i; S ):÷ ÓÌÕÞÁÅ ÓÉÍÍÅÔÒÉÞÎÏÊ ÉÇÒÙ v f (i; S ) = f (S ) É ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i.

äÌÑ ËÁÖÄÏÊËÏÁÌÉÃÉÉ S f (S ) ×ÈÏÄÉÔ × ÓÕÍÍÕ ÓÔÏÌØËÏ ÒÁÚ, ÓËÏÌØËÏ ËÌÀÞÅ×ÙÈ ÉÇÒÏËÏ× ×ËÏÁÌÉÃÉÉ S . ô.Å. ÁËÓÉÏÍÕ ÍÏÖÎÏ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÔØ:nXi=1i(v) =XS ⊂Nk(S )f (S );ÇÄÅ k(S ) | ÞÉÓÌÏ ËÌÀÞÅ×ÙÈ ÉÇÒÏËÏ× × ËÏÁÌÉÃÉÉ S .2.1. ôÅÏÒÅÍÁ ËÌÁÓÓÉÆÉËÁÃÉÉôÅÏÒÅÍÁ 5. 1) ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É T.ôÏÇÄÁi(v) =XS ∈Wi (v)70g(i; S );(2.1)ÇÄÅ g(i; S ) | ÐÒÏÉÚ×ÏÌØÎÙÅ ÞÉÓÌÁ.2) ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, T É SymGL1.ôÏÇÄÁi(v) =XS ∈Wi (v)g(S );(2.2)ÇÄÅ g(S ) | ÐÒÏÉÚ×ÏÌØÎÙÅ ÞÉÓÌÁ.3) ðÕÓÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, T É ÏÂÅÉÍ ÞÁÓÔÑÍ SymGL. ôÏÇÄÁi(v) =XS ∈Wi (v)g(|S |);(2.3)ÇÄÅ g(|S |) | ÐÒÏÉÚ×ÏÌØÎÙÅ ÞÉÓÌÁ.ïÔÍÅÔÉÍ, ÞÔÏ ËÁÖÄÏÅ ÓÌÅÄÕÀÝÅÅ ÕÓÌÏ×ÉÅ ÔÅÏÒÅÍÙ ÕÓÉÌÉ×ÁÅÔ ÐÒÅÄÙÄÕÝÅÅ.äÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÐÏÔÒÅÂÕÅÔÓÑ ÓÌÅÄÕÀÝÁÑ ÌÅÍÍÁ.ìÅÍÍÁ 1.

1) ðÕÓÔØ S ∈ M (v) É (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÆÏÒÍÕÌÅ (2.1). ôÏÇÄÁi(v) − i(v−S ) =2) ðÕÓÔØ S ∈ M (v). ôÏÇÄÁi(v) − i(v−S ) =ÅÓÌÉ i ∈ S ;g(i; S ); −g (i; S ∪ {i});ÅÓÌÉ i ∈= S:ÅÓÌÉ i ∈ S ;f (i; S ); −f (i; S ∪ {i});ÅÓÌÉ i ∈= S:äÏËÁÚÁÔÅÌØÓÔ×Ï.äÏËÁÖÅÍ ÐÅÒ×ÕÀ ÞÁÓÔØ ÌÅÍÍÙ.i(v) − i(v−S ) =XS ∈Wi (v)g(i; S ) −=XS ∈Wi (v−S )g(i; S ) =Xg(i; S ) −XS ∈ Wi(v);S ∈ Wi(v−S );S ∈= Wi(v−S )S ∈= Wi(v)71g(i; S ):ðÏÓÌÅÄÎÉÅ Ä×Å ÓÕÍÍÙ ÓÏÄÅÒÖÁÔ ÐÏ ÌÅÍÍÅ 1 ÔÏÌØËÏ ÏÄÎÏ ÓÌÁÇÁÅÍÏÅ: g(i; S ),ÅÓÌÉ i ∈ S É −g(i; S ∪ {i}), ÅÓÌÉ i ∈= S .

þÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ.÷ÔÏÒÁÑ ÞÁÓÔØ ÌÅÍÍÙ ÓÌÅÄÕÅÔ ÉÚ ÐÅÒ×ÏÊ, ÐÏÓËÏÌØËÕ -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔÆÏÒÍÕÌÅ (2.1) ÐÒÉ g(i; S ) = f (i; S ). ¥ôÅÐÅÒØ ÐÅÒÅÊÄÅÍ Ë ÄÏËÁÚÁÔÅÌØÓÔ×Õ ÔÅÏÒÅÍÙ.äÏËÁÚÁÔÅÌØÓÔ×Ï. äÏËÁÖÅÍ ÓÎÁÞÁÌÁ, ÞÔÏ ÄÌÑ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÇÏ ÏÄÎÏÊ ÉÚ ÆÏÒÍÕÌ (2.1)|(2.3), ×ÙÐÏÌÎÑÀÔÓÑ É ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ ÁËÓÉÏÍÙ.ðÏÓËÏÌØËÕ ÉÚ (2.3) ÓÌÅÄÕÅÔ (2.2), Á ÉÚ (2.2) | (2.1), ×ÙÐÏÌÎÅÎÉÅ ÁËÓÉÏÍ T É NPÄÏÓÔÁÔÏÞÎÏ ÄÏËÁÚÁÔØ ÄÌÑ ÓÌÕÞÁÑ (2.1), Á ÐÅÒ×ÕÀ ÞÁÓÔØ SymGL | ÄÌÑ (2.2).ðÕÓÔØ ÉÇÒÏË i ÎÅ ËÌÀÞÅ×ÏÊ ÎÉ × ÏÄÎÏÊ ËÏÁÌÉÃÉÉ × ÉÇÒÅ v.

ôÏÇÄÁ ÓÕÍÍÁ ×ÏÐÒÅÄÅÌÅÎÉÉ i(v) ÎÅ ÓÏÄÅÒÖÉÔ ÎÉ ÏÄÎÏÇÏ ÓÌÁÇÁÅÍÏÇÏ, ÐÏÜÔÏÍÕ ÒÁ×ÎÁ 0. úÎÁÞÉÔ,×ÙÐÏÌÎÑÅÔÓÑ ÁËÓÉÏÍÁ NP.ðÏ ÌÅÍÍÅ 1 i(v) − i(v−S ) ÚÁ×ÉÓÉÔ ÔÏÌØËÏ ÏÔ i É S , ÎÏ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ v,ÐÏÜÔÏÍÕ ÄÌÑ ÌÀÂÙÈ ÉÇÒ v É w i(v) − i(v−S ) = i(w) − i(w−S ), ÅÓÌÉ ÔÏÌØËÏÉÇÒÙ v−S É w−S ÏÐÒÅÄÅÌÅÎÙ, Ô.Å. S ∈ M (v) É S ∈ M (w). úÎÁÞÉÔ, ×ÙÐÏÌÎÑÅÔÓÑÁËÓÉÏÍÁ T.ðÕÓÔØ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÆÏÒÍÕÌÅ (2.2), S ∈ M (v), i; j ∈ S .

ðÏ ÌÅÍÍÅ 1i(v) − i(v−S ) = g(S ) = j (v) − j (v−S ):óÌÅÄÏ×ÁÔÅÌØÎÏ, ×ÙÐÏÌÎÑÅÔÓÑ ÐÅÒ×ÁÑ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL.îÁËÏÎÅÃ, ÐÕÓÔØ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÆÏÒÍÕÌÅ (2.3), S ∈ M (v), i; j ∈= S . ðÏÌÅÍÍÅ 1i(v) − i(v−S ) = −g(|S ∪ {i}|) = −g(|S ∪ {j }|) = j (v) − j (v−S ):óÌÅÄÏ×ÁÔÅÌØÎÏ, ×ÙÐÏÌÎÑÅÔÓÑ ×ÔÏÒÁÑ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL.äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ.1) ïÐÒÅÄÅÌÉÍ g(i; S ) ËÁË72g(i; S ) = i(uS ) − i(uS−s):äÏËÁÖÅÍ ÔÅÐÅÒØ ÐÅÒ×ÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÔÅÏÒÅÍÙ ÐÏ ÉÎÄÕËÃÉÉ ÐÏ |Wi(v)|.

åÓÌÉ|Wi (v )| = 0, Ô.Å. ÉÇÒÏË i ÎÅ ËÌÀÞÅ×ÏÊ ÎÉ × ËÁËÏÊ ×ÙÉÇÒÙ×ÁÀÝÅÊ ËÏÁÌÉÃÉÉ, ÔÏ ÐÏÁËÓÉÏÍÅ NP i(v) = 0, ËÁË É ÄÏÌÖÎÏ ÐÏÌÕÞÉÔØÓÑ ÐÒÉ ÓÕÍÍÉÒÏ×ÁÎÉÉ ÐÏ ÐÕÓÔÏÍÕÍÎÏÖÅÓÔ×Õ.ðÕÓÔØ ÔÅÐÅÒØ |Wi(v)| = k É ÕÔ×ÅÒÖÄÅÎÉÅ ÄÏËÁÚÁÎÏ ÄÌÑ ×ÓÅÈ ÉÇÒ, × ËÏÔÏÒÙÈi ËÌÀÞÅ×ÏÊ × ÍÅÎØÛÅÍ ÞÉÓÌÅ ËÏÁÌÉÃÉÊ. ÷ ÉÇÒÅ v ÓÕÝÅÓÔ×ÕÅÔ ÍÉÎÉÍÁÌØÎÁÑ ×Ù-ÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ, × ËÏÔÏÒÏÊ i | ËÌÀÞÅ×ÏÊ. ïÂÏÚÎÁÞÉÍ ÅÅ ÞÅÒÅÚ R. ôÏÇÄÁ¡¢i(v) = (i(v) − i(v−R )) + i(v−R ) = i(uR ) − i(uR−R ) + i(v−R ) == g(i; R) +XS ∈Wi (v−R )g(i; S ) =XS ∈Wi (v)g(i; S ):÷ÔÏÒÏÅ ÒÁ×ÅÎÓÔ×Ï ÓÌÅÄÕÅÔ ÉÚ ÁËÓÉÏÍÙ T, ÔÒÅÔØÅ ÉÚ ÏÐÒÅÄÅÌÅÎÉÑ g(i; R) ÉÐÒÅÄÐÏÌÏÖÅÎÉÑ ÉÎÄÕËÃÉÉ, ÐÏÓÌÅÄÎÅÅ ÉÚ ÌÅÍÍÙ 1: Wi(v) = Wi(v−R ) ∪ R.2) ðÏÓËÏÌØËÕ ÐÅÒ×ÁÑ ÞÁÓÔØ ÔÅÏÒÅÍÙ ÄÏËÁÚÁÎÁ, ÄÏÓÔÁÔÏÞÎÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏg(i; S ) ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i: ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S É ÌÀÂÙÈ i; j ∈ S g (i; S ) = g(j; S )(ÅÓÌÉ i ∈= S , g(i; S ) ÎÅ ÏÐÒÅÄÅÌÅÎÏ), Á ÜÔÏ ÓÌÅÄÕÅÔ ÉÚ ÐÅÒ×ÏÊ ÞÁÓÔØ ÁËÓÉÏÍÙSymGL, ÐÒÉÍÅÎÅÎÎÏÊ Ë uS :g(i; S ) = i(uS ) − i(uS−s) = j (uS ) − j (uS−s) = g(j; S ):3) ðÏÓËÏÌØËÕ ×ÔÏÒÁÑ ÞÁÓÔØ ÔÅÏÒÅÍÙ ÄÏËÁÚÁÎÁ, ÄÏÓÔÁÔÏÞÎÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏg(S ) ÚÁ×ÉÓÉÔ ÔÏÌØËÏ ÏÔ |S |: ÄÌÑ ÌÀÂÙÈ Ä×ÕÈ ËÏÁÌÉÃÉÊ ÏÄÎÏÇÏ ÒÁÚÍÅÒÁ S É S 0g(S ) = g(S 0).ðÕÓÔØ T = S ∩ S 0, ôÏÇÄÁ S = {s1; : : : ; sk } ∪ T , Á S 0 = {s01; : : : ; s0k } ∪ T , ÇÄÅ ÜÌÅÍÅÎÔÙ s1; : : : ; sk ; s01; : : : ; s0k ÐÏÐÁÒÎÏ ÒÁÚÌÉÞÎÙ.

òÁÓÓÍÏÔÒÉÍ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ73ËÏÁÌÉÃÉÊ, × ËÏÔÏÒÙÈ si ÐÏÏÞÅÒÅÄÎÏ ÚÁÍÅÎÑÀÔÓÑ ÎÁ s0i:S0 = S;S1 = {s01; s2; : : : ; sk } ∪ T;:::Si = {s01; : : : s0i; si+1; : : : ; sk } ∪ T;:::Sk = S 0 :äÏÓÔÁÔÏÞÎÏ ÄÏËÁÚÁÔØ, ÞÔÏ ÄÌÑ ÌÀÂÏÇÏ i g (Si) = g(Si+1), Ô.Å. ÕÔ×ÅÒÖÄÅÎÉÅÄÏÓÔÁÔÏÞÎÏ ÄÏËÁÚÁÔØ ÄÌÑ Ä×ÕÈ ËÏÁÌÉÃÉÊ S É S 0 ÏÄÉÎÁËÏ×ÏÇÏ ÒÁÚÍÅÒÁ, ÏÔÌÉÞÁÀÝÉÈÓÑ ÔÏÌØËÏ ÏÄÎÉÍ ÜÌÅÍÅÎÔÏÍ: S = T ∪ {i}, S 0 = T ∪ {j }.òÁÓÓÍÏÔÒÉÍ ÉÇÒÕ uT . ðÏÓËÏÌØËÕ T ∈ M (uT ), i; j ∈= T , ÔÏ ÐÏ ×ÔÏÒÏÊ ÞÁÓÔÉÁËÓÉÏÍÙ SymGL É ÌÅÍÍÅ 1¡¢¡¢g(S ) = − i(uT ) − i(uT−T ) = − j (uT ) − j (uT−T ) = g(S 0):ôÅÏÒÅÍÁ ÄÏËÁÚÁÎÁ. ¥úÁÍÅÞÁÎÉÅ 1. ÷ ÄÏËÁÚÁÔÅÌØÓÔ×Å ×ÔÏÒÏÊ ÐÏÌÏ×ÉÎÙ 1-ÇÏ ÐÕÎËÔÁ ÔÅÏÒÅÍÙ ÁËÓÉÏÍÁ T ÉÓÐÏÌØÚÕÅÔÓÑ ÔÏÌØËÏ × ÓÌÕÞÁÅ, ËÏÇÄÁ i ∈ S .

ðÏÜÔÏÍÕ ÅÅ ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁÁËÓÉÏÍÕ ST. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÄÌÑ ÌÀÂÏÇÏ ÉÎÄÅËÓÁ, ÕÄÏ×ÌÅÔ×ÏÒÑÀÝÅÇÏ ÁËÓÉÏÍÁÍST É NP, ÔÁËÖÅ ×ÅÒÎÁ ÆÏÒÍÕÌÁ 2.1.ðÏ ÔÅÏÒÅÍÅ 5 ÌÀÂÏÊ ÉÎÄÅËÓ, ÄÌÑ ËÏÔÏÒÏÇÏ ×ÅÒÎÁ ÆÏÒÍÕÌÁ 2.1, ÕÄÏ×ÌÅÔ×ÏÒÑÅÔÁËÓÉÏÍÅ T. ðÏÜÔÏÍÕ T ÓÌÅÄÕÅÔ ÉÚ ÁËÓÉÏÍ ST É NP.ðÏ ×ÓÅÊ ×ÉÄÉÍÏÓÔÉ, ÁËÓÉÏÍÁ T ÓÌÅÄÕÅÔ É ÐÒÏÓÔÏ ÉÚ ÁËÓÉÏÍÙ ST, ÎÏ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÜÔÏÇÏ ÆÁËÔÁ Á×ÔÏÒÕ ÎÅÉÚ×ÅÓÔÎÏ.úÁÍÅÞÁÎÉÅ 2. áËÓÉÏÍÁ ÁÎÏÎÉÍÎÏÓÔÉ ×ÅÒÎÁ, ÔÏÌØËÏ ÅÓÌÉ ×ÙÐÏÌÎÑÅÔÓÑ ÕÓÌÏ×ÉÅÔÒÅÔØÅÇÏ ÐÕÎËÔÁ ÔÅÏÒÅÍÙ, Ô.Å.

An ÓÌÅÄÕÅÔ ÉÚ NP, T É SymGL, ÎÏ ÎÅ ÓÌÅÄÕÅÔ ÉÚ74NP , T É SymGL1.2.2. áËÓÉÏÍÁÔÉËÉ ÄÌÑ -ÉÎÄÅËÓÁ÷ÙÑÓÎÉÍ, ËÁËÉÍ ÉÚ ÕÐÏÍÑÎÕÔÙÈ ×ÙÛÅ ÁËÓÉÏÍ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ -ÉÎÄÅËÓ.ìÅÍÍÁ 2. éÎÄÅËÓ ×ÌÉÑÎÉÑ (v), ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ ÍÎÏÖÅÓÔ×Å SGPn, ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, TP, T É ST. åÓÌÉ ÏÇÒÁÎÉÞÉÔØ (v) ÎÁ ÍÎÏÖÅÓÔ×ÏÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ (SSGPn), ÔÏ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÁËÖÅ ÐÅÒ×ÏÊ ÞÁÓÔÉ ÁËÓÉÏÍÙ SymGL.äÏËÁÚÁÔÅÌØÓÔ×Ï. -ÉÎÄÅËÓ ÐÏÄÐÁÄÁÅÔ ÐÏÄ ÄÅÊÓÔ×ÉÅ 1-ÇÏ ÐÕÎËÔÁ ÔÅÏÒÅÍÙ 5,ÐÏÜÔÏÍÕ ÄÌÑ ÎÅÇÏ ×ÙÐÏÌÎÑÀÔÓÑ ÁËÓÉÏÍÙ NP É T. ÷ ÓÌÕÞÁÅ ÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ(v) ÐÏÄÐÁÄÁÅÔ ÐÏÄ ÄÅÊÓÔ×ÉÅ É 2-ÇÏ ÐÕÎËÔÁ ÔÅÏÒÅÍÙ 5, ÐÏÜÔÏÍÕ ×ÙÐÏÌÎÑÅÔÓÑÐÅÒ×ÁÑ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL.áËÓÉÏÍÁ ST | ÜÔÏ × ÔÏÞÎÏÓÔÉ ÕÔ×ÅÒÖÄÅÎÉÅ ÌÅÍÍÙ 1.îÁËÏÎÅÃ, ÎÁÊÄÅÍ ÓÕÍÍÕ ×ÓÅÈ ËÏÏÒÄÉÎÁÔ ×ÅËÔÏÒÁ (v).nXi=1i(v) =nXXi=1 S ∈Wi (v)f (i; S );Ô.Å.

×ÙÐÏÌÎÑÅÔÓÑ ÁËÓÉÏÍÁ TP. ìÅÍÍÁ ÄÏËÁÚÁÎÁ. ¥úÁÍÅÞÁÎÉÅ 3. äÌÑ ÎÅÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ f (i; S ) ÎÅ ÏÂÑÚÁÔÅÌØÎÏ ÒÁ×ÎÏ f (j; S ),ÐÏÜÔÏÍÕ ÐÅÒ×ÁÑ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL ÎÅ ×ÙÐÏÌÎÑÅÔÓÑ.úÁÍÅÞÁÎÉÅ 4. äÌÑ ÉÇÒ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ (ËÁË ÓÉÍÍÅÔÒÉÞÎÙÈ, ÔÁË É ÎÅÓÉÍÍÅÔÒÉÞÎÙÈ) ÎÅ ×ÙÐÏÌÎÑÅÔÓÑ ×ÔÏÒÁÑ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL, ÐÏÓËÏÌØËÕ ÅÓÌÉ i ∈= S ,ÔÏ i(v) − i(v−S ) = −f (i; S ∪ {i}), Á f (i; S ∪ {i}) ÚÁ×ÉÓÉÔ ÏÔ i.752.2.1. óÌÅÄÓÔ×ÉÅ ÉÚ ÔÅÏÒÅÍÙ ËÌÁÓÓÉÆÉËÁÃÉÉäÌÑ ÏÄÎÏÚÎÁÞÎÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ -ÉÎÄÅËÓÁ ÄÏÓÔÁÔÏÞÎÏ Ä×ÕÈ ÁËÓÉÏÍ, ÎÏ ÏÄÎÁ ÉÚÎÉÈ ÏÞÅÎØ ÓÉÌØÎÁ.ôÅÏÒÅÍÁ 6. éÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É ST ÔÏÇÄÁ ÉÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ (v) = (v).äÏËÁÚÁÔÅÌØÓÔ×Ï.

ðÏ ÌÅÍÍÅ 2 (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É ST. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ.ðÕÓÔØ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É ST. óÏÇÌÁÓÎÏ ÚÁÍÅÞÁÎÉÀ 1 × ÜÔÏÍÓÌÕÞÁÅ ×ÅÒÎÁ É ÁËÓÉÏÍÁ T. ðÏÜÔÏÍÕ (ÐÅÒ×ÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÔÅÏÒÅÍÙ 5)i(v) =XS ∈Wi (v)g(i; S ):ôÁË ËÁË S ∈ M (uS ), ÐÏ ÌÅÍÍÅ 1 g(i; S ) = i(uS ) − i(uS−S ), Á ÐÏ ÁËÓÉÏÍÅ STi(uS ) − i(uS−S ) = f (i; S ).