)' ,ilK 5191765197 1422
B. llJ. POT K 0
3W
BBEilEHHE O p H p eweHHII psna npnxaanuux aana s . TaKIIX. K aK CIfHTe3 KOMMyTJIpylOllJ.JlX CTpyKTyP . ceren CBH311 II ;rp ymx. B0 3HIIKaeT sanaxa, KOTo paH ¢oPMyJlH pyeTcH C.l e,nYIOWI1.1 o6pa30M : Tpe6yeTCH nOCTpoHTb rparp C 3aJ1aHHblMII MHO>KecTBaMII nYTeil ,llJlH aunenenaux n ap Bep w lI H; nYTII 3 a ,lla1OTCH C TO'lHOCTblO,110 nepes acaeaas BXO;l HWII X B HIIX pe6ep . BB e;reHlle I ,llonOJlH HTeJJbH bIX (orne se naux) p e6 ep ,llJlH Ka>K;rOli napst BbUleJJeHHblX sepuma auureyno xsHYTaH aaaasa CBO,llIlTCH K aaaase nOCTpoeHIIH rp aqia C 3a.1aHHbl M MHO>KecT BOM UHKJlOB. ]lyaJl b Hoil n o OTHOruemno K Heli lIBJlHeTClI aanasa nOCTpoeHHH rpaoa C 3uaHHblM MHO>KeCTBOM pas pesoa. PeweHHIO nOCJIe,llHHX sanax, KaK B cnyxae IlCXO,ll HOro 3alla HHlI ¢YH,llaMeHTaJlbHblx UHKJlOB. TaK H ¢YH,llaMeHTa.lbHblX paspeaoa, nOCBHmeHO 6oJlbwoe '1HCJlO pa60 T [1-6). O,llHaKO npeanaraexue B HHX xeroas; He ;r OBe.1eHbI no . l ex a HH'I ecKH X npouenyp H OTCyTCTBylOT 2laHHble 0 6 HX 3qxpeKTHBHOCTH.
M = {Cl' C2 • . .. . Cm} m} . Ha3blB aeT CH kc y m ecrsyer N s M raxaa, 'I TO
Onpe ,lleJleHH e I. Cosoxyneo crs MHO>KeCTB C, '= E. i E{I, 2. .... n epeKpblBaeMo H. eCJIII
n C =I= 0
II c a rdN = k.
J
e,EN Onpeneaeune 2.
CoBOKynHOCTb M = {Cl' C2 1 '" • Cm} C, s E, i E{I, 2. .. .. m}, nonycxaer IIHTep nperaumo B sane MHO>KeCTBa u eHTp3JIbHblX paspeaon
MHO>KeCTB
rparpa,
eCJlII OHa He lI BJllIeTC H 3-nepeKp blB3 eMo H. Onpe,lleJIeH He 3. COBoKynHoc TII M {Cl' C2 • . .. . Cm} H N {DI'D 2 • . .. I D n } MHO>KeCTB C,. D j E. iE {1, 2..... m}. iE { 1,2 1 . . . l n}, 6yne M Ha3bIBaTb 3K BHBaJleHTHbIMII. eCJIIl C i JlHHeHHall KOM6HHa UH H ( OTHOCHTeJlbHO onepauna cHMMeTpH'IeCKOH paanocrn) 3J1eMeHTOB 113 N, D, - JlHHeHHaH KOM6HH a UHH 3J1e·
=
=
MeHTOB H3
s
M.
O n p eneJl ~ Hll e 4.
Coaoxyrmocrs M = {Cl> C2 • .. . Cm} MHO>KeCTB C, ~ E. i E {I . 2 , ...• m}. nonycxaer airrepnperaumo B aane MHO>KecTBa ¢YH,llaMeHTaJlbHblX paapeaos (peanaayeaa), ecnn cymeCTByeT N = {D l • D 2 • • • • • D m } . KOTopaH He lIBJlHeTCH "
'1
B ;ra HHoil paoore npenaaratorca aJirOpHTMbI CHHr esa rpaoa (HeopHeHTHpoBaHHoro H opuearnpoaau- 3 .nepeKpblBaeMoli H 3KBHBaJleHTHa M. aoro) no sanaaaosry MHO>KecTBY ¢YH,llaMeHTaJlbHbIX ]lpyrHMH CJlOBaMH , M peamrayesta, ecJJH cyuiecraypaspesoa, B OCHOB Y KOTOpblX nOJlO>KeH MeTO,ll Malie,llbl er JlHHeilHOe npeoripasouanae T OTHOCHTeJJbHO onepa(3 -5]. I1 CCJle..'lO BaHbI ¢aKTOpbI. BJlHHlOmlle na 6b1CTUHH cHMMeTpH'IecKoli pa3HOCTH raxoe, 'ITO N = poneacrsne anroprrrnon, Il pa3pa60TaHbI cpeacraa = T (M) 3KBHBaJleHTHa M Il He HBJlHeTCH 3-nepeJl.
KeCTB C, s E. nO;J.TBep>K;raIOT npaBIlJlbHOCTb n OJlO>KeHllil. HCnOJlb30i E{I. 2.... . m}. Ha3b1BaeTCH nBy6JJo'lHoe pa36HeHHe B a H H ~ np H pa3pa60TKe aJJropHTMoB . S = {So. SI} MHolKecraa E raxoe, 'ITO Ci S So 1IJ11l Ct ,=SI. Onpeneaeua e 6. f,\HO>KeCTBa M W s M . U' Eto. I}. n OCTPOEHHE HEOPHEHTHPOBAHHOrO rPAllJA cososynaocrn M = {Cl' C2 1 ... . Cm} MHO>KeCTB CiS E C 3AAA HHbiM MHOlfiE CTBOM Ha3bIBaIOT CH 3aUenJiHI01UIlMHCH no C iE/vI, eCJIIl ,llJlH
=
3a)laHa c OBo KynHocTb M = {Cl' Ct ' .•. , Cm }' m> O, MII OiK eCTB C,sE TaK HX . 'ITO E, =1= E H M uurepnpera-
n OCTa HOBKa
U c, =
3a,lla 'l H.
C,
U c,
0·
1":#
I
PYIOTClI KaK MIlO>KeCTBa peoep Il ¢YHJlaMeIlTaJlbllbiX Pa3Pe30B HeOplleHTHpOBaHHoro rparpa. Tpeoyercn nocrpoars rpadi G (M) C 33,llaHHblM MIIO>KeCTBOM M ¢YHJlaMeHT3JlbHblX paspeaoa C, 1IJ11l nosasars, 'ITO
raxoro rparpa He cylUecTByeT . Ilpexcne '1eM nepefirn K onacamno weHH lI nOCTaBJleHIIOii 3 a,lla 'l ll . anenea HII H. 3,llecb
X
II
3JIrOpHTMa pe-
pllJl onpeneneB naJlbHeHllIeM MOIUHOCTb MHO>KecTBa
6yneM 0603Ha 'laTb card
kH6E.PHETIlKA. 1986. 16 I
X.
M IC t = {CI CYl1leCTByeT
C,. ..· • CI_
1
Ci • Ci+I"-C l ... . , Cm Cd
cenaparop S = {So. S'}
TaK OH, 'I TO
w
M W={Cj EM IC j nS = 0 }, wE {O, I}. (lnp enenenu e 7. Ko~moHeH THoH xyrmocrn
M = {Cl' Ct• ... Cm}
Ha3bIBaeTCH rpeOOBaHHHM:
CBH3HOCTII
K
COBO-
MHO>KeCTB C, S E YJlOBJIeTBOpHlOmee CJIeJlYlOl1lllM I
L s E.
I) L = Ct. C, EM - KOMnOHeHTa CBH3HOCTH K; 2) eCJIIl L -KOMnOHeHTa CBH3HOCTH II L nC" =1= 0 .
C" EM.
TO L UC" Onpeneaeuue 8.
-
KOMnOHeHTa CBH3HOCTH KOMn oHeHTa CBH3HOC TII
K. K
Ha3b1.
39
lilIlf J<.. TaKOIl, tH O J<.. Q 9 Il \Ill CQlloKyn HOCTb MHOlKecTB, KOTOpbl IlIlT pnpe'TIlP '101'G$l KaK Uel~TpaJJbHble pa 3pe3bl rparpa a P M I M} - npenuxat peaJlll3ye Toporo '¥ ' . IQCTII M npu VC OBIIII M c;;, Al 0 6ocHoo aHHe·a Jlr OpIl TMa . B OCIIOBY nocTpo eHII 5I aJIropIITM3 no ~OlKeH bI yTBeplKJleIIlI51 I II 2, sor opu e 51BJl5lIOTC5I C.Te!lCTBIl5l MH reopen. JlOKa 33HHblX B l3. 5], a T8KlK e pa gpa60TaHHbie cTp 3Terll ll JlII HaMH4ec Koro ¢lop ~fII POB3 H Il 51 YC.IIOBII 5I pea JIII 33UHIl ~\HomeCTBa ljJYHll,aMeHTa bHblX paspesoa . BBIIJlY orpauas HUOro o6be.l a CTaTbll JlOKaSaTe.Tl bCTBa nplIBOJlII Ibl X y TBep >K-
H H tlI
US! II
eHHII onYlUeIlbl. YT Bep lKJl.eHll e
E. AI
C,
M = {GI' G2 ,
Flycn,
I.
AI II G EM
P(M IM)-+ \r
9
51BJI n:Ma.T.bH eTCH Kal<' HeKOTOp.l'!FO IOlUHeCll co lUeuHHlii K Ta (Bbl6llpaeT HHeM card 6). 3TOMY KpllTeplllO weHll10 4HCJIa 6Hrra 0603Ha4HM M
Gm } ·
... .
P (M~ \ M~ ld' P ( M:I Ml},
5,
C
nap a 3aUenJI5IIOlUHXC5I no •
MHO>KeCTB
• 0
• I
s M TaKII X. 'ITO M~ c:: M~, M , nM , = {C}, ,if? U' 'f: = M U {C}, w E { O, I}, r - 411CJIO B03MO>I{-
,'vI ,
HblX nap .
= /VI,
I,VI)
04eBH)lHO, eCJIH M TO P (M npHHH raer 3Ha4eHHe «II CTIl HCU npu YCJiOBHU. 'I TO /\<1 He 51BJI5IeTC5I 3-nepeKpbIBae.lOil. II «JIOlK b" - B npOTlIBHO~1 CJIY4ae. '11 + 1
YTBeplKJleHHe
.
2. ECJIH P (M }->- d' P (M J} II P (M J} 1=1
raer 3Ha4eHlIe «lI CTUHa» JlJI5I acex i E { I. 2, .., ...• m + 11. TO CHMMeTpH 4eCKa51 pa3HOCTb 3JIe~leHTOp.
npllHlI
M J ecrs ue HTpaJIbHblit paspes rparpa, peaJIH3YIOuter o M . Yc.l0BHe peaJIU3aUHIl M MOlKHO npencrasurs 1'1-
K3
1'1Jl1'1-rpaljJo , 171. n p elLolara lOTC5I CJIeJlYlOlUlIe crparernn JlIIH 3MH4ec«oro ljJop MHpOBaHH5I YCJlOBHll pe3JIU3aUIIII \HOlKeCTBa ljJYHllaMeHTa,TbHbl x I) npa pa3Jl0iKeHHu cOBOKynHOCTH
paapesoa :
M na
3BUenJl5l1Ow.HeCll
no
G
M~, wE {O, I}. IE {l , 2, ...• r}, Bb1611-
M,
paeTC5I G EM npn KOTOpOM MIG HMeeT MII HH' MaJlbHOe '1I1CJiO , ulIHapHblx cenaparopon;
Ml Bbl611palOTcll
2) M ~ 11 xapasr epacraxa
vr
=card
M~+
B
nopsnxe
card
KOTOpylO 6yneM Ha3bIBaTb HeCOM; 3} sapaanr u aauennsnouiaxc s n o
Mi,
B03paCTaHIIlI
U Mi , G
wE { O,
I} ,
cOBoKynHOCTeH
wE IO . I } , j E{I ,2, .. . ,r}. Bbl611pa lo Tcli B nopsn Ke aospacranns XapaKTepUCTHKII d / v' - v~ KOTa-
=I
I,
PYIO 6yJleM aasasars ne¢eKTOM; 4) coxpauieuae 411CJla aapnanroa nap 3aUenJI U1IIXCli coaoxynaocrea na B0 3MOlKHO c on ee pa lI IDsranax . HHHX
Crpareraa 4) OCHOBaHa touiero YTBeplKneHlIlI . 40
'au.
aa cnpaBeMIIBOCTH
P
B.
M
= 2j , + W, + I,
r-ae
I, -:
caeny""
HO~1{o 1. .. , ,''1
pa3JiOiKeHIlli YPOBHlI I , Ji o~eIlHlI V~0Bfffl I, " _ 41lCJlO aJIbTepHaTllDHblX n ap pa3J1 of! napbl' W i W , _ 1l0Mep KOMnOHeHTbl aJlbTepilaTIIBH
napu
1= 1
rne (M ~ , M ~) -
a
n oc p cMOKYlli ,; 7':" ' ;-. ; 5 1" " ' L .... J10 el1:;b Jiy4eHH YIO B pe3YJIbTaTe1: P33 .>K
M . Tor na
x
6'
6 m5l' Q - MilOTaKlK e cJlenyIOlllll e 0 0 3Ila4ef B~ 5leMo e unB lKeCTBO ljJYH)l aMeHTaJlb HbIX pa 3pe3 0 , npo p I}.
E { O.
Bseneu
Q-
peaJlll 3y eMocT b; MHOlKeCTBO cjJY HJlaMeUTaJIbHb l HHTepn peTllpyeMblX KaK u eilTp aJl b Hble paspeas rpaoa : L _ ypoBeHb pa3JIOlKeHllll; a - 4 HCJlO 3 J1bTE'PHaTHBHblX nap ; Q (L) = (Q1 (L) , Q 2 (L) , ." ,Q 20 - 1 (L ).
paspesoa, Q (L )) -
cnHCOK KO mOHeHT aJlbTep ilaT HBIlhlX n ap 20 pa3JIO:-KeHH5l ypOBHlI L; S = (5\, 52' .. , , SL ) - BeK TOp COCTOllHllii. YKa3blBaIOlllHii Bhl6paHilble KOMnOHeHTbl 113 cmfCKOB KOMnOHeHT aJIbTepHaTHBHblX nap P33 JUl lJHbIX ypoBHeii: n =(Q(I),Q(2), .. • • Q(L); B (car d Q ( I ) . card Q(2), . .. , ca rd Q (L); C - sauenasnouiee \B OlKeCTBO; R - rexyiuas COBOKynHocTb MHOlKecTB, unr epnpempyesrax KaK COBoKynHocTIl ueurpansnsix paspeaoe
=
rparpa, 1\1;
AJirOp HTM. I. HHHUHaJlH3aUH5l: Q +- A; B +- A; S -- A; R -+-
L +- 0; Il
Q=
K n . 12. MHOlKeCTB a MHHIIMaJIbHblM 3HalJeHH e I card C . 2.
ECJlIl
Q,
Q -
nepearn
3. Buoop s auenn snouiero
C EQ
4.
n
HeHT
7.
S, +-S L
+ 1;
Q-+-Q
(L) ; 'L
0;
(2).
QC
KOMno-
n. Q (L);
(-+-Q . (L). nepeime L
2. L - 1.
K BbInOJIHeHHlO n .
8. L +9. Fcnn
10.
SL 4 eTHO, nepeiiTH K n ,
SL -.. SL
+ I.
I\.
II. Koppexuns R . H n. 12. R +- R U { Q}. 13. ECJlIl L = 0, ne peilTH K n . 16. 14. EC JlH SL He4eTHO, n epeiiTH K n. 7. KII6E P H ETlI "
'v \, 1986. ~ •
15. L -- L -
I. nepeirm K n. 13. OOCTpOCllHC . 1H0 >l' CCTBa UCIITpa,1b Hbl.· paape30B N' pe3Y,1bTllpY,lOllI,CrO rparpa : R aanaer JIH Hei m o e npeo6pa30BaHllc T conoxynaocru MHO>t<ecTB M QTHOCIlTf.1bHO onepauuu clI .l.leTpll 'lecKoil pa3HocTII . 16.
T.
e. N'
=
T' (M) .
17.
KOHeu. Pac c 10Tpll I aanaxy ¢oP IIIpoB aHIISI ynopnnosen noro cnllcKa KOMnOHeHT ansrepuaruauux nap Q (L) . 31'a 3:ua'l a rpop lyJIIl pyCTC SI c.1CJlYlOllI,II I 06pa30.1. {C l • C2 • . .. . Cm} 1110 3aJ13Ha COBOK nHOCTb lvl >t<ecTB C, s E. KOTOPblC S1BJ1S1IOTCSI ueaaeucuuu III OTIIOCII Te.1bHO onepa uuu CII M terpusecxon pa3110CTIL
=
1II0 >t<ec TB (\.1 ~ M . Tpesanaaaoro aauennsnoutero MHO>t<ecTBa C E. \1 .\1 nocr poirrs BCC aonycruuue ansrepuar aa a pa 3.10>t<elllISi I ua napu (M~. IHI) 3 aUCnJl SllOUl II Xe Si no C no MHO>t<ecTB C BblJleJJCHll bl MII MHo>t<eCTBaMII .w~. wE {O. I) . II yncpanosnrs aJlbTepHaTII BHblC na-
q,YIIAaMCHTaJlLHLlX paapeaoa
phi B nOpSlll.KC B03paCTaHH SI ll.C¢eKTa. a IWMnOHCHTbl napu - B nOpSlJlKC B0 3p aCTaHIl SI aeca KOMnOHCHTbl. A.lbTep"aTIIBllaSi nap a S1BJl SlCTCSI nenon ycruvoa , CeJl H
wE {O. I}.
BbL1 en ell 3 6yeTCSI
cOBOKy m locTb
1l~S1
.
XQTlI 6b1
onna
KOMn OHCHTa
3-nepeKPbIB3e~lOc
Mr.
w E{O. I}.
COJlCp>t
Mw
• MHO>t<ecTBO PernCHIlC nOCTaBJIC HHOU aana sa CBSl3a HO e noneKO)! 611HapHblx cenaparopo s . Ilpn n o eTpO CHHII IlX anropHTMa BocnOJlb3YCMell eJlCll.YIOUlHM yTBCp>tt<ecTBO MaKCllMaJlbHbIX KOMnOHeHT eB1l3HOCTli eOBO-
=
K)l1HOCT1l M IC MHO>KecTB ;Wy6.7JO'lHoe pa36HCHHC K .
l
C," ,C =t= 0 H {K0. K } Torna {Ko. Kl} coorsercr-
{ i}
[1,2.J,~.5}
{ ff}
{i,2,J,-:,5}
Puc. 2.
ayer
rpaq, C 33;1.31111L1M MHOlKCCTOOM
611llapHbli\ eenapaTOp
Ai HeopllCIITlI pooallllLlx
UK,•
{SO. 5 1}. rne SW=
K,EK'" n p OHJlJlIOeTp Hp y CM paoory anroparxa na npHMcp e . I. nYCTL COBo Ky m l oCTL M = {I . 2. 3. 4. 5) MIIOlKeCTB·
n pUMOp
{c.
f. e. h. i} . 4 = (d, f. h.
6YJl.eM 9J1CMellTbi MHO)Kecrna
M. SlBJlSlJOll(lIeCSl ra x ace
I = {a. i). 5 =
f. gJ. 2 = l b. f. g, h}. :; =
»cecrna
if
Ie, f. i} HIlTepnpetllpyetCSl KaK MHOlKeCTBO q,yH;J.a ICHram-nux pa apeaos rpaq,a . n OCTpOHM MHOlKCCTOO N' uenr p aasIIb1X paapeson rparpa , npcACTaB.1l'IJOll(erO 3aAaHHOC MIIOlKCCTBl> Ai q,YHJl.aMeHTaJlbIlLlx paap esoa . B l eCTO asuoro o n ucauas 101110 '
M.
9J1e\leHTaMH MHOlKeCTBa nOMeqaTb csepxy C1lMBOJlOM er o x x a•• Ilpouecc pa60TbI aJlr OplITMa HJlJlIOCTpllpyetCSl Ta6.1. 1. 3Aecb I _ HOMep urara npouecca , Q - aaaa H311 pyeMaSl co s o x y n aoct s MHOlKeCTB . C - sane namomee MHOJKeCTBO. QIC - peayuapoaan aas OTIIOCHTCJlbHO C co so xynuocrs Q IHOlKeCTO. K (QIC) Ko>mOH eHTbl CBSl3HOCTH QIC. S (Q) - 6HHapHble cenaparopu AJlSl Q. A (Q. C) - an sr ep aaraa uu e napu 3auenJl SlJOll(IIXCSl no C cOBoKy nHoCTell MHOlKeCTB .
P (QW) -
3HaqeHHSl npeaa x ara pea -
JlII3ye MOCTH cOBoKynHocT II ~UI MHOlKCCTB. R - <\JopMllpyeMoe JI ll , HellH oc npe06paaoBaHlle T' conoxynaocru M MIIO>KeCTll . Ha pHC. 1 npna eaen q,parMeHT nocrpoeusoro H .HJIH · r p a<jJa . on acuaaiouiero YCJlOBIISl peaJlH3aUHH coBoKynHoCTII AI 1I10JKCCTll. M HolKeCTBo uearpaasnux pa apeaos N' = T' {M) lllcKo~loro rpaq,a HMeeT OIlJl. N' = !N .. N•• N s- N•• N•• N. }. Nt I = (a.
=
f.I1). N. = 5 = (e. f. i). N. = 1 \:B 2 = {a , b. Ii). N. = 4 B \:B 5= {d. e. h}. N, = 3 \:t) 4 = {c. d. g }. N. =2 81 3 = {b. c. i) .
{iZ}
{;. n
H a pIIC. 2 11306palKclI lIallJl.CHIILlll r p a.p. r paq,oM K3 ,3 Il or pa r uua-c-Kyparoacxoro (8] .
(Z,J,4)}
n OCTP OEHH E HEOPHEHTHPOBAHHOfO C 3 A,llAHHbIM MHOlKECTBOM CIlYH,llAMEHTA.I\bHblX UHK.I\OB V1 3BCCTII 0
[81.
'ITO MII O>KecTBO UAKJlOB
A
fPAOlA
paapeaos
rp arjJa J1.yaJlbllbl no oruouremuo npyr K npyry . CneJlOBaTeJJbIlO. JlJlH peuienns aanaxa nOCTpOCHIIH rparpa e 3 alla HHbi M MIlO>KCCTBOM ¢YllllaMCIlT3JIbllb1X UAKJlOB
(i,J) }
{j, ~}
x orop u n SlD.1Sl er c~
(1,2,J.-:,5)
nepetrr n K JlY3JIbllOM Y MHO>KeCTBy A BOCnoassoaarsca aJlrOpHTMOM nocrpoeana rparpa C aa -
llOCTaTOtllIO
{z , j}
JlallllbiM
MII OlKecTBOM
Flpoanmocrpup yea Pue. 1. <1>parMcHT H .HJIH .rpa<jJ3. on llcJ,/03JOwcro pea.'H3aUHlI
MHOlKeCToa
Ta.1LHblX paapeaon
AI
Heop lIellTHpooaHHJ,/x
YCJI ooHe <jJYlIAaMcH'
¢Y Hlla MellTa Jl b llhl X paap 3JIrOpHTM nocrpoeaas
>Kcc:rBa uenrpans nu x paapeaos r parpa C MIIO>KCCTBOM ¢ YHlla Me HTaJl b Hhl X lI,AKJlOB
na
~~~:
3aJl.aHH hiM npAMe p e .
r
II
KeQIO
c
(2' .3' . 4' ,5') • (2', 3', 4' , 5' ) (b , h) .
(1, 2, 3 , 4, 5)
:1'
I·,
'it
(b .
e, a, e,
II. /)
3' - (e. n, I).
2
(1. 2, 3, 4, 5)
3
(I.
~.
4.
I
"
I,
(2 , 'l , 4 , !'»
f,
1~
(2,
a,
4t
4' 5' (I', I'
1
j
IJ'
'"
( I)
o
(5)
u
W _O\u'_1
O·
~~ ' 2 , 3 . 4 ,
T
«1))
(1. 2 , 3, 4,
T
«1). (5))
T
((1 ) , (5), / 1.2 ))
(d, h . I) , (I'. I )
2',3', 4). ~\;. 2' , 3' .
2'
(a. Il) , (b. /.I, 'I).
3'
(c ,
(b,
e.
d . R . h)
5)
R, II),
4' (d, h) (1'1 3' , 4' • G' ), I' (u). 3 ' (e. l). 4' (d , I),
:!
\ ,.,~
A(Q, Cl
(QJ
VIr
5' (e , I) (2'. 3' . 5') , ~: (b . 1/) , ..
(c. R)
,J
/ _)
(2 ' 4'), 2' (b) . 4' (d )
( 1' 1
(c . d, a. /)
(3'. 4 ' , Ii ' )
(a, e ,
(2' . 3 ',
(b , e . 1/)
(5',
(b,
(2' )
(b)
(4')
(b . ,11
c.
a,
-.
r ,
.)
(a)
(1, 2)
(2 , 3 . I. 5)
'"
(2)
(t')
(4 .5)
( I , 2 , 3. 4 . 5) /2. 3, 4)
c-
(4)
(2,
(d)
(3. ,I ) (2, :3)
«(1), (5),
1,2). (4,5») g)
(3)
,
4 . 5)
(2, :I , 41
/'I
F
'1,
a ocru
ec.m
na KOTOpoli sanaao cnenvioinee oruoureaue:
'1' • (din Clj)U (Ci n C~ ) * 0 .
i=/=i,
TO
Cj,CjE
E ,\I ", .. E {a, I};
ecnn •
/
(d n~)U (C: ndJ')...L ..,- 0.
" I. 1=/=
TO
/
6. Ecnn
R={A·'j= I\12 ,
.. . .
1\1? UM)
\
b .;
2
M"
, ..... E {O, I};
ec.m (. 'I? n \i ~ ) u (\i ) n Af}) =/= 0 . i =/= 1 ii ER, i\1 j ER - "' , wE {O, I}. Bae.'leJ . HO,;" e... --rna
UCi
i.
TO
onepaumo CMeHbl opueurauun 3JIe~leIlTOB CL CJIe;J.l.IOUU~1 06paJO M: n YCTb Cj= c? U
• TOrAa
/
7.
JIIIHelI Hoe
/
/
/
II
npeocpaaoeaune T'.
{M;. ,\1;...., M ~+t} . rne Nt; = M i1; = l\1 j, ecJIlI Md :. R wE {O, I}. j•
rD
•
,2.1l1 peurena s s anas a nocrpoean s MIlOlKeCTBa nearpa lbHbIX pas pes os opHeHTllpoBalllloro r parpa C sa;taHHbl 1Il0lK ecTBOM QlYHJlaM eHTaJIbHblX paspeaoa ;J.OCTaTO'lHO MO.llH Qlll u ll p o Ba Tb anr opnrx .nJIli neopneurnposaaaoro r parpa CJIe.nYIOIUIIM o 6 p a3 0 M: 1) BBeeTH llOnOJIHII TeJI b HY IO npoaepxy peanasyeMOCTH cO Bo Kyn HocTH MHOlKecTB opHeHTHpoBallHblM
rpaoo a; 2) pea.1H30BaTb rrocrpoenae JIHHei'IHOrO npeoripaso-
T';
Ba HH lI
3)
o;mQlH u HpoBa Tb nocTpoeHlle u eHTPaJIbHblX pas-
p e30B Pe3Y.Q bTH PYlOl.l.I.e ra
Fln. 1)
H
2)
rparpa.
MOryT 6blTb pea JIH30BaHbl O.nHHM Il TeM
lKe 3.1rOpHT 10M, peUJalOlUllM CJIe.nYlOmylO 33.nalJY· 3a,naHa cOBOKy n HOCTb M = {CI' C2 • .. , , Cm } MHOlKecrB
C, = C'7 UC:, C'7n C)=0 . C1£ £ . i E{1.2, ... . m}·
113HTH JlBy6J10lJlloe pasoaeuae {MO . M I} cOBOKyn HocTII M (Mil nOK3 3aTb . 'ITO raxoro pa 36l1e·
Tpeoyerca
HIIH He CYlUecTBY eT ) . 113 KOTOpOM
3aJIaHO
cnenyiouiee
oruourenne;
ecnn
(d nC}) u(C) nc,' ):f= 0 .
wE{o. l }; ecaa (c';' n L1) U (C) n c: ) =/= 0. CJEM '- • wl'fO. I}. 3T3
33;I 3 '13
MOlKeT
tlblTb
TO TO
C" C,E M C, E M
W
\ /
\
/
/
/
~\
\
\
0 .;
J
\
Q 2
8
Puc. 4.
f p a cj> b1 COBMeCT II MOCTII II lIeCOBM ecTlIM OCTII :lJI e M eIlT OB Mll OlK e CTB {2, 3, 4}. {2. 3. 4. 5}. {I. 3. 5) II {I. 2. 4}
TeJIbHOH
COUBeTlIOCTII
II
06H3 aTeJI b llOH pa3110UBeT-
IIOCTJI. DpOIlJlJlIOCTpHpyeM anroparx rnposanaoro rp a¢a aa npxsiepe.
nocrpoeans opnea -
t. g,
_ n~H~tep 3. ntC~ ~~ ~ {I. 2. 3. 4. 5}. 1 = {a. ii, T, 1. ~, ~, pI , 2 = {b.) . i.!.- 1; n }. 3 = {c. i. 4 = {d. Ii: i. m. pI , 5 = I e, i, k, l, p} nar epnperup yer cs K aK MllOlKeCTBO
g. m. n}.
cj>Y HilaM eIl Ta Jl~H bll<
paapesos op uearupoaa a aoro rp atpa. n OCTpOIl M N uesrpaasaux paapeaos r parpa, npencraan.noutero aanaanoe MHOlK eCTBO M cj>YH ilaM e HTa Jl b Hbll' paspeaoa. Il pouecc pa60TbI anropnrsra HJlJllOCTpll p y eTc lI Ta6J1 . 2. Ha p HC. 4 npeacraaaeau rpacj>b1 COBMeCTIlMOCTII II lIecOBMecTlIMOCTII 3J1eMe HTOB IHOlKeCTB {2. 3.4). {2. 3, 4. 5}. {I . 3. 5}, {I. 2. 4} II Ill'
MII OlKec TBO
611HapHall KJlaCcllcj>IIKaUlIll . 'uJllI Hal'OlKileHlllI JlIIHeilHoro npeoopaaosan ua T ' . npeoepaa yiouiero 1\1 B MHOlKeCTB O N'. mrrepnpenrpyeaoe KaK MII OlK ecrno uesrpaasaux paspeaos opneumpoeannoro rpatpa, KJlaC cllcj>HlUl ' pyex II npeoopa ayex ero B COOTBeTCTBlII1 C 3TOil KJlaCcHcj>IIKaUlle A. Ha pIIC . 5 npasenen rpacj> COBMecT II MOCTII II HeCOBMecTII' MOCTII 3J1eMeHTOB lIa R. J1I1HeHHoe npeoepasoaaxue T' npeacras-
R
{3}. (:t}. {5}. Ii;" 3,5) , (I, 2,1 l) . L~1) ImeeT Bllil N = {N!, N•• N•• ~.}. = _2 = {b. f. j , /. n}, N. = 3 = g. Ii. m, n}, "!...3 4 = {d.:.. h.)•.!.n:.., p}, N, =:.5 = {e. i. I, pl. N. = = 1$ 3 £15 = {a, c. e, f. It}. N. = 1 EB 2EB4= (ii, b. d. g, i}. H a puc, 6 npuaeneu r pacj>, COOTBeTC1BYlOlUIIH N'.
MHOlKecTBOM R*={{2}. HCKOMoe MII OlK eCTBO N' ~ T'
nsercs
!ls'.!'"
=:.
!iI
t;
{c.
, W •
IIHTepnpeTHpOB311a KaK
paCKp3CK3 BepwHII rparpa, conOCT3BJIeHllblX 3JIeMell' TaM MHOlK ecTB3 M. C HCnOJlb30B3HlleM nBYX xpacox . Pe6p a rp3 -f.;) r B V X nWOB 33.ll31OT OTHoweHlle 06H33l( lI fi E P H ET ll KA, IYllti, l& 1
1
0
J
~IHOlKecTBO QlYHnaMeHTaJIb HblX opaenTIlpoBaH HbIX paspeaoa M B MHOlKecTBO N' ueurpa nsHblX paspesoa OplleHTIlpOBaHHOrO rparpa, onucueaerc s
eczm .·1i E R"'.
f
\
npeoopasyiotnee
O;+;ecTIlO~1 RO=
5
~\
s
.4
a
o
Cj = ct UcJ . C? = C), cJ = C?.
~'T1leplKJleH He
\
o
J\1m+ l} -
eOBOK)l1 HOCTb peanrayea ux ~IHOlKecTB 1\:11' TO cvmecrsy er .nBy6.10'l Hoe pascnenue {RO. R' } MilO : lK ecrea R, aa KOTOPO~' 3aAaIlO CJIeAYlOl.l.I.ee oruourenue: •0 • I • ec.qll (A1; n Mj) U(M) ni\1~)=/= 0. i=/=i . TO
AlJ E
\
/
Cj E 1- ", :...' E{O. \). TaeplK eHHe
~\
/
C.j EM' lD .
• 1
J
2
J
nOCTPOEH HE OPHEHTHPOBA H HOrO rPAlPA C 3A~AHHbIM MHO mECTBOM lPYH ~AMEHT AAbHblX ijHKAO B JlJlH peurenu s 3an3lJII nocr p o enn a opll eHTHpoB aHHOro
rparpa C 3a n 3 Hll bl M MIIOlKecTBOM QlYlI.lla Me HTa ll b HblX UIIKJlOB .llOCTaTO'lIlO nOCTpoHTb .llyanbllo e n o OTHolUe -
43
/
/
/
/ /
/
Je{--
---{
/
---
/
/
----Ols] Puc. 5.
HoCOnMCCTllIoIOCTIl
neMCHTon
MlfOIK
muo
1l0>RCcmy ~IlKIIOB 1II0iKeCTBO aocnonssonarscn anropnruoa
K
3aT(~M
paspeaoa
Ii
nOCTpOClIllH
rpadia no mOiKCCTIlY paapesos. PaCCMOTpllM npnxep nocrpoeuas nyansnon OBOKynHOCTIl MlIOiKCCTIl C 0plleliTJIpOB31111blMII lie tenT3MIi.
npHMep 4. rlYC1b M "'" (I, 2. 3. 4, 5, 6, 7, ,9,10), I ~ lao fl. 2 fa, c. ), 3 - (a, d, h), 4 =0 [c, e, f), 5 = (b,d. II =0 " 11), 7 = {a. b, ,f), 8 '" {a, c, d, m}, 9"'" (a, o, c, n), 10 ~ ( J d, e. pl. llyaJlbllOC no OTllOW lIHIO K M MHOlKCcrDO M "
=
b,
I
e.
1(' " " II
a A(Q,
5(Ql
"
II
(I, 2. 3,
2
·1
Q,"
o
4 . 5)
KeQ,co
(1',3',4', 5'), )' _(a. g . h , "
f , 3" ')
~,
I
p) , (c. g, Il. m) , (d. h , m , p), Tn ,
3' 4' 5' 2
2, 3.
(I.
3
n-. I'
4 . 5)
2' I'
3
(I, 2. 3 ,
2' 3' II , 2. 3.
5
4,
5\
( I' , 2' . 4',
(I' , 2' , 3' ,
5')
44
T
«(2» )
(a, b, d,
e, t , h , I , it i ,
«(2) , (3))
OJ
(3)
(I. 2 . 3 , 4. 5)
T
(a, b , c, P,
I , R,
Ql
(4)
(I. 2 . 3 , 4, 51
0'
~ I, ,'2. 3 . 4, 5 )
7
((2), (31,
(4»
n)
I,.
{I' , 2' , 3' . 4' 1
(a , b , c, d , /, R.
/1, I, n)
(2'. 4' )
(b. I).
II). (d , I) , (e, 11)
[;
«- I
4, 5)
I. It , / ,
/, nJ '
n), 3' -(e . R. m , n) 4' - (d . h, I, m) ~2" 3', 4'. 5' ).
'
I
p)
I . p).
(b, ,I. n), (c. fl. n), 6' (e . I, k, /) (I', 2', 3' , 4'), I' (a, t , fl, h . m , n) ,
3' 4' 6'
(I, 2, 3 ,
u-O
p)
2' -(b, l , l,
(1, ~ , ~ .
(2)
0'
I.
(a, h . I , l , pl, 5'1 (b , l , I, I) ,
ta, n,
C?'
p(Q U1
p)
2' , 4'. 5')
6' (e , I, l , p) (I', 2', 3', El), I' (a . t . fl . t,
4,6)
4. 5,
r-, " 11 .
(a. c , a, r, g, h, 11 , m .
Q
o
ttl, n.. I)
c, d , e, " k) (b.
(6 1
m.
(c ,
(3'. 6' )
Q
(c ,
e. 11) (1, 3 , 5) (1. 2. 4)
e
(11
(1, 2 , 3 , 4 , 5)
( 2), (3), (4) , (5»
7
T
"/
I-
«2 ) , (3), (4 ) , (5),
(I.
,5),
(1.
2 . 4» )
Kll h EI IlI ETIlKA . 1!lN8, ... I
PE3y ,\bTATbI MAWIfHHOro 3KCnEPHMEHTA
OnllC8HHble 3JIroPIlTMbI nOCTpOeHIIH ueopuearnpoaauUbi: II opuearnpoaanaux rpados C saaauuus: MHOlKeCTBO.I <jlyH1l3.leHTa..lbHblX paapeson IlJIII u,IIKJ10n 6b1J1I1 38npore a I. IIlpOBaHbI na asuxe J151nAC-M [9]. MaWIIHH blll sxcnepuaear C pa3pa60TaHHblMII nporpaauasut T .6 -' " u a 3
n.p.aw
rp
:-o1 Z,. 'U I
I
card E
card .\f
9 9 9 9 9 9 9 9 9 9 13 19
20 20 20
20 .0 21
--
]0
, T•
• " u
r
16
.-
32
I
I
CE4\1Il U
'>
CE4HHU2
21 390 62 8 164 47 78 68 17 12 680 1800
2.0 2.5 2 ,5 3 ,0 2 ,5 3 ,5 4 ,0 2. 5 2 ,5 2 .0 12 ,9 19 ,3
caeaoaauna .
4
J'l&M eT p bl 3&;10Q
cord E
20
fir e""'1 PCUJ('IlIUI (C)
rpaMMbI nOCTpoeHlili opHeHTHpOBaHlIoro r p arpa He3Ha'iIlTeJJbHO OTJlII'IaIOTCli OT xapaKTcpHCTIiK 1.'1.' aaanora llJlH cnyxaa neoplleHTllpOBaHHoro rpa¢a . Ananns peJy.lJbTaTOa MaWHHlIoro 3KcnepHMeHTa C nporpaasiaaa CE4Y1HU II CE4V1HU2 nOKa3blBaer , 'ITO nocnennsa llBJllleTCH 60Jlee 3qxpeKTlIBHOit. Ha OTJleJJbHblX npuaepax 6b1CTpOlleli cTBlle nporpaMMbI CELJl1HU2 nuuie 6b1CTpOlleiICTBIIlI nporpaMMbl CE41-!I-1U n HecKOJlbKO necHTKOB paa , Hccaenoaanue nporpaMMbI CE4V1HU2 nOKa3aJlII, 'ITO llJlll Rconoxynaoctea npeas peaJlll 3aU,llll onucsmaercn <jlyHKu,Heit, 6Jlll3KOli K JIIlHeitlloit , a 3aBIlcmlOCTII OT card M . .llJlll N R-coaoKynHocTcil BpeMH peanuaaunn onucuBaeTClI cjJYHKu,lIeit, npHHallJlelKaw.eli xnaccy sxcnolIeHT, OllHaKO llJlll aanas, xoropsre BCTpe'laIOTCli ua npaKTIIKe, npeMll peurenaa OKa3bIBaeTCH npuexJleMbIM. ABTop ornaer ce6e OT'IeT a TOM , 'ITO Ou,eIlK II 3cjJQleKTHBHOCTIi anropnraoa na OCHOaI.' pesyn sraroa Maumaaoro ascnepnnenra He 3aMell ll 1OT aHaJlIITH'IecKIiX Ou,eIIOK. Haxoxcneaae TaKHX ouesox np encrasJlHeT coooit caMOCTOllTeJJbHYIO rexy aaysaoro Ii C-
I
card ..\1
9 11 13 15 17
O U,CIl K3
06'bCM Bbl 60p1
R-C OBO ti:yn 1I0 CTb
58 49 13 9 16
cpen uero
SpCM e HH p e W C.HIUI
(c)
I
N R -C080KynHOCTb
R - COBOK } 'f1HOCTb
6 15 16 32 16
2 .5 3,5 4 ,1 5,0 6.0
nJlOBO.1H.'ICH aa U BM EC - (020. I-!cT04HHKOM IlCXOllaHHblX .'1.151 ncnsrryea u x np orp aaxt CJlYlKlIJI r eHii neparop nces.n.DC.1Y'l aHHblX rparpoa C 3allaHHblM '1IlC.10M aepWHH H pe6e p. n o rparpy HaXOJUIJlIlCb <jlyIlJl aeHT
I
0 1leUK.1 ,llltCnCpCH"
N R -C080Kv n nc en,
R ·C oBOK ) 'n n OCTb
4 .8 10,3 26 .0 43 .4 100.5
0 ,17 0 ,80 0 .5 4 0, 47 0.62
I
N R -co 8o Ky ml o cTb
0 ,5 80 692 2 588 27746
c n l1COK. Jl I1TEP AT YPbl . . 1. Au,s 1 a n d e r L. . T r e n t H M t~e rea llza h on of linear graph given its algebra: . Soc. Amer.- 1961.- 33, N 9 _ ~c tf~catIon II Acousl. 2. JI e r p e H JI. Peureune np06~e~lbI 1192. 6b1TOQHblMIi 6YJleBbiMII cxeMa MH 6 peaJlH3yeMOCTII ueuaN. 5.- C. 60-101. epuer. c6.- 1962 . 3. ill aye d a W. Necessar d . . realizability of cut-sel Ym af . s/~Iclent con ditions for Theory . - 1960.- 7, N I.-~. r~9':.8 1 IR E Tr ans. Circui t 4. ill aye d. W. Realizability of fund . cos of oriented graphs. IE E E Trans C~me~ttal cu t-sel matri10, N 1.- P . 133-134 . )fCU I Theory.- 1963.5. ill aye d a \\' Pro ~rt' f which Iransror~ cut~se\es m~trit:e ~orsin.gu~ar matrices ces II Ibld . - P . 128-130 es no inc Iden ce matri6. T utI e W T F . , 1964.- 16. N p.ml~~l~~ to graphs II Can . J. iIIath.7. H II JI be 0 II H HCK cern . acxa peweIlIlA.-·" I.: "I;'p , I~~3~ ;~ITe.nJleKT: MeTo.l\b1 no8. X a pap II cl>. Teopns rpa <jJoB' - ~ c. 9. 3 a K p e B c K II A A 11 T ' ill.. MIlP, 1973._ 300 nporpa mlHpooaHIIH .ri5lnAC-M p o 0 B H . P. CIICTe~~~ HII Ka , 1978.- 239 c. .III1CK : HaYKa II rex-
il .,11 v
1:-
,,'i
llocmynu.ta 05.07.83
1936, ... 1
45
