close

Вход

Забыли?

вход по аккаунту

?

Смежность вершин многогранника к-факторов.

код для вставкиСкачать
Ма▓ема▓и╖е▒кие
▒▓░│к▓│░╗ и модели░ование
1998. В╗п. 2, ▒.39-50.
УДК 519.1
СМЕЖНОСТЬ ВЕРШИН
МНОГОГРАННИКА
K
-ФАКТОРОВ
Р.Ю.Симан╖
ев
In this paper the criterion of adjacency of the vertices one of the polyhedral
relaxations of k-factors polytope was received. The particularity given criterion is that it is worded in graph terms. Received criterion gives sucient
conditions of adjacency of vertices corresponding integer polytope.
В ░┐де алго░и▓мов комбина▓о░ной оп▓имиза╢ии ╕и░око и▒пол╝з│е▓▒┐ ин┤о░ма╢и┐ о поли╜д░ал╝ной ▒▓░│к▓│░е в╗п│кл╗╡ оболо╖ек доп│▒▓им╗╡ ░е╕ений ░а▒▒ма▓░иваем╗╡ зада╖. Ши░окий кла▒▒ об░аз│╛▓ ╜к▒▓░емал╝н╗е зада╖и
в ▒лед│╛╣ей по▒▓ановке. П│▒▓╝ E { коне╖ное множе▒▓во, c : E ! R { адди▓ивн╗й ┤│нк╢ионал на E , = 2E { неко▓о░ое ▒емей▒▓во подмноже▒▓в множе▒▓ва
E . Т░еб│е▓▒┐ най▓и ▓акой H 2 =, ╖▓о c(H ) c(H ) дл┐ л╛бого H 2 =.
Поли╜д░ал╝н╗й под╡од к анализ│ и ░е╕ени╛ ▓акой зада╖и закл╛╖ае▓▒┐ в ▒опо▒▓авлении ╜▓ой зада╖е ▒пе╢иал╝ного (0; 1)-многог░анника и и▒пол╝зовании
поли╜д░ал╝н╗╡ и комбина▓о░н╗╡ ▒вой▒▓в по▒леднего. Множе▒▓в│ E ▒опо▒▓авим евклидово п░о▒▓░ан▒▓во RE , име┐ в вид│ взаимнооднозна╖ное ▒оо▓ве▓▒▓вие межд│ E и множе▒▓вом коо░дина▓н╗╡ о▒ей п░о▒▓░ан▒▓ва RE , дл┐ л╛бого F 2 2E оп░еделим его век▓о░ ин╢иден╢ий xF 2 RE как век▓о░-▒▓олбе╢
▒ компонен▓ами xFe = 1 п░и e 2 F , xFe = 0 п░и e 2= F . Таким об░азом, м╗
пол│╖аем взаимнооднозна╖ное ▒оо▓ве▓▒▓вие межд│ 2E и множе▒▓вом ве░╕ин
едини╖ного к│ба в RE . Тепе░╝ положим
P (=) = convfxH 2 RE j H 2 =g:
В ▒ил│ адди▓ивно▒▓и ┤│нк╢ионал c : E ! R е▒▓е▒▓венн╗м об░азом а▒▒о╢ии░│е▓▒┐ ▒ линейн╗м ┤│нк╢ионалом fc : RE ! R, п░и╖ем c(F ) = fc (xF ) дл┐ л╛бого
F E.
Как │же гово░ило▒╝, поли╜д░ал╝на┐ ▒▓░│к▓│░а многог░анника P (=) иг░ае▓
▒│╣е▒▓венн│╛ ░ол╝ п░и ░аз░або▓ке алго░и▓мов ░е╕ени┐ зада╖и. Нап░име░,
полное или ╖а▒▓и╖ное линейное опи▒ание многог░анника P (=) позвол┐е▓ п░имен┐▓╝ дл┐ ░е╕ени┐ зада╖и аппа░а▓ линейного и ╢ело╖и▒ленного линейного
c 1998 Р.Ю. Симан╖ев
E-mail: siman@univer.omsk.su
Ом▒кий го▒│да░▒▓венн╗й │ниве░▒и▓е▓
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
40
п░ог░амми░овани┐ [5]; диаме▓░ P (=) може▓ ▒л│жи▓╝ о╢енкой ╖и▒ла и▓е░а╢ий
└наил│╖╕ей┴ ▒имплек▒ной п░о╢ед│░╗ [5]; кла▒▒╗ ▒межн╗╡ ве░╕ин [1, 2] ве▒╝ма
полезн╗ п░и ░аз░або▓ке алго░и▓мов локал╝ной оп▓имиза╢ии и ░е╕ении зада╖и
иден▓и┤ика╢ии п░авил╝н╗╡ не░авен▒▓в [4].
Один из под╡одов к в╗делени╛ ▒межн╗╡ ве░╕ин многог░анника P (=) закл╛╖ае▓▒┐ в ▒лед│╛╣ем. У▒ловим▒┐ ╖е░ез vertM обозна╖а▓╝ множе▒▓во в▒е╡
ве░╕ин многог░анного множе▒▓ва M . П│▒▓╝ M (=) { неко▓о░а┐ ░елак▒а╢и┐
многог░анника P (=), ▓.е. P (=) M (=). Релак▒а╢и╛ M (=) б│дем наз╗ва▓╝
поли╜д░ал╝ной , е▒ли M (=) = fx 2 RE j Ax bg, где A { (n j E j)ма▓░и╢а, b { n-век▓о░. Е▒ли M (=) { многог░анное множе▒▓во и x1; x2 2
(vertP (=)) \ (vertM (=)) ▒межн╗ в M (=), ▓о они, о╖евидно, ▒межн╗ и в P (=).
В ▒л│╖ае, когда ░елак▒а╢и┐ M (=) поли╜д░ал╝на┐, воп░о▒ о ▒межно▒▓и ▓о╖ек
x1; x2 2 vertM (=) можно анализи░ова▓╝ на о▒нове подма▓░и╢╗ об╣и╡ дл┐ x1 и
x2 линейн╗╡ ог░ани╖ений. Однако п░и до▒▓а▓о╖но бол╝╕ом j E j в╗╖и▒ление
░анга ▒оо▓ве▓▒▓в│╛╣ей подма▓░и╢╗ за▓░│дни▓ел╝но и по╜▓ом│ имее▓ ▒м╗▒л
пои▒к комбина▓о░н╗╡ к░и▓е░иев ▒межно▒▓и ве░╕ин ░елак▒а╢ии M (=). В на▒▓о┐╣ей ▒▓а▓╝е ╜▓о▓ под╡од п░имен┐е▓▒┐ к многог░анник│ k-┤ак▓о░ов полного
г░а┤а.
Нам понадоб┐▓▒┐ ▒лед│╛╣ие пон┐▓и┐ и обозна╖ени┐.
П│▒▓╝ Rd { d-ме░ное ве╣е▒▓венное п░о▒▓░ан▒▓во. А┤┤инной комбина╢ией
век▓о░ов
x1; : : :; xt п░о▒▓░ан▒▓ва
Rd наз╗вае▓▒┐ в▒┐кий век▓о░ x =
Pt xi, (▓о╖ек)
P
t
i=1 i │довле▓во░┐╛╣ий │▒лови╛ i=1 i = 1. Е▒ли к ╜▓ом│ добавлено │▒ловие i 0; i = 1; : : :t, ▓о век▓о░ x наз╗вае▓▒┐ в╗п│клой комбина╢ией век▓о░ов
x1; : : :; xt. В╗п│клой оболо╖кой п░оизвол╝ного множе▒▓ва S RE наз╗вае▓▒┐
множе▒▓во convS , ▒о▒▓о┐╣ее из в▒евозможн╗╡ в╗п│кл╗╡ комбина╢ий ▓о╖ек
множе▒▓ва S ; а┤┤инной оболо╖кой { affS { наз╗вае▓▒┐ множе▒▓во в▒евозможн╗╡ а┤┤инн╗╡ комбина╢ий ▓о╖ек множе▒▓ва S . Семей▒▓во век▓о░ов x1; : : :; xt
п░о▒▓░ан▒▓ва RE б│дем наз╗ва▓╝ а┤┤инно незави▒им╗м, е▒ли ни один из ╜▓и╡
век▓о░ов не ┐вл┐е▓▒┐ а┤┤инной комбина╢ией о▒▓ал╝н╗╡. Под ░азме░но▒▓╝╛
в╗п│клого множе▒▓ва S RE { dimS { б│дем понима▓╝ мо╣но▒▓╝ мак▒имал╝ного а┤┤инно незави▒имого ▒емей▒▓ва его ▓о╖ек мин│▒ 1.
В╗п│кл╗м многог░анником (или п░о▒▓о многог░анником) в п░о▒▓░ан▒▓ве
Rd наз╗вае▓▒┐ в╗п│кла┐ оболо╖ка коне╖ного множе▒▓ва ▓о╖ек ╜▓ого п░о▒▓░ан▒▓ва. М╗ оп░еделим поли╜д░ в d-ме░ном ве╣е▒▓венном п░о▒▓░ан▒▓ве
как множе▒▓во ░е╕ений коне╖ной ▒и▒▓ем╗ линейн╗╡ │░авнений и не░авен▒▓в
о▓но▒и▓ел╝но d пе░еменн╗╡, е▒ли оно ог░ани╖ено. Согла▒но ▓ео░еме Вейл┐Минков▒кого, дл┐ в▒┐кого в╗п│клого многог░анника P ▒│╕е▒▓в│е▓ ▓акой поли╜д░ F , ╖▓о P = F . Ве░но и об░а▓ное: в▒┐кий поли╜д░ ┐вл┐е▓▒┐ многог░анником.
Г░ан╝╛ многог░анника P наз╗вае▓▒┐ множе▒▓во fx 2 P j aT x = a0g, где
T
a x a0 { опо░ное к P не░авен▒▓во. Г░ан╝ наз╗вае▓▒┐ p-г░ан╝╛, е▒ли ее ░азме░но▒▓╝ ░авна p, 0-г░ани наз╗ва╛▓▒┐ ве░╕инами, 1-г░ани { ░еб░ами многог░анника P . Две ве░╕ин╗ ▒межн╗ в P , е▒ли они п░инадлежа▓ одном│ ░еб░│
многог░анника P . Я▒но, ╖▓о е▒ли P { поли╜д░, ▓о 1) x 2 P ┐вл┐е▓▒┐ ве░╕иной ▓огда и ▓ол╝ко ▓огда, когда ░анг подма▓░и╢╗ ог░ани╖ений, об░а╣аем╗╡
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
41
▓о╖кой x в ░авен▒▓во, ░авен d; 2) две ве░╕ин╗ x1; x2 2 P ▒межн╗ в P ▓огда и ▓ол╝ко ▓огда, когда ░анг подма▓░и╢╗ ог░ани╖ений, об░а╣аем╗╡ ╜▓ими
▓о╖ками в ░авен▒▓во однов░еменно, ░авен d 1.
П│▒▓╝ Kn = (V; E ) { полн╗й нео░иен▓и░ованн╗й г░а┤ без пе▓ел╝ и к░а▓н╗╡
░ебе░ ▒ множе▒▓вами ве░╕ин V и ░ебе░ E , j V j= n. Дл┐ в▒┐кого G 2 Kn ╖е░ез
V G и EG обозна╖им ▒оо▓ве▓▒▓венно множе▒▓ва ве░╕ин и ░ебе░ г░а┤а G. П░и
╜▓ом дл┐ ░еб░а e 2 E б│дем ▓акже и▒пол╝зова▓╝ запи▒╝ uv, понима┐ u; v 2 V
как па░│ ин╢иден▓н╗╡ ░еб░│ e ве░╕ин. Дл┐ W V положим
EG (W ) EEG(W ) = fuv 2 EG j u; v 2 W g;
G(W ) EG(W ) = fuv 2 EG j u 2 W; v 2= W g:
С▓епен╝╛ о▓но▒и▓ел╝но G (или EG) п░оизвол╝ной ве░╕ин╗ u 2 V назовем вели╖ин│ dG (u) dEG (u) =j G (u) j. Е▒ли G = Kn , ▓о в обозна╖ени┐╡
EG (W ); G(W ) и dG (u) ▒имвол └G┴ б│дем оп│▒ка▓╝. В▒┐кое R E инд│╢и░│е▓ неко▓о░╗й подг░а┤ T , │ ко▓о░ого ET = R и V T { множе▒▓во ве░╕ин
из V , ин╢иден▓н╗╡ ░еб░ам множе▒▓ва R. В ╜▓ой ▒в┐зи ▓ам, где не возникае▓
дв│▒м╗▒ленно▒▓и, г░а┤, инд│╢и░ованн╗й множе▒▓вом ░ебе░ R, б│дем п░о▒▓о
обозна╖а▓╝ ╖е░ез R. Дл┐ па░╗ г░а┤ов G; F Kn под G [ F б│дем понима▓╝
▓акой г░а┤ H , ╖▓о V H = V G [ V F и EH = EG [ EF , а под G \ F { г░а┤, инд│╢и░ованн╗й множе▒▓вом ░ебе░ EG \ EF . И наконе╢, п░о▒▓╗м ╢иклом назовем
▓акой ▒в┐зн╗й подг░а┤ C Kn , ╖▓о dC (u) = 2 дл┐ в▒е╡ u 2 V C . П░и ╜▓ом
п░о▒▓ой ╢икл б│дем ▓акже задава▓╝ либо по▒ледова▓ел╝н╗м ▒пи▒ком ве░╕ин,
либо по▒ледова▓ел╝н╗м ▒пи▒ком ░ебе░. П░о▒▓ой ╢икл наз╗вае▓▒┐ ╖е▓н╗м, е▒ли
он имее▓ ╖е▓ное ╖и▒ло ░ебе░, не╖е▓н╗м { в п░о▓ивном ▒л│╖ае.
Дл┐ x 2 RE и R E оп░еделим линейн│╛ ┤о░м│
x(R) =
X
e2R
xe:
В╗бе░ем ▓акое на▓│░ал╝ное k, ╖▓о 1 k n 1 и kn { ╖е▓но. Под k┤ак▓о░ом г░а┤а Kn б│дем понима▓╝ о▒▓овн╗й одно░одн╗й ▒▓епени k подг░а┤.
множе▒▓во в▒е╡ k -┤ак▓о░ов, а ╖е░ез k;n { множе▒▓во
Обозна╖им ╖е░ез k;n
в▒е╡ ▒в┐зн╗╡ k-┤ак▓о░ов г░а┤а Kn . Заме▓им, нап░име░, ╖▓о 2;n { множе▒▓во
гамил╝▓онов╗╡ ╢иклов полного г░а┤а. Сопо▒▓авим множе▒▓в│ E евклидово
п░о▒▓░ан▒▓во RE , а каждом│ F Kn { его век▓о░ ин╢иден╢ий xF xEF 2 RE
▓ак, как ╜▓о опи▒ано в╗╕е. П│▒▓╝
= conv fxH 2 RE j H 2 g;
Pk;n
k;n
Pk;n = convfxH 2 RE j H 2 k;ng
{ многог░анники k-┤ак▓о░ов и ▒в┐зн╗╡ k-┤ак▓о░ов ▒оо▓ве▓▒▓венно.
С г░а┤ом Kn ▒в┐жем его ве░╕инно-░ебе░н│╛ ма▓░и╢│ ин╢иден╢ий A.
С▓░│к▓│░а ма▓░и╢╗ A ▓акова: ▒▓░оки ▒оо▓ве▓▒▓в│╛▓ ╜лемен▓ам множе▒▓ва
V , а ▒▓олб╢╗ { ╜лемен▓ам множе▒▓ва E и п░и ╜▓ом в кле▓ке (u; e) ▒▓ои▓ 1,
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
42
е▒ли ве░╕ина u ин╢иден▓на ░еб░│ e, и 0 { в п░о▓ивном ▒л│╖ае. Легко заме▓и▓╝, ╖▓о A ▒о▒▓ои▓ из в▒евозможн╗╡ ▒▓олб╢ов ▒ дв│м┐ едини╢ами и (n 2)
н│л┐ми. Ма▓░и╢│ ин╢иден╢ий п░оизвол╝ного F Kn обозна╖им ╖е░ез A(F ).
Она, о╖евидно, ┐вл┐е▓▒┐ подма▓░и╢ей ма▓░и╢╗ A, об░азованной пе░е▒е╖ением
▒▓░ок V F и ▒▓олб╢ов EF .
Положим
Mk;n = fx 2 RE j Ax = k; 0 x 1g;
где k { век▓о░-▒▓олбе╢ ▒ n компонен▓ами ░авн╗ми k, 0 и 1 аналоги╖но. В ▓е░мина╡ Kn ▒и▒▓ема, оп░едел┐╛╣а┐ Mk;n , може▓ б╗▓╝ запи▒ана в виде
x((u)) = k; u 2 V;
(1)
0 xe 1; e 2 E:
(2)
Не▓░│дно заме▓и▓╝, ╖▓о век▓о░ ин╢иден╢ий л╛бого k-┤ак▓о░а │довле▓во░┐е▓ ▒и▒▓еме (2:1) (2:2). Следова▓ел╝но, множе▒▓во Mk;n можно ░а▒▒ма▓░ива▓╝
и Pk;n . К░оме ▓ого, ▓ак
как поли╜д░ал╝н│╛ ░елак▒а╢и╛ многог░анников Pk;n
E
vertMk;n . Э▓а
как Mk;n е▒▓╝ подмноже▒▓во едини╖ного к│ба в R , ▓о vertPk;n
░елак▒а╢и┐ и▒пол╝зовала▒╝ в ░або▓а╡ [3, 4, 6].
В ░або▓е [7] б╗ло показано, ╖▓о Mk;n имее▓ не╢ело╖и▒ленн╗е ве░╕ин╗.
П│▒▓╝ x 2 Mk;n. С ▓о╖кой x ▒в┐жем ▒лед│╛╣ие подг░а┤╗:
Cx { г░а┤ д░обно▒▓и ▓о╖ки x { инд│╢и░ован множе▒▓вом ░ебе░ ECx = fe 2
E j 0 < xe < 1g;
Tx { г░а┤ едини╢ ▓о╖ки x { инд│╢и░ован множе▒▓вом ░ебе░ ETx = fe 2 E j
xe = 1g.
В ▓е░мина╡ ╜▓и╡ г░а┤ов ▒▓░│к▓│░а не╢ело╖и▒ленн╗╡ ве░╕ин поли╜д░а Mk;n
може▓ б╗▓╝ опи▒ана ▒лед│╛╣им об░азом.
Тео░ема 1. [7]. То╖ка x 2 Mk;n ┐вл┐е▓▒┐ ве░╕иной поли╜д░а Mk;n ▓огда
и ▓ол╝ко ▓огда, когда она ╢ело╖и▒ленна, либо ее г░а┤ д░обно▒▓и Cx и г░а┤
едини╢ Tx │довле▓во░┐╛▓ │▒лови┐м:
1) Cx е▒▓╝ об║единение ╖е▓ного ╖и▒ла п░о▒▓╗╡ ве░╕инно-непе░е▒ека╛╣и╡▒┐ не╖е▓н╗╡ ╢иклов, п░и╖ем дл┐ л╛бого e 2 ECx имее▓ ме▒▓о xe = 12 ;
2) dTx (u) = k 1 дл┐ в▒е╡ u 2 V Cx и dTx (u) = k дл┐ в▒е╡ u 2 V n V Cx.
П│▒▓╝ x1; x2 2 Mk;n { па░а ░азли╖н╗╡ ▓о╖ек. Нам понадоб┐▓▒┐ ▒лед│╛╣ие
обозна╖ени┐:
R(x1; x2) = fe 2 E j x1e ; x2e 2 f0; 1g; x1e + x2e = 1g;
R(x1; x2) = E n fR(x1; x2) [ E (Cx1 [ Cx2 )g;
U (x1; x2) = fu 2 V n V (Cx1 [ Cx2 ) j Tx1 (u) = Tx2 (u)g;
Gx1 ;x2 { компонен▓╗ ▒в┐зно▒▓и г░а┤а, инд│╢и░ованного множе▒▓вом ░ебе░
R(x1; x2), не ▒оде░жа╣ие ве░╕ин из V (Cx1 [ Cx2 ).
К░оме ▓ого, дл┐ л╛б╗╡ W V и R E положим W = V n W и под B (W; R)
б│дем понима▓╝ подма▓░и╢│ ма▓░и╢╗ A(Kn) = A, об░азованн│╛ ▒▓░оками,
▒оо▓ве▓▒▓в│╛╣ими ве░╕инам множе▒▓ва W , и ▒▓олб╢ами, ▒оо▓ве▓▒▓в│╛╣ими
░еб░ам множе▒▓ва R.
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
43
Воп░о▒ о ▒межно▒▓и па░╗ ве░╕ин x1 и x2 поли╜д░а Mk;n б│дем анализи░ова▓╝ на о▒нове под▒и▒▓ем╗ ▒и▒▓ем╗ (1)-(2), об░азованной ог░ани╖ени┐ми,
ко▓о░╗е однов░еменно об░а╣а╛▓▒┐ в ░авен▒▓во ▓о╖ками x1; x2. Ма▓░и╢│ ╜▓ой
под▒и▒▓ем╗ обозна╖им ╖е░ез A(x1; x2). Указанна┐ под▒и▒▓ема в╗гл┐ди▓, о╖евидно, ▒лед│╛╣им об░азом:
AT x = k;
xe = 0 или 1; e 2 R(x1; x2):
Ма▓░и╢│ A(x1; x2) ▒╡ема▓и╖но можно изоб░ази▓╝ ▓ак, как показано на ░и▒│нке.
E (Cx1 [ Cx2 ) R(x1; x2) R(x1; x2)
V (Cx1 [ Cx2 )
V (Cx1
[
Cx2 )
R(x1; x2)
0
0
0
0
0
U (x1; x2)
I
Зде▒╝ I { едини╖на┐ ма▓░и╢а.
Так как в п░авом нижнем │гл│ ма▓░и╢╗ A(x1; x2) ▒▓ои▓ едини╖на┐ ма▓░и╢а,
▓о, обозна╖а┐ ╖е░ез B ма▓░и╢│ B (V nU (x1; x2); E (Cx1 [Cx2 )[R(x1; x2)), пол│╖им
rankA(x1; x2) = jR(x1; x2)j + rankB:
(3)
Тео░ема 2. П│▒▓╝ x1; x2 2 Mk;n { ве░╕ин╗, R(x1; x2) = ;. Тогда x1 и x2
▒межн╗ в Mk;n , е▒ли и ▓ол╝ко е▒ли
jV (Cx1 [ Cx2 )j = jE (Cx1 [ Cx2 )j 1:
Доказа▓ел╝▒▓во. Необ╡одимо▒▓╝. П│▒▓╝ x1 и x2 ▒межн╗. Тогда
о▓к│да
n2 n 1 = rankA(x1; x2) = jR(x1; x2)j + rankA(C 1 [ C 2 );
x
x
2
rankA(Cx1 [ Cx2 ) = n
2
n 1 jR(x1; x2)j = jE (C 1 [ C 2 )j 1:
x
x
2
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
44
Так как в Cx1 [ Cx2 не▓ ви▒┐╖и╡ ве░╕ин, ▓о jV (Cx1 [ Cx2 )j jE (Cx1 [ Cx2 )j.
Таким об░азом,
jE (Cx1 [ Cx2 )j 1 = rankA(Cx1 [ Cx2 ) jV (Cx1 [ Cx2 )j jE (Cx1 [ Cx2 )j:
П░едположим, ╖▓о jV (Cx1 [ Cx2 )j = jE (Cx1 [ Cx2 )j. Тогда Cx1 [ Cx2 { набо░
непе░е▒ека╛╣и╡▒┐ не╖е▓н╗╡ ╢иклов, о▓к│да ▒лед│е▓, ╖▓о
rankA(Cx1 [ Cx2 ) = jV (Cx1 [ Cx2 )j = jE (Cx1 [ Cx2 )j:
Э▓о, о╖евидно, п░о▓иво░е╖и▓ │▒лови╛ rankA(x1; x2) = n22 n 1. Зна╖и▓, jV (Cx1 [
Cx2 )j = jE (Cx1 [ Cx2 )j 1.
До▒▓а▓о╖но▒▓╝. Из ░авен▒▓ва jV (Cx1 [ Cx2 )j = jE (Cx1 [ Cx2 )j 1 и ▓ого,
╖▓о Cx1 , Cx2 { набо░╗ не╖е▓н╗╡ ╢иклов, ▒лед│е▓, ╖▓о Cx1 [ Cx2 либо набо░ не╖е▓н╗╡ ╢иклов, ▒░еди ко▓о░╗╡ име╛▓▒┐ ░овно два ▒ об╣ей ве░╕иной, либо набо░ не╖е▓н╗╡ ╢иклов ▒ одной ╡о░дой. Непо▒░ед▒▓венн╗ми в╗╖и▒лени┐ми легко
│беди▓╝▒┐, ╖▓о в обои╡ ▒л│╖а┐╡ ма▓░и╢а A(Cx1 [ Cx2 ) имее▓ полн╗й ░анг, ▓.е.
rankA(Cx1 [ Cx2 ) = jE (Cx1 [ Cx2 )j 1. О▓▒╛да
rankA(x1; x2) = jR(x1; x2)j + rankA(Cx1 [ Cx2 ) =
2
= jR(x1; x2)j + jE (Cx1 [ Cx2 j 1 = n 2 n 1;
╖▓о озна╖ае▓ ▒межно▒▓╝ ве░╕ин x1 и x2.
Тео░ема доказана.
Дл┐ анализа ▒межно▒▓и ве░╕ин в ▒л│╖ае R(x1; x2) 6= ; нам понадоб┐▓▒┐
▒лед│╛╣ие │▓ве░ждени┐. Б│дем обозна╖а▓╝ V (Cx1 [ Cx2 ) = V n V (Cx1 [ Cx2 ).
П░едложение 1. П│▒▓╝ x1; x2 2 Mk;n { ве░╕ин╗ и R(x1; x2) 6= ;. Тогда
rankB (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)) = jV (Cx1 [ Cx2 )j
jU (x1; x2)j jV Gx1;x2 j + rankA(Gx1;x2 ):
(4)
Доказа▓ел╝▒▓во. В ма▓░и╢е B (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)) кажд╗й
▒▓олбе╢ ▒оде░жи▓ не более дв│╡ едини╢. П│▒▓╝ R1 R(x1; x2) { ▓е ▒▓олб╢╗,
в ко▓о░╗╡ ▒▓ои▓ ░овно по одной едини╢е. Э▓о озна╖ае▓, ╖▓о один коне╢ л╛бого ░еб░а из R1 лежи▓ в V (Cx1 [ Cx2 ). П│▒▓╝ V1 V (Cx1 [ Cx2 ) { множе▒▓во
в▒е╡ ве░╕ин, ин╢иден▓н╗╡ ░еб░ам из R1. Я▒но, ╖▓о ма▓░и╢а B (fV (Cx1 [ Cx2 ) n
U (x1; x2)g n V1; R1) ▒о▒▓ои▓ из н│лей и rankB (V1; R1) = jV1j. Тогда
rankB (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)) = jV1j+
+B (fV (Cx1 [ Cx2 ) n U (x1; x2)g n V1; R(x1; x2) n R1):
П░о▒ма▓░ива┐ аналоги╖н╗м об░азом ▒▓олб╢╗ по▒ледней ма▓░и╢╗, в╗дел┐ем
множе▒▓во ░ебе░ R2 R(x1; x2), один коне╢ каждого из ко▓о░╗╡ лежи▓ в V1
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
45
(▓.е. в ▒▓олб╢е e 2 R2 ╜▓ой ма▓░и╢╗ имее▓▒┐ ░овно одна едини╢а), и множе▒▓во ве░╕ин V2 fV (Cx1 [ Cx2 ) n U (x1; x2)g n V1, ин╢иден▓н╗╡ ╜▓им ░еб░ам.
П░одолжа┐ п░о▒мо▓░, добе░ем▒┐ до ▓аки╡ Rt и Vt , ╖▓о ма▓░и╢а
+B (fV (Cx1 [ Cx2 ) n U (x1; x2)g n [ti=1Vi ; R(x1; x2) n [ti=1Ri)
б│де▓ либо п│▒▓ой, либо в каждом ее ▒▓олб╢е б│де▓ ░овно по две едини╢╗.
Не▓░│дно заме▓и▓╝, ╖▓о ╜▓а ма▓░и╢а и б│де▓ ма▓░и╢ей A(Gx1;x2 ). П░и ╜▓ом в
▒ил│ ▓ого, ╖▓о j [ti=1 Vij = jV (Cx1 [ Cx2 )j jU (x1; x2)j jV Gx1;x2 j, пол│╖аем
rankB (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)) = j [ti=1 Vi j + rankA(Gx1;x2 ) =
= jV (Cx1 [ Cx2 )j jU (x1; x2)j jV Gx1 ;x2 j + rankA(Gx1;x2 ):
У▓ве░ждение доказано.
П░едложение 2. П│▒▓╝ x1; x2 2 Mk;n { ве░╕ин╗ и R(x1; x2) 6= ;. В▒┐-
кий изоли░ованн╗й п░о▒▓ой ╢икл в г░а┤е, инд│╢и░ованном множе▒▓вом ░ебе░
R(x1; x2), ╖е▓ен.
Доказа▓ел╝▒▓во. В ▒амом деле, п░едположим, ╖▓о ▒░еди ▓аки╡ ╢иклов
найде▓▒┐ не╖е▓н╗й { ▒кажем, C = fe1; e2; : : : etg. Л╛бое ░еб░о, ин╢иден▓ное
какой-либо ве░╕ине ╜▓ого ╢икла и о▓ли╖ное о▓ ei, i = 1; : : : t, не п░инадлежи▓ R(x1; x2). Зна╖и▓, полага┐, без ог░ани╖ени┐ об╣но▒▓и, ╖▓о e1 2 ETx1 , закл╛╖аем, ╖▓о e2 2 ETx2 , e3 2 ETx1 , . . . , e2l 2 ETx2 , e2l+1 2 ETx1 , . . . , et 2 ETx1 .
Таким об░азом, из ве░╕ин╗ u, об╣ей дл┐ ░ебе░ e1 и e2, в╗╡од┐▓ два ░еб░а,
п░инадлежа╣ие Tx1 . Но ▓ак как в ▒ил│ ▓ео░ем╗ 3.1, дл┐ л╛бой u 2 V в╗полн┐е▓▒┐ ░авен▒▓во dTx1 (u) = dTx2 (u), ▓о из ве░╕ин╗ u неп░еменно в╗╡од┐▓ е╣е два
░еб░а, лежа╣ие в Tx2 . (П░едпо▒╗лка └dTx1 (u) = dTx2 (u) дл┐ в▒е╡ u 2 V ┴ в ▒л│╖ае
k = 2 имее▓ иной вид, а имеено └dTx1 (u) = dTx2 (u) дл┐ в▒е╡ u 2 V (Cx1 [ Cx2 )┴.
Но ╜▓о не ме╕ае▓ доказа▓ел╝▒▓в│, ибо п░и k = 2 нали╖ие в R(x1; x2) ░еб░а, ин╢иден▓ного какой-либо ве░╕ине из V (Cx1 [ Cx2 ) озна╖ае▓, ╖▓о ░еб░а R(x1; x2)
не инд│╢и░│╛▓ набо░а ╢иклов.) Таким об░азом, dR(x1;x2)(u) 4, ╖▓о п░о▓иво░е╖и▓ │▒лови╛ │▓ве░ждени┐.
Тео░ема 3. П│▒▓╝ x1; x2 2 Mk;n { ве░╕ин╗ и R(x1; x2) 6= ;. Е▒ли x1 и x2
▒межн╗ в Mk;n , ▓о
jV (Cx1 [ Cx2 )j jR(x1; x2)j + jU (x1; x2)j jV (Cx1 [ Cx2 )j + 1
и Cx1 [ Cx2 ┐вл┐е▓▒┐ набо░ом п░о▒▓╗╡ ве░╕инно-непе░е▒ека╛╣и╡▒┐ ╢иклов.
Доказа▓ел╝▒▓во. В ▒ил│ (3)
2
rankB = rankA(x1; x2) jR(x1; x2)j = n 2 n 1 jR(x1; x2)j =
(5)
= jE (Cx1 [ Cx2 )j + jR(x1; x2)j 1 Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
46
jV (Cx1 [ Cx2 )j + jV (Cx1 [ Cx2 )j jU (x1; x2)j:
Так как в Cx1 [ Cx2 не▓ ви▒┐╖и╡ ве░╕ин, ▓о из (5) имеем
0 jE (Cx1 [ Cx2 )j + jV (Cx1 [ Cx2 )j jV (Cx1 [ Cx2 )j jU (x1; x2)j jR(x1; x2)j + 1;
(6)
jR(x1; x2)j jV (Cx1 [ Cx2 )j jU (x1; x2)j + 1:
Заме▓им, ╖▓о в▒┐ка┐ ве░╕ина из V (Cx1 [Cx2 )nU (x1; x2) ин╢иден▓на не менее,
╖ем дв│м ░еб░ам из R(x1; x2), ▓.е. дл┐ в▒е╡ u 2 V (Cx1 [ Cx2 ) n U (x1; x2) имеем
dR(x1;x2)(u) 2. С│мми░│┐ ╜▓и ▒▓епени ▒ ко╜┤┤и╢иен▓ом 21 по в▒ем ве░╕инам
из V (Cx1 [ Cx2 ) n U (x1; x2), пол│╖аем не░авен▒▓во
jR(x1; x2)j jV (Cx1 [ Cx2 )j jU (x1; x2)j:
(7)
Покажем, ╖▓о Cx1 [ Cx2 { набо░ непе░е▒ека╛╣и╡▒┐ ╢иклов. Из (6) и (7)
▒лед│е▓, ╖▓о 0 jE (Cx1 [ Cx2 )j jV (Cx1 [ Cx2 )j 1. П░едположим, ╖▓о jE (Cx1 [
Cx2 )j = jV (Cx1 [ Cx2 )j + 1. Тогда
jR(x1; x2)j = jV (Cx1 [ Cx2 )j jU (x1; x2)j:
(8)
Из (5) ▒лед│е▓, ╖▓о е▒ли e = uv 2 R(x1; x2), ▓о неп░еменно u; v 2 V (Cx1 [
Cx2 ) n U (x1; x2). Дей▒▓ви▓ел╝но, в п░о▓ивном ▒л│╖ае ▒│╣е▒▓в│е▓ ▓акое e = uv 2
R(x1; x2), ╖▓о либо u; v 2 V (Cx1 [ Cx2 ), либо u 2 V (Cx1 [ Cx2 ) и v 2 V (Cx1 [ Cx2 ).
В пе░вом ▒л│╖ае в ▒ил│ ▓ого, ╖▓о в▒┐ка┐ ве░╕ина из V (Cx1 [ Cx2 ) n U (x1; x2)
ин╢иден▓на не менее, ╖ем дв│м ░еб░ам из R(x1; x2), имеем
X
jR(x1; x2)j 21 f
dR(x1;x2)(w)g + 1 w2V nU (x1;x2 )
jV (Cx1 [ Cx2 )j jU (x1; x2)j + 1;
╖▓о п░о▓иво░е╖и▓ (8). Во в▓о░ом ▒л│╖ае, обозна╖ив множе▒▓во fV n U (x1; x2)gn
fvg ╖е░ез V 0, пол│╖им
X
jR(x1; x2)j 12 f dR(x1;x2)(w) + dR(x1;x2)(v) 1g + 1 w 2V 0
jV (Cx1 [ Cx2 )j jU (x1; x2)j + 12 ;
╖▓о ▓акже п░о▓иво░е╖и▓ (8).
Так как в каждом ▒▓олб╢е ма▓░и╢╗ A(Kn) ▒▓о┐▓ ░овно по две едини╢╗, ▓о
из показанного ▒лед│е▓, ╖▓о ма▓░и╢а B (V (Cx1 [ Cx2 ); R(x1; x2)) н│лева┐. К░оме
▓ого, ╜▓о и (6) влек│▓ ▓о▓ ┤ак▓, ╖▓о ма▓░и╢а B (V (Cx1 [Cx2 )nU (x1; x2); R(x1; x2))
┐вл┐е▓▒┐ ма▓░и╢ей ин╢иден╢ий неко▓о░ого г░а┤а L, п░и╖ем она квад░а▓на┐.
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
47
Следова▓ел╝но, г░а┤ L ┐вл┐е▓▒┐ набо░ом п░о▒▓╗╡ непе░е▒ека╛╣и╡▒┐ ╢иклов.
О▓▒╛да, в ▒ил│ │▓ве░ждени┐ 2, пол│╖аем, ╖▓о ╜▓и ╢икл╗ ╖е▓н╗е и по╜▓ом│
rankA(L) < jV (Cx1 [ Cx2 )j jU (x1; x2)j = jR(x1; x2)j:
Тогда из п░едположени┐ jE (Cx1 [ Cx2 )j = jV (Cx1 [ Cx2 )j + 1 в╗▓екае▓, ╖▓о
rankB = rankA(Cx1 [ Cx2 ) + rankA(L) < jV (Cx1 [ Cx2 )j+
+jR(x1; x2)j = jE (Cx1 [ Cx2 )j 1 + jR(x1; x2)j;
╖▓о п░о▓иво░е╖и▓ ░авен▒▓в│ (5). Таким об░азом, jE (Cx1 [ Cx2 )j = jV (Cx1 [ Cx2 )j
и по╜▓ом│ Cx1 [ Cx2 { набо░ п░о▒▓╗╡ ве░╕инно непе░е▒ека╛╣и╡▒┐ ╢иклов.
Тео░ема доказана.
Тео░ема 4. П│▒▓╝ x1; x2 2 Mk;n { ве░╕ин╗, R(x1; x2) 6= ;, Cx1 [ Cx2 { набо░
п░о▒▓╗╡ ве░╕инно-непе░е▒ека╛╣и╡▒┐ ╢иклов. Сп░аведлив╗ ▒лед│╛╣ие │▓ве░ждени┐:
1) е▒ли jR(x1; x2)j + jU (x1; x2)j = jV (Cx1 [ Cx2 )j + 1, ▓о ве░╕ин╗ x1 и x2
▒межн╗ в Mk;n ▓огда и ▓ол╝ко ▓огда, когда Gx1;x2 либо п│▒▓, либо ┐вл┐е▓▒┐
па░ой п░о▒▓╗╡ не╖е▓н╗╡ ╢иклов ▒ одной об╣ей ве░╕иной;
2) е▒ли jR(x1; x2)j + jU (x1; x2)j = jV (Cx1 [ Cx2 )j, ▓о ве░╕ин╗ x1 и x2 ▒межн╗
в Mk;n ▓огда и ▓ол╝ко ▓огда, когда Gx1 ;x2 { ╖е▓н╗й ╢икл.
Доказа▓ел╝▒▓во. Из │▒лови┐ ▓ео░ем╗ и не╖е▓но▒▓и ╢иклов, об░аз│╛╣и╡
г░а┤ Cx1 [ Cx2 , ▒лед│е▓, ╖▓о rankA(Cx1 [ Cx2 ) = jV (Cx1 [ Cx2 )j = jE (Cx1 [ Cx2 )j.
Из (4) и (5) не▓░│дно в╗ве▒▓и ░авен▒▓во
jV Gx1;x2 j rankA(Gx1;x2 ) = jV (Cx1 [ Cx2 )j jU (x1; x2)j jR(x1; x2)j + 1: (9)
Обозна╖им ╖е░ез H г░а┤, инд│╢и░ованн╗й множе▒▓вом ░ебе░ R(x1; x2).
Я▒но, ╖▓о Gx1;x2 H . П│▒▓╝ Gx1;x2 = H n Gx1;x2 (в ░ебе░ном ▒м╗▒ле). Заме▓им, ╖▓о dGx1;x2 (u) 2 дл┐ в▒е╡ u 2 V Gx1;x2 \ V (Cx1 [ Cx2 ) и dGx1;x2 (u) 1 дл┐
в▒е╡ u 2 V Gx1;x2 \ V (Cx1 [ Cx2 ). Зна╖и▓,
X
dGx1 ;x2 (u) jEGx1;x2 j = 12
u2V G
x1 ;x2
jV Gx1;x2 \ V (Cx1 [ Cx2 )j + 21 jV Gx1;x2 \ V (Cx1 [ Cx2 ) =
(10)
= jV (Cx1 [ Cx2 )j jV Gx1 ;x2 j jU (x1; x2)j + 21 jV Gx1;x2 \ V (Cx1 [ Cx2 );
▓ак как Gx1;x2 { набо░ компонен▓ ▒в┐зно▒▓и.
Тепе░╝ пе░ейдем непо▒░ед▒▓венно к доказа▓ел╝▒▓в│ │▓ве░ждений, ▒┤о░м│ли░ованн╗╡ в ▓ео░еме.
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
48
1) Необ╡одимо▒▓╝. Из (9) ▒░аз│ ▒лед│е▓, ╖▓о rankA(Gx1;x2 ) = jV Gx1 ;x2 j. П│▒▓╝
Gx1 ;x2 6= ;. Тогда ▒▓епен╝ в▒┐кой его ве░╕ин╗ ╖е▓на и не мен╝╕е 2. Зна╖и▓,
jEGx1 ;x2 j = jV Gx1 ;x2 j + q, q 0. Из (9) и (10) имеем
1 jV G 1 2 \ V (C 1 [ C 2 )j jEG 1 2 j jV (C 1 [ C 2 )j + jV G 1 2 j + jU (x1; x2)j =
x
x ;x
x
x
x ;x
x
2 x ;x
= jR(x1; x2)j (jV Gx1;x2 j + q) jV (Cx1 [ Cx2 )j + jV Gx1 ;x2 j + jU (x1; x2)j = (11)
= jR(x1; x2)j jV (Cx1 [ Cx2 )j + jU (x1; x2)j q = rankA(Gx1;x2 ) jV Gx1 ;x2 j (q 1):
Покажем, ╖▓о V H \ V (Cx1 [ Cx2 ) = ;. Дей▒▓ви▓ел╝но, в п░о▓ивном ▒л│╖ае
V Gx1;x2 \ V (Cx1 [ Cx2 ) 6= ; и по╜▓ом│ из (11) ▒лед│е▓
1 d 12 jV Gx1;x2 \ V (Cx1 [ Cx2 )je rankA(Gx1;x2 ) jV Gx1 ;x2 j q + 1;
▓.е. 0 rankA(Gx1;x2 ) jV Gx1 ;x2 j q, ╖▓о возможно ли╕╝ п░и q = 0. Тогда
jEGx1 ;x2 j = jV Gx1;x2 j и ▓ак как ▒▓епени ве░╕ин ╜▓ого г░а┤а не мен╝╕е 2, ▓о
он ┐вл┐е▓▒┐ набо░ом ╢иклов, п░и╖ем rankA(Gx1;x2 ) = jV Gx1;x2 j = jEGx1;x2 j. В
▒ил│ │▓ве░ждени┐ 2 ╜▓и ╢икл╗ ╖е▓н╗е. Но ▓огда rankA(Gx1;x2 ) < jV Gx1;x2 j.
П░о▓иво░е╖ие.
Таким об░азом, е▒ли Gx1 ;x2 6= ;, ▓о V H \ V (Cx1 [ Cx2 ) = ;. Тогда H =
Gx1 ;x2 и A(Gx1;x2 ) = B (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)). К░оме ▓ого, ▓ак как
rankA(Gx1;x2 ) = jV Gx1 ;x2 j и V Gx1;x2 \ V (Cx1 [ Cx2 ) = ;, ▓о из (11) пол│╖аем, ╖▓о
0 1 q и, ▒ледова▓ел╝но, q = 1. Зна╖и▓,
rankA(Gx1;x2 ) = jV Gx1;x2 j = jEGx1;x2 j 1:
(12)
Так как в г░а┤е Gx1;x2 не▓ ве░╕ин не╖е▓ной ▒▓епени, ▓о из (12) ▒лед│е▓, ╖▓о в
Gx1 ;x2 имее▓▒┐ ░овно одна ве░╕ина ▒▓епени 4, о▒▓ал╝н╗е { 2. Э▓о зна╖и▓, ╖▓о
Gx1 ;x2 = H1 [ H2 [ : : : [ Ht , где H1 { па░а ╢иклов ▒ одной об╣ей ве░╕иной, H2,
H3, . . . , Ht { ╖е▓н╗е (в ▒ил│ │▓ве░ждени┐ 2) ╢икл╗, п░и╖ем Hi, i = 1; 2; : : : ; t,
попа░но непе░е▒ека╛▓▒┐. Так как A(Gx1;x2 ) пе░е▒▓ановкой ▒▓░ок и ▒▓олб╢ов
може▓ б╗▓╝ п░иведена к кле▓о╖но-диагонал╝ном│ вид│, ▓о
rankA(Gx1;x2 ) rankA(H1) +
Из (12) пол│╖аем
Xt
i=2
jEHij (t 1) =
= rankA(H1) + jR(x1; x2)j jEH1j (t 1):
jEH1j > jV H1j rankA(H1) rankA(Gx1;x2 )
jR(x1; x2)j + jEH1j + (t 1) = jEH1j + (t 1) 1;
6 ; по │▒лови╛ ▓ео░ем╗, ▓о t 6= 0.
о▓к│да t < 2. Так как R(x1; x2) = EGx1 ;x2 =
Зна╖и▓, t = 1 и, ▒ледова▓ел╝но, Gx1 ;x2 { па░а ╢иклов ▒ одной об╣ей ве░╕иной.
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
49
Не▓░│дно показа▓╝, ╖▓о ╜▓и ╢икл╗ име╛▓ одинаков│╛ ╖е▓но▒▓╝. П░едположив, ╖▓о они ╖е▓н╗, легко │беди▓╝▒┐ непо▒░ед▒▓венн╗ми в╗╖и▒лени┐ми, ╖▓о
rankA(Gx1;x2 ) < jV Gx1 ;x2 j, ╖его б╗▓╝ не може▓.
Таким об░азом, доказано, ╖▓о, дей▒▓ви▓ел╝но, Gx1;x2 либо п│▒▓, либо ┐вл┐е▓▒┐ па░ой не╖е▓н╗╡ ╢иклов ▒ одной об╣ей ве░╕иной.
До▒▓а▓о╖но▒▓╝.
rankA(x1; x2) = jR(x1; x2)j+
+rankB (V (Cx1 [ Cx2 ) n U (x1; x2); R(x1; x2)) + jE (Cx1 [ Cx2 )j:
Е▒ли Gx1;x2 = ;, ▓о jV Gx1 ;x2 j = rankA(Gx1;x2 ) = 0, и из │▓ве░ждени┐ 1 пол│╖аем
rankA(x1; x2) = jR(x1; x2)j + jE (Cx1 [ Cx2 )j + jV (Cx1 [ Cx2 )j jU (x1; x2)j =
2
= jR(x1; x2)j + jE (Cx1 [ Cx2 )j + jR(x1; x2)j 1 = n 2 n 1;
▓о е▒▓╝ ве░╕ин╗ x1 и x2 ▒межн╗ в Mk;n.
Е▒ли Gx1;x2 { па░а не╖е▓н╗╡ ╢иклов, ▓о внов╝ jV Gx1 ;x2 j = rankA(Gx1;x2 ) = 0
и, как и в╗╕е, опи░а┐▒╝ на │▓ве░ждение 1, имеем
2
rankA(x1; x2) = jR(x1; x2)j + jE (Cx1 [ Cx2 )j + jR(x1; x2)j = n 2 n 1:
2) Необ╡одимо▒▓╝. Из (9) ▒лед│е▓, ╖▓о в ╜▓ом ▒л│╖ае rankA(Gx1 ;x2 ) =
jV Gx1 ;x2 j 1, ▓.е., в ╖а▒▓но▒▓и, Gx1 ;x2 6= ;. Тогда, ▓ак же как и в 1), из ╜▓ого
можно в╗ве▒▓и, ╖▓о V H \ V (Cx1 [ Cx2 ) = ;. По▒леднее озна╖ае▓, ╖▓о H = Gx1 ;x2
и, к░оме ▓ого, EGx1;x2 = R(x1; x2) и jV Gx1;x2 j = jV (Cx1 [ Cx2 )j jU (x1; x2)j.
Ин╗ми ▒лов╗ми, jEGx1 ;x2 j = jV Gx1 ;x2 j и, ▒ледова▓ел╝но, Gx1;x2 е▒▓╝ набо░ непе░е▒ека╛╣и╡▒┐ ╖е▓н╗╡ ╢иклов H1, H2 , . . . , Ht (╖е▓но▒▓╝ ▒лед│е▓ из │▓ве░ждени┐
2). П░и ╜▓ом
rankA(Gx1;x2 ) =
Xt
i=1
rankA(Hi) Xt
i=1
(jV Hi j 1) = jV Gx1;x2 j t:
Так как x1 и x2 ▒межн╗, ▓о в ▒ил│ (3) и │▓ве░ждени┐ 1,
n2 n 1 = rankA(x1; x2) = jR(x1; x2)j + jE (C 1 [ C 2 )j+
x
x
2
+jV (Cx1 [ Cx2 )j jU (x1; x2)j jV Gx1;x2 j + rankA(Gx1 ;x2 ) 2
jR(x1; x2)j + jE (Cx1 [ Cx2 )j + jR(x1; x2)j t = n 2 n t:
О▓▒╛да закл╛╖аем, ╖▓о t = 1, ▓.е. Gx1;x2 { ╖е▓н╗й ╢икл.
Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование. 1998. В╗п. 2.
50
До▒▓а▓о╖но▒▓╝. Е▒ли Gx1 ;x2 { ╖е▓н╗й ╢икл, ▓о, как не▓░│дно │беди▓╝▒┐ непо▒░ед▒▓венно, rankA(Gx1;x2 ) = jV Gx1;x2 j 1. Таким об░азом,
rankA(x1; x2) =
= jR(x1; x2)j + jE (Cx1 [ Cx2 )j + jV (Cx1 [ Cx2 )j jU (x1; x2)j 1 =
2 n
n
= 2
1:
Тео░ема доказана.
Тео░ем╗ 2, 3 и 4 полно▒▓╝╛ опи▒╗ва╛▓ │▒лови┐ ▒межно▒▓и ве░╕ин поли╜д░а
Mk;n . След▒▓вием ▓ео░ем╗ 4 ┐вл┐е▓▒┐ ▒лед│╛╣ее до▒▓а▓о╖ное │▒ловие ▒межно▒▓и век▓о░ов ин╢иден╢ий k-┤ак▓о░ов.
Тео░ема 5. П│▒▓╝ H и H 0 { k-┤ак▓о░╗ в Kn . Е▒ли множе▒▓во ░ебе░ (EH [
EH 0)n(EH \EH 0 ) инд│╢и░│е▓ либо п░о▒▓ой ╖е▓н╗й ╢икл, либо па░│ не╖е▓н╗╡0
ве░╕ин╗ xH и xH
╢иклов ▒ одной об╣ей ве░╕иной, ▓о в многог░аннике Pk;n
▒межн╗.
Ли▓е░а▓│░а
1. Chvatal V. On certain polytopes associated with graphs // Jornal of Combinatorial
Theory (B). 1975. N 18. P.138-154.
2. Hausmann D. Adjacency on Polytopes in Combinatorial Optimization. { Oelschlager,
Gunn & Hain, Cambridge, MA, 1979.
3. Cook W., Pulleyblank W.R. Linear systems for constrained matching problems //
Math. of Operations Research. 1987. V.12. N 1. P.97-120.
4. Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Program. 1991. N 51. P.141-202.
5. С╡░ейве░ А. Тео░и┐ линейного и ╢ело╖и▒ленного п░ог░амми░овани┐. { М.: Ми░,
1991. Т.1,2.
6. Симан╖ев Р.Ю. О ░ангов╗╡ не░авен▒▓ва╡, по░ожда╛╣и╡ ┤а▒е▓╗ многог░анника
▒в┐зн╗╡ k-┤ак▓о░ов // Ди▒к░е▓н╗й анализ и и▒▒ледование опе░а╢ий. 1996. Т.3.
N 3. С.84-110.
7. Симан╖ев Р.Ю. С▓░│к▓│░а не╢ело╖и▒ленн╗╡ ве░╕ин ░елак▒а╢ии многог░анника k-┤ак▓о░ов // Ма▓ема▓и╖е▒кие ▒▓░│к▓│░╗ и модели░ование (Ом▒к). 1998.
В╗п.1. С.20-26.
Документ
Категория
Без категории
Просмотров
3
Размер файла
316 Кб
Теги
факторов, вершине, смежности, многогранники
1/--страниц
Пожаловаться на содержимое документа