Диссертация (1137405), страница 11
Текст из файла (страница 11)
úÎÁÞÉÔ, g(i; S ) = f (i; S ) Éi(v) =XS ∈Wi (v)f (i; S ) = i(v);ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ. ¥áÎÁÌÏÇ ÜÔÏÊ ÁËÓÉÏÍÁÔÉËÉ | ÕÔ×ÅÒÖÄÅÎÉÅ Ï ÔÏÍ, ÞÔÏ ÌÉÎÅÊÎÁÑ ÆÕÎËÃÉÑ ÏÐÒÅÄÅÌÑÅÔÓÑ Ä×ÕÍÑ Ó×ÏÊÓÔ×ÁÍÉ | × ÎÕÌÅ ÏÎÁ ÒÁ×ÎÁ ÎÕÌÀ, Á ÐÒÏÉÚ×ÏÄÎÁÑ × ÌÀÂÏÊÔÏÞËÅ ÐÏÓÔÏÑÎÎÁ.2.2.2. áÎÁÌÏÇ ÁËÓÉÏÍÁÔÉËÉ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ÷ ÓÌÕÞÁÅ ÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ -ÉÎÄÅËÓ ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÁËÓÉÏÍÙ NP, T,SymGL1 É TP. äÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÎÕÖÎÁ ÓÌÅÄÕÀÝÁÑ ÌÅÍÍÁ.76ìÅÍÍÁ 3. éÚ ÁËÓÉÏÍÙ TP ÓÌÅÄÕÅÔ, ÞÔÏ ÄÌÑ ÌÀÂÏÊ ÐÒÏÓÔÏÊ ÉÇÒÙ Ó ÐÒÅÄÐÏÞÔÅÎÉÑÍÉ É ÌÀÂÏÊ ÍÉÎÉÍÁÌØÎÏÊ ×ÙÉÇÒÙ×ÁÀÝÅÊ ËÏÁÌÉÃÉÉ S ÉÍÅÅÔ ÍÅÓÔÏXi∈S(i(v) − i(v−S )) −Xj ∈= S(j (v−S ) − j (v)) =Xi∈Sf (i; S ) −Xj ∈= Sf (j; S ∪ {j }): (2.4)äÏËÁÚÁÔÅÌØÓÔ×Ï.
óÎÁÞÁÌÁ ÏÔÍÅÔÉÍ, ÞÔÏ ÌÅ×ÁÑ ÞÁÓÔØ ÆÏÒÍÕÌÙ (2.4) | ÜÔÏÐÒÏÓÔÏ ÐÏ-ÄÒÕÇÏÍÕ ÚÁÐÉÓÁÎÎÏÅ ×ÙÒÁÖÅÎÉÅnXi=1(i(v) − i(v−S )):÷ÙÞÉÓÌÉÍ ÅÇÏ, ÉÓÐÏÌØÚÕÑ ÁËÓÉÏÍÕ TP É ÌÅÍÍÕ 1.nXi=1(i(v) − i(v−S )) =XXi∈S T ∈Wi (v)\Wi (v−S )nXXf (i; T )−i=1 T ∈Wi (v)Xf (i; T ) −Xj ∈= S T ∈Wj (v−S )\Wj (v)nXXi=1 T ∈Wi (v−S )f (j; T ) =Xi∈Sf (i; T ) =Xf (i; S )− f (j; S ∪{j }):j ∈= S¥úÁÍÅÞÁÎÉÅ 5. ïÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÂÕÄÅÔ ×ÅÒÎÏ, ÅÓÌÉ (0) = 0.
ôÁËÁÑ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÁ ÁËÓÉÏÍÙ TP | ÁÎÁÌÏÇ ÁËÓÉÏÍÙ AGLB ÉÚ ÁËÓÉÏÍÁÔÉËÉ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ [65].óÌÅÄÓÔ×ÉÅ 1. ÷ ÓÌÕÞÁÅ ÓÉÍÍÅÔÒÉÞÎÙÈ ÉÇÒ f (i; S ) ÎÅ ÚÁ×ÉÓÉÔ ÏÔ i É ÒÁ×ÅÎÓÔ×Ï(2.4) ÐÒÉÎÉÍÁÅÔ ×ÉÄXi∈S(i(v) − i(v−S )) −Xj ∈= S(j (v−S ) − j (v)) = s f (S ) −Xj ∈= Sf (S ∪ {j }):(2.5)ôÅÐÅÒØ ÄÏËÁÖÅÍ ÏÓÎÏ×ÎÕÀ ÔÅÏÒÅÍÕ ÜÔÏÇÏ ÐÁÒÁÇÒÁÆÁ.ôÅÏÒÅÍÁ 7. éÎÄÅËÓ ×ÌÉÑÎÉÑ (v), ÏÐÒÅÄÅÌÅÎÎÙÊ ÎÁ SSGPn, ÕÄÏ×ÌÅÔ×ÏÒÑÅÔÁËÓÉÏÍÁÍ NP, TP, T É SymGL1 ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ (v) = (v).77äÏËÁÚÁÔÅÌØÓÔ×Ï.
ðÏ ÌÅÍÍÅ 2 -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ×ÓÅÍ ×ÙÛÅÕÐÏÍÑÎÕÔÙÍÁËÓÉÏÍÁÍ. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ.äÏËÁÖÅÍ ÕÔ×ÅÒÖÄÅÎÉÅ ÉÎÄÕËÃÉÅÊ ÐÏ ÞÉÓÌÕ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ, ÎÅÏÄÎÏËÒÁÔÎÏ ÉÓÐÏÌØÚÕÑ ÐÒÉ ÜÔÏÍ ÌÅÍÍÕ 2.ïÓÎÏ×ÁÎÉÅ ÉÎÄÕËÃÉÉ. åÓÌÉ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ ÎÅÔ, ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏÎÉ ÏÄÉÎ ÉÇÒÏË ÎÅ ÂÕÄÅÔ ËÌÀÞÅ×ÙÍ ÎÉ × ÏÄÎÏÊ ËÏÁÌÉÃÉÉ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÐÏÁËÓÉÏÍÅ NP i(v) = 0 ÄÌÑ ×ÓÅÈ i. ðÏÓËÏÌØËÕ (v) ÔÏÖÅ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ NP, i(v) =0. úÎÁÞÉÔ, i(v) = i(v).ûÁÇ ÉÎÄÕËÃÉÉ. ÷ÏÚÍÏÖÎÙ Ä×Á ÓÌÕÞÁÑ.1) ðÕÓÔØ × ÉÇÒÅ v ÏÄÎÁ ÍÉÎÉÍÁÌØÎÁÑ ×ÙÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ S , Ô.Å. v = uS .÷ ÜÔÏÍ ÓÌÕÞÁÅ ËÏÁÌÉÃÉÑ T ÂÕÄÅÔ ×ÙÉÇÒÙ×ÁÀÝÅÊ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁÏÎÁ ÓÏÄÅÒÖÉÔ S , Ô.Å.
ÓÏÄÅÒÖÉÔ × ÓÅÂÅ ×ÓÅÈ ÉÇÒÏËÏ× ÉÚ S . ðÏÜÔÏÍÕ, ÅÓÌÉ ÉÇÒÏËj ∈= S , ÏÔ ÅÇÏ ×ÈÏÖÄÅÎÉÑ ÉÌÉ ÎÅ×ÈÏÖÄÅÎÉÑ × ËÏÁÌÉÃÉÀ T ÎÉÞÅÇÏ ÎÅ ÉÚÍÅÎÉÔÓÑ| T É T \ {j } ÂÕÄÕÔ ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÉÌÉ ÐÒÏÉÇÒÙ×ÁÀÝÉÍÉ ÏÄÎÏ×ÒÅÍÅÎÎÏ.úÎÁÞÉÔ, ×ÓÅ ÉÇÒÏËÉ, ÎÅ ×ÈÏÄÑÝÉÅ × S , ÂÕÄÕÔ ÂÏÌ×ÁÎÁÍÉ × ÉÇÒÅ v. é, ÅÓÌÉ i ∈= S ,i(v) = i(v) = 0.ðÕÓÔØ ÔÅÐÅÒØ i ∈ S .
úÁÐÉÛÅÍ ÁËÓÉÏÍÕ TP ÄÌÑ v É ÉÎÄÅËÓÏ× É .Xi∈S(i(v) − i(v−S )) −Xi∈S(i(v) − i(v−S )) −Xj ∈= SXj ∈= S(j (v−S ) − j (v)) = s f (S ) −(j (v−S ) − j (v)) = s f (S ) −Xj ∈= SXj ∈= Sf (S ∪ {j }):(2.6)f (S ∪ {j }):(2.7)ðÒÁ×ÙÅ ÞÁÓÔÉ ÒÁ×ÅÎÓÔ× ÓÏ×ÐÁÄÁÀÔ. ðÏ NP ÄÌÑ ×ÓÅÈ j , ÎÅ ×ÈÏÄÑÝÉÈ × S ,j (v) = 0 = j (v), ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ ÄÌÑ ×ÓÅÈ j j (v−S ) = j (v−S ).ðÏÄÓÔÁ×É× × (2.6) É ÓÒÁ×ÎÉ×ÁÑ Ó (2.7), ÐÏÌÕÞÉÍ78Xi∈S(i(v) − i(v−S )) =Xi∈S(i(v) − i(v−S )):óÏÇÌÁÓÎÏ ÐÅÒ×ÏÊ ÞÁÓÔÉ ÁËÓÉÏÍÙ SymGL ×ÓÅ ÓÌÁÇÁÅÍÙÅ É ÔÏÊ, É ÄÒÕÇÏÊ ÓÕÍÍÙÐÏÐÁÒÎÏ ÒÁ×ÎÙ. óÌÅÄÏ×ÁÔÅÌØÎÏ, ÄÌÑ ÌÀÂÏÇÏ i ∈ Si(v) − i(v−S ) = i(v) − i(v−S ):îÁËÏÎÅÃ, ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ i(v−S ) = i(v−S ).
úÎÁÞÉÔ, É i(v) =i(v).2) ðÕÓÔØ ÔÅÐÅÒØ M (v) > 1, Ô.Å. × ÉÇÒÅ v ÅÓÔØ Ä×Å ÍÉÎÉÍÁÌØÎÙÅ ×ÙÉÇÒÙ×ÁÀÝÉÅ ËÏÁÌÉÃÉÉ S É T , ÓÏÄÅÒÖÁÝÉÅ s É t ÜÌÅÍÅÎÔÏ× ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ. ðÒÉ ×ÙÞÅÒËÉ×ÁÎÉÉ ÓÎÁÞÁÌÁ S , ÐÏÔÏÍ T ÐÏÌÕÞÁÅÔÓÑ ÔÁ ÖÅ ÉÇÒÁ, ÞÔÏ É ÐÒÉ ×ÙÞÅÒËÉ×ÁÎÉÉÓÎÁÞÁÌÁ T , ÐÏÔÏÍ S .óÏÇÌÁÓÎÏ ÁËÓÉÏÍÅ T ÄÌÑ , ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ É ÁËÓÉÏÍÅ T ÄÌÑ (v),i(v) − i(v−S ) = i(v−T ) − i(v−S −T ) = i(v−T ) − i(v−S −T ) = i(v) − i(v−S ):îÏ ÐÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ i(v−S ) = i(v−S ).
úÎÁÞÉÔ, É i(v) = i(v).¥ôÅÏÒÅÍÕ 7 ÔÁËÖÅ ÍÏÖÎÏ ×Ù×ÅÓÔÉ ËÁË ÓÌÅÄÓÔ×ÉÅ ÔÅÏÒÅÍÙ ËÌÁÓÓÉÆÉËÁÃÉÉ (ÓÍ.ÓÌÅÄÕÀÝÉÊ ÐÁÒÁÇÒÁÆ), ÎÏ ÐÒÉ×ÅÄÅÎÎÏÅ ×ÙÛÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ËÒÁÓÉ×ÅÅ, ÈÏÔÑ ÉÄÌÉÎÎÅÅ.áÌØÔÅÒÎÁÔÉ×ÎÏÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 7äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÏ ÌÅÍÍÅ 2 -ÉÎÄÅËÓ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, TP, T ÉSymGL1. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ.ðÏ ÌÅÍÍÅ 2 (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP É ST. äÏËÁÖÅÍ ÏÂÒÁÔÎÏÅ.ðÕÓÔØ (v) ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÁËÓÉÏÍÁÍ NP, T É SymGL1. ôÏÇÄÁ, ÓÏÇÌÁÓÎÏ ×ÔÏÒÏÍÕ ÕÔ×ÅÒÖÄÅÎÉÀ ÔÅÏÒÅÍÙ 579i(v) =XS ∈Wi (v)g(S ):ïÓÔÁÌÏÓØ ÄÏËÁÚÁÔØ, ÞÔÏ g(S ) = f (S ) ÄÌÑ ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S .
ðÒÏ×ÅÄÅÍ ÉÎÄÕËÃÉÀÐÏ ÒÁÚÍÅÒÕ ËÏÁÌÉÃÉÉ S . íÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ g(∅) = f (∅) = 0.ðÕÓÔØ ÔÅÐÅÒØ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÏËÁÚÁÎÏ ÄÌÑ ×ÓÅÈ ËÏÁÌÉÃÉÊ, ÍÅÎØÛÉÈ ÐÏ ÞÉÓÌÕÉÇÒÏËÏ×, ÞÅÍ SðÏÓËÏÌØËÕ ÉÎÄÅËÓÙ ×ÌÉÑÎÉÑ É ÕÄÏ×ÌÅÔ×ÏÒÑÀÔ ÁËÓÉÏÍÅ TP, Á ÐÒÁ×ÁÑ ÞÁÓÔØÒÁ×ÅÎÓÔ×Á × ÎÅÊ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÉÎÄÅËÓÁ, ÔÏ ÄÌÑ ÌÀÂÏÊ ÐÒÏÓÔÏÊ ÉÇÒÙ vXi∈Ni(v) =Xi∈Ni(v):ðÏÄÓÔÁ×ÉÍ × ÜÔÕ ÆÏÒÍÕÌÕ v = uS É v = uS−S , ×ÙÞÔÅÍ É ÐÏÍÅÎÑÅÍ ÐÏÒÑÄÏËÓÕÍÍÉÒÏ×ÁÎÉÑ:X¡i∈N¢i(uS ) − i(uS−S ) =X¡i∈N¢i(uS ) − i(uS−S ) :÷ÏÓÐÏÌØÚÕÅÍÓÑ ÌÅÍÍÏÊ 1 ËÁË ÄÌÑ ÐÒÁ×ÏÊ, ÔÁË É ÄÌÑ ÌÅ×ÏÊ ÞÁÓÔÉ. ðÏÌÕÞÉÍXi∈Sg(S ) −Xi=∈Sg(S \ {i}) =Xi∈Sf (S ) −Xi=∈Sf (S \ {i}):ðÏ ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÉÎÄÕËÃÉÉ ÄÌÑ ÌÀÂÏÇÏ i ∈= S g(S \ {i}) = f (S \ {i}), ÐÏÜÔÏÍÕ×ÔÏÒÙÅ ÓÌÁÇÁÅÍÙÅ × ÐÒÁ×ÏÊ É ÌÅ×ÏÊ ÞÁÓÔÉ ÓÏËÒÁÝÁÀÔÓÑ, Ô.Å.Xi∈Sg(S ) =Xi∈Sf (S ):îÏ Ô.Ë.
f (S ) É g(S ) ÎÅ ÚÁ×ÉÓÑÔ ÏÔ i, ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ s · g(S ) = s · f (S ), Ô.Å.g(S ) = f (S ), ÅÓÌÉ S 6= ∅. á ÄÌÑ ÐÕÓÔÏÊ ËÏÁÌÉÃÉÉ ÔÅÏÒÅÍÁ ÄÏËÁÚÁÎÁ ×ÙÛÅ. ¥802.3. ðÒÉÍÅÎÅÎÉÅ Ë ÉÎÄÅËÓÁÍ âÁÎÃÁÆÁ É ûÅÐÌÉ|ûÕÂÉËÁ÷ ÐÒÉÍÅÒÅ 25 (ÇÌÁ×Á 1) ÂÙÌÏ ÐÏËÁÚÁÎÏ, ÞÔÏ ÐÒÉ ÐÏÄÓÔÁÎÏ×ËÅ ×ÍÅÓÔÏ f (S ) ÅÄÉÎÉÃÙ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ (v) ÐÒÅ×ÒÁÝÁÅÔÓÑ × ÏÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ, Á ÐÒÉ ÐÏÄÓÔÁÎÏ×ËÅ(s−1)!(n−s)!n!| × ÉÎÄÅËÓ ûÅÐÌÉ|ûÕÂÉËÁ. ðÏÓÍÏÔÒÉÍ, ÞÔÏ ÐÒÉ ÜÔÉÈ ÐÏÄ-ÓÔÁÎÏ×ËÁÈ ÐÒÏÉÚÏÊÄÅÔ Ó ÁËÓÉÏÍÁÍÉ ÄÌÑ (v).ôÅÏÒÅÍÁ 8. ÷ ÁËÓÉÏÍÁÔÉËÅ äÕÂÉ|ûÅÐÌÉ ÄÌÑ ÏÂÝÅÇÏ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ É ÁËÓÉÏÍÁÔÉËÅ äÕÂÉ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ ÁËÓÉÏÍÕ ÁÎÏÎÉÍÎÏÓÔÉ ÍÏÖÎÏÚÁÍÅÎÉÔØ ÎÁ ÐÅÒ×ÕÀ ÞÁÓÔØ ÁËÓÉÏÍÙ SymGL.äÏËÁÚÁÔÅÌØÓÔ×Ï.
ðÏÄÓÔÁ×ÉÍ f (S ) = 1. ôÏÇÄÁ ÁËÓÉÏÍÙ NP É TP ÓÏ×ÐÁÄÕÔ ÓÁËÓÉÏÍÁÍÉ NP É BzTP ÓÏÏÔ×ÅÔÓÔ×ÅÎÎÏ. áËÓÉÏÍÁ T ÓÏ×ÐÁÄÅÔ Ó T∗ ÉÚ ÁËÓÉÏÍÁÔÉËÉ ìÁÒÕÅÌÌØ|÷ÁÌÅÎÓÉÁÎÏ, Á SymGL1 | Ó ÐÅÒ×ÏÊ ÞÁÓÔØÀ ÁËÓÉÏÍÙ SymGL ÉÚÔÏÊ ÖÅ ÁËÓÉÏÍÁÔÉËÉ. ÷ [65] ÄÏËÁÚÁÎÏ, ÞÔÏ ÁËÓÉÏÍÙ T É T∗ ÜË×É×ÁÌÅÎÔÎÙ, ÓÌÅÄÏ×ÁÔÅÌØÎÏ, ÐÏ ÔÅÏÒÅÍÅ 7 ÁËÓÉÏÍÙ NP, BTP, T É ÐÅÒ×ÁÑ ÞÁÓÔØ SymGL ÏÄÎÏÚÎÁÞÎÏÚÁÄÁÀÔ ÏÂÝÉÊ ÉÎÄÅËÓ âÁÎÃÁÆÁ.òÁÓÓÕÖÄÅÎÉÅ ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ|ûÕÂÉËÁ ÁÎÁÌÏÇÉÞÎÏ É ÏÔÌÉÞÁÅÔÓÑ ÌÉÛØÔÅÍ, ÞÔÏ ÐÒÉ ÐÏÄÓÔÁÎÏ×ËÅ f (S ) = (s−1)!(n!n−s)! ÁËÓÉÏÍÁ TP ÐÒÅ×ÒÁÔÉÔÓÑ × ÁËÓÉÏÍÕÜÆÆÅËÔÉ×ÎÏÓÔÉ ÉÚ ÁËÓÉÏÍÁÔÉËÉ ûÅÐÌÉ.
¥áËÓÉÏÍÁ ST ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÚÁÐÉÓÙ×ÁÅÔÓÑ ÐÒÏÓÔÏ É ËÒÁÓÉ×Ï. äÌÑ ÌÀÂÏÊÉÇÒÙ v ∈ SGn, ÌÀÂÏÊ ËÏÁÌÉÃÉÉ S ∈ M (v) É ÌÀÂÏÇÏ i ∈ Si(v) − i(v−S ) = 1:üÔÁ ÁËÓÉÏÍÁ ×ËÕÐÅ Ó NP ÏÄÎÏÚÎÁÞÎÏ ÏÐÒÅÄÅÌÑÀÔ ÉÎÄÅËÓ âÁÎÃÁÆÁ. áÎÁÌÏÇÉÞÎÙÊ (ÎÏ ÍÅÎÅÅ ËÒÁÓÉ×ÙÊ) ÒÅÚÕÌØÔÁÔ ×ÅÒÅÎ É ÄÌÑ ÉÎÄÅËÓÁ ûÅÐÌÉ-ûÕÂÉËÁ.813. áËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ × ÓÌÕÞÁÅÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊâÏÌØÛÉÎÓÔ×Ï ÓÕÝÅÓÔ×ÕÀÝÉÈ ÓÈÅÍ ÇÏÌÏÓÏ×ÁÎÉÑ Ñ×ÌÑÀÔÓÑ (ÉÌÉ ÍÏÇÕÔ ÂÙÔØÏÐÉÓÁÎÙ ËÁË) ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ. ÷ÓÔÁÅÔ ×ÏÐÒÏÓ | ËÁË ÁËÓÉÏÍÁÔÉÞÅÓËÉ ÚÁÄÁÔØ ÉÎÄÅËÓ ×ÌÉÑÎÉÑ ÎÁ ÜÔÏÍ ËÌÁÓÓÅ ÐÒÁ×ÉÌ ÐÒÉÎÑÔÉÑ ÒÅÛÅÎÉÑ.îÅÐÏÓÒÅÄÓÔ×ÅÎÎÏ ÐÅÒÅÎÅÓÔÉ ÌÀÂÕÀ ÉÚ ÒÁÓÓÍÏÔÒÅÎÎÙÈ ×ÙÛÅ ÁËÓÉÏÍÁÔÉË ÎÁÓÌÕÞÁÊ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ ÎÅ ÕÄÁÅÔÓÑ, ÐÏÓËÏÌØËÕ ÒÅÚÕÌØÔÁÔ ÍÎÏÇÉÈ ÏÐÅÒÁÃÉÊÎÁÄ ÇÏÌÏÓÏ×ÁÎÉÑÍÉ Ó Ë×ÏÔÏÊ (ÏÂßÅÄÉÎÅÎÉÅ, ÐÅÒÅÓÅÞÅÎÉÅ, ×ÙÞÅÒËÉ×ÁÎÉÅ ËÏÁÌÉÃÉÉ) ÕÖÅ ÎÅ ÂÕÄÅÔ ÚÁÐÉÓÙ×ÁÔØÓÑ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ.ðÒÉÍÅÒ 1.
ðÕÓÔØ N = {1; 2; 3; 4}. ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ v ÐÒÏÓÔÕÀ ÉÇÒÕ Ó Ä×ÕÍÑÍÉÎÉÍÁÌØÎÙÍÉ ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ | {1; 2} É {3; 4}. ÷ ÐÒÉÍÅÒÅ 10(ÇÌÁ×Á 1) ÂÙÌÏ ÄÏËÁÚÁÎÏ, ÞÔÏ v ÎÅÌØÚÑ ÚÁÐÉÓÁÔØ × ×ÉÄÅ ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ.îÏ1. v = u{1;2} ∪ u{3;4}, Ô.Å. ÏÂßÅÄÉÎÅÎÉÅ Ä×ÕÈ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ.2. òÁÓÓÍÏÔÒÉÍ 4 ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊw1 = (3; 2; 1; 2; 1); w2 = (3; 1; 2; 2; 1); w3 = (3; 2; 1; 1; 2); w4 = (3; 1; 2; 1; 2):÷ÙÉÇÒÙ×ÁÀÝÉÍÉ ËÏÁÌÉÃÉÑÍÉ × ÎÉÈ ÂÕÄÕÔ ×ÓÅ 3- É 4-ÜÌÅÍÅÎÔÎÙÅ ÍÎÏÖÅÓÔ×ÁÉÇÒÏËÏ× É ×ÓÅ 2-ÜÌÅÍÅÎÔÎÙÅ, ËÒÏÍÅ {2; 4} ÄÌÑ w1, ËÒÏÍÅ {1; 4} ÄÌÑ w2, ËÒÏÍÅ{2; 3} ÄÌÑ w3É ËÒÏÍÅ {1; 3} ÄÌÑ w4.
ðÏÜÔÏÍÕ ÐÒÉ ÐÅÒÅÓÅÞÅÎÉÉ ÜÔÉÈ ÇÏÌÏÓÏ×ÁÎÉÊÓ Ë×ÏÔÏÊ ÐÏÌÕÞÁÅÔÓÑ v.3. ÷ w1 5 ÍÉÎÉÍÁÌØÎÙÈ ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ | ×ÓÅ 2-ÜÌÅÍÅÎÔÎÙÅ, ËÒÏÍÅ {2; 4}. ÷ÙÞÅÒËÎÅÍ {1; 3}. ðÏÌÕÞÅÎÎÁÑ ÐÒÏÓÔÁÑ ÉÇÒÁ ÎÅ ÍÏÖÅÔ ÂÙÔØ ÚÁÐÉÓÁÎÁ,ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ. éÎÁÞÅ, ÐÏÓËÏÌØËÕ ËÏÁÌÉÃÉÉ {1; 2} É {3; 4} ×ÙÉÇÒÙ×ÁÀÝÉÅ, ÓÕÍÍÁ ÉÈ ÇÏÌÏÓÏ× ÎÅ ÍÅÎØÛÅ Ä×ÕÈ Ë×ÏÔ, {1; 3} É {2; 4} | ÐÒÏÉÇÒÙ×ÁÀÝÉÅ,82ÐÏÜÔÏÍÕ ÓÕÍÍÁ ÉÈ ÇÏÌÏÓÏ× ÍÅÎØÛÅ Ä×ÕÈ Ë×ÏÔ. îÏ × ÏÂÏÉÈ ÓÌÕÞÁÑÈ ÒÅÞØ ÉÄÅÔ ÏÓÕÍÍÅ ÇÏÌÏÓÏ× ×ÓÅÈ ÉÇÒÏËÏ×. ðÒÏÔÉ×ÏÒÅÞÉÅ.÷ [8] ÂÙÌÁ ÐÏÓÔÒÏÅÎÁ ÁËÓÉÏÍÁÔÉËÁ ÄÌÑ ÉÎÄÅËÓÁ ×ÌÉÑÎÉÑ âÁÎÃÁÆÁ, ÁÄÁÐÔÉÒÏ×ÁÎÎÁÑ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ.
÷ ÜÔÏÊ ÓÔÁÔØÅ ××ÏÄÉÔÓÑ ÎÅÓËÏÌØËÏ ÎÏ×ÙÈÁËÓÉÏÍ, ÆÏÒÍÕÌÉÒÏ×ËÉ ËÏÔÏÒÙÈ Ó ÔÏÞËÉ ÚÒÅÎÉÑ Á×ÔÏÒÁ ÜÔÏÊ ÓÔÁÔØÉ ÓÌÏÖÎÅÅ,ÞÅÍ × ÁËÓÉÏÍÁÔÉËÁÈ ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ ÄÌÑ ÐÒÏÓÔÙÈ ÉÇÒ.ëÏÎÓÔÒÕËÃÉÑ [8] ÉÎÔÅÒÅÓÎÁ ÓÁÍÁ ÐÏ ÓÅÂÅ, ÎÏ ÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÍÎÏÇÉÅ (Á ÎÁÓÁÍÏÍ ÄÅÌÅ | ÂÏÌØÛÉÎÓÔ×Ï) ÁËÓÉÏÍÁÔÉË ÍÏÖÎÏ ÁÄÁÐÔÉÒÏ×ÁÔØ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊÓ Ë×ÏÔÏÊ."âÁÚÏ×ÙÅ" ÉÇÒÙ ÚÁÐÉÓÙ×ÁÀÔÓÑ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÑ Ó Ë×ÏÔÏÊ É, ÈÏÔÑ ÉÚ ÉÇÒÙv ∈ W Gn ÎÅÌØÚÑ ×ÙÞÅÒËÎÕÔØ ÐÒÏÉÚ×ÏÌØÎÕÀ ÍÉÎÉÍÁÌØÎÕÀ ×ÙÉÇÒÙ×ÁÀÝÕÀ ËÏ-ÁÌÉÃÉÀ, ÏÓÔÁ×ÛÉÓØ ×Ï ÍÎÏÖÅÓÔ×Å W Gn, ÎÏ ËÁËÕÀ-ÎÉÂÕÄØ ÍÏÖÎÏ.
ðÏÜÔÏÍÕ ÎÅËÏÔÏÒÙÅ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÏÓÔÁÀÔÓÑ ×ÅÒÎÙÍÉ, ÅÓÌÉ ÐÒÏÓÔÏ ÄÏÐÉÓÁÔØ × ÎÕÖÎÙÈÍÅÓÔÁÈ ÆÒÁÚÕ "× ÔÏÍ ÓÌÕÞÁÅ, ÅÓÌÉ ÒÅÚÕÌØÔÁÔ ÏÐÅÒÁÃÉÉ ÂÕÄÅÔ ÇÏÌÏÓÏ×ÁÎÉÅÍ ÓË×ÏÔÏÊ".óÔÏÌØ ÖÅ ÐÒÏÓÔÏ ÕÄÁÅÔÓÑ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÔØ ÄÌÑ ÇÏÌÏÓÏ×ÁÎÉÊ Ó Ë×ÏÔÏÊ ÉÁËÓÉÏÍÁÔÉËÉ ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ×.îÅ×ÏÚÍÏÖÎÏ, ÄÁ É ÎÅ ÎÕÖÎÏ ÐÒÉ×ÏÄÉÔØ ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ËÉ É ÄÏËÁÚÁÔÅÌØÓÔ×ÁÄÌÑ ×ÓÅÈ ×ÏÚÍÏÖÎÙÈ ÁËÓÉÏÍÁÔÉË. ÷ ÄÉÓÓÅÒÔÁÃÉÉ ÜÔÏ ÓÄÅÌÁÎÏ ÄÌÑ ÁËÓÉÏÍÁÔÉËÉäÕÂÉ|ûÅÐÌÉ [50] ÄÌÑ ÉÎÄÅËÓÁ âÁÎÃÁÆÁ [32] É ÏÄÎÏÊ ÉÚ ÁËÓÉÏÍÁÔÉË ÄÌÑ ÉÎÄÅËÓÏ× ×ÌÉÑÎÉÑ, ÚÁ×ÉÓÑÝÉÈ ÏÔ ÐÒÅÄÐÏÞÔÅÎÉÊ ÕÞÁÓÔÎÉËÏ× [1, 23].æÏÒÍÁÌÉÚÁÃÉÀ ÓËÁÚÁÎÎÏÇÏ ÎÁÞÎÅÍ ÓÏ ÓÌÅÄÕÀÝÅÊ ÌÅÍÍÙ.ìÅÍÍÁ 4.
Á) ðÒÏÓÔÙÅ ÉÇÒÙ 0; 1 ∈ W Gn.Â) äÌÑ ÌÀÂÏÇÏ S uS ∈ W Gn.×) äÌÑ ÌÀÂÏÇÏ S 6= N uS−S ∈ W Gn.83Ç) ðÕÓÔØ v ∈ W Gn, Á ÉÇÒÏË i ÎÅ ÂÏÌ×ÁÎ × v. ôÏÇÄÁ ÓÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑÍÉÎÉÍÁÌØÎÁÑ ×ÙÉÇÒÙ×ÁÀÝÁÑ ËÏÁÌÉÃÉÑ S 3 i, ÞÔÏ v−S ∈ W Gn.äÏËÁÚÁÔÅÌØÓÔ×Ï. Á) ðÕÓÔØ ÄÌÑ ×ÓÅÈ i ∈ N wi = 1. ôÏÇÄÁ ÅÓÌÉ q = 0, ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÂÕÄÕÔ ×ÓÅ ËÏÁÌÉÃÉÉ, Á ÅÓÌÉ q = n + 1, ×ÙÉÇÒÙ×ÁÀÝÉÈ ËÏÁÌÉÃÉÊ ÎÅÂÕÄÅÔ.Â) ðÕÓÔØ wi = n + 1, ÅÓÌÉ i ∈ S , vi = 1, ÅÓÌÉ i ∈= S , q = |S | · (n + 1).
÷ ÜÔÏÍÓÌÕÞÁÅ ËÏÁÌÉÃÉÑ ÂÕÄÅÔ ×ÙÉÇÒÙ×ÁÀÝÅÊ, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ ÏÎÁ ÓÏÄÅÒÖÉÔ S . þÔÏÉ ÔÒÅÂÏ×ÁÌÏÓØ.×) ïÐÒÅÄÅÌÉÍ ×ÅÓÁ ÉÇÒÏËÏ× ÔÁËÖÅ, ËÁË É × ÐÒÅÄÙÄÕÝÅÍ ÐÕÎËÔÅ, Á Ë×ÏÔÕ ÓÄÅÌÁÅÍ ÎÁ ÅÄÉÎÉÃÕ ÍÅÎØÛÅ: q = |S | · (n + 1) − 1. ëÏÁÌÉÃÉÑ ÂÕÄÅÔ ×ÙÉÇÒÙ×ÁÀÝÅÊ,ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ ÏÎÁ ÓÏÄÅÒÖÉÔ S ÚÁ ÏÄÎÉÍ ÉÓËÌÀÞÅÎÉÅÍ: S | ÐÒÏÉÇÒÙ×ÁÀÝÁÑ. ëÏÎÓÔÒÕËÃÉÑ ÎÅËÏÒÒÅËÔÎÁ, ÅÓÌÉ |S | = 0. îÏ ÔÏÇÄÁ S = ∅ É v = 1, Á ÜÔÏÔÓÌÕÞÁÊ ÕÖÅ ÒÁÓÓÍÏÔÒÅÎ × Ð. 1.Ç) òÁÚÏÂØÅÍ ÕÔ×ÅÒÖÄÅÎÉÅ ÎÁ Ä×Á.Ç1) åÓÌÉ ÉÇÒÕ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ, ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ, ÔÏ ÅÅ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË ÇÏÌÏÓÏ×ÁÎÉÅ Ó Ë×ÏÔÏÊ ÔÁË, ÞÔÏÂÙ ×ÙÉÇÒÙÛÉ ×ÓÅÈ ËÏÁÌÉÃÉÊ ÂÙÌÉÐÏÐÁÒÎÏ ÒÁÚÌÉÞÎÙ.Ç2) åÓÌÉ ×ÙÉÇÒÙÛÉ ×ÓÅÈ ËÏÁÌÉÃÉÊ ÐÏÐÁÒÎÏ ÒÁÚÌÉÞÎÙ, ÔÏ ÕÍÅÎØÛÉ× ×ÅÓ ÉÇÒÏËÁ i, ÍÏÖÎÏ ÄÏÂÉÔØÓÑ ÔÏÇÏ, ÞÔÏÂÙ ×ÙÉÇÒÙ×ÁÀÝÉÍÉ ÏÓÔÁÌÉÓØ ×ÓÅ ÔÅ ÖÅ ËÏÁÌÉÃÉÉ, ËÒÏÍÅ ÏÄÎÏÊ, ÓÏÄÅÒÖÁÝÅÊ i.äÏËÁÖÅÍ ÓÎÁÞÁÌÁ Ç1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
