Luận án Cấu trúc của V - Thứ tự và định lý kiểu kruskal- katona

ChttO'ng2. Djnh if ki~u KK 16 Chudng 2. , ;!, DINH LY KIEV KK. Trongchl1a'ngnaychungtoisechungminhr~ngt~ph,pB cacvecta' Boolla m(>tK-poset,tuc 130chungminhdinhly ki~uKK trenB. Cac k~tquacuachungtoi trongchl1a'ngnaydadl1'Ccongb6trong[5],[6] va[7]. 2.1 Ky hi~u. GQi IN 130t~ph,pcacs6nguyenkhongam. V6i n E IN thl ky hi~u V (n) d~chi t~ph,pcacvecta'a =ala2. . .am ai E IN: V(n) ={ala2" .an: ai E IN} vdi V(O) ={0}. Tl1a'ngtlJ, B(n) 130t~ph,pcacvecta'Bool n chi~u: B(n) ={ala2...an: ai=0 hayai =1}v6iB(O)={0}. TacoB(n)C V(n). Cac vecta'sedl1'Cth~hi~nb~ngchi!co net d~mva chi!thl1<Jngse dl1'Cdungd~chi cacthanhph~ncuano, ching h~nnhl1: a - a* - a* * *- ala2' . .an, - la2'" an, Choa =ala2. . .an E V(n), n >1. . Va 130s6 nguyen xac dinh nhl1 sail { 1 n~ual <... <an Va = n n~u an-I> an h n~uah-l >ahvaah< .. . <an Chl1dng2. Djnh if ki~uKK 17 . 6iala vecta'trongV(n -1) codU'Q'ctu a b~ngcachb6thanhphan thui cuaa,tucla { 61a = a2'" an, 6na = a1'" an-I, 6ia = a1'" ai-1 ai+1. . . an, 1<i <n. . a*, wa, j.La,va Aa dU'Q'Cdinh nghianhU'sail a* - 6hav6ih =Va a1+a2 +. . . +an max{ai : 1 <i <n} s6ca,ci th6aai =j.La mill{ai : 1 <i <n}. wa - j.La = va - Aa - Ta gQiwa la trQngIU'Q'ngcuaa. . Vecta'zerocua V (n) la vecta'co trQngIU'Q'ngb~ng0 va dU'Q'Cky hi~uZn (v6i Zo=0). . Vecta'cotrQngIU'Q'ngn trongB(n) dU'Q'cvi~tla gn' V~ygn=1. . .1 (v6i go=0)vagn la vecta'cotrQngIU'Q'ng16nnha:tcua B (n). . N~ua E B(n) vaa =I gnthl a* = 6ka= 6hav6ih = Va va k = max{i:ai = O}lienta coth~giaS11Va =k khi tlnha*, a =I gn- . ad, dav6id E IN IanIU'qtla cacvecta'saildaycuaV(n+1) ad =a1. . .and, da = da1. . .an- Ngoaifa, v6iA c V(n) thltavi~t A*={a*:aEA}. Ai:d= {a1a2. . .anE A : ai = d}. Ad={ad:a E A}c V(n+1). dA={da:a E A}c V(n+1). V~yv6iA C B(n), n >2thlA coth~vi~t A =MO+N1 v6i M, N c B(n - 1). Chttdng2. Djnh 1f ki~uKK 18 . N~ua =al . . .apva b =b1... bqthl ab =al'" apb1. . .bq (v~y ab =a n~uq=0vaab=b n~up =0). . N~uA c V(p),B c V(q)thl AB ={ab:a E A,bE B} c V(p+g). . V6ia =al" .anvab =b1...bnla haivectO'khacnhaucuaV(n) ta d~t a(a,b) =min{i : ai =IbJ. NhU'ta da bi~ttrong ChU'O'ng1,V =U v(n) la mQtposetco hc;wg n2:0 v6imucthun la V(n), bongcuaa E V(n) la L1a={Jja: 1<j <n} vabongcuaA C V(n) la L1A=U L1a.TU'O'ngtlJ choB =U B(n). aEA n2:0 2.2 Thti t1!BG la khongthich hQ'p NhU'danoidphantren,nam1992Bezrukov aGronauc6ngb6bai baa"A Kruskal-Katonatypetheorem"[12],trongdohQchor~ngdtnh 11ki~uKK choposetcacvectO'nguyenkh6ngamdadU'Q'cchungminh (vadodobaitoanchovectO'BoolclingdU'Q'cgiaiquy~t).Chungt6ida chiracaisaicuabaibaatrentrong[6]. BezrukovaGronaudadU'ara thli'tlJ tuy~nHnhsaildaymachung t6igQila thli'tlJ BG. 2.2.1Dinh nghia. (Thu tlJ BG). Ta sap th1it'/!V(n) bangquing,p nhusau: Vdin =1 thiV(l) =IN auQ'csapt'/!nhien 0 <1<2<3<4<5<6<7<8<9... Xetn >1vagidsu trenV(n - 1)aacoth1it,/!. Choa, b fa hai vectacuaV(n) vdi a =al a2 . . .an=Ib = b1b2. . .bn- D I'Jt h =max{i : ai = Aa})k =max{i : bi= Ab}. Ta vitt a <b ntu (i) J1a< J1b)hol'Jc Cht1dng2. Dinh1fki~uKK 19 (ii) l1a=I1bva6ha<6kbtrongV(n - I), hOlfC (iii) l1a=I1bva6ha=6kbva wa <wb, hOlfc (vi) l1a =I1b va 6ha=6kb va wa =wb vaaj > bj trongdo j =a(a,b). DinhnghiatrenvaVIdl,lsaildayduQ'ctrlchtit [12]. Vi dv.2.1. TrongV(3), 27ph~ntit d~utientheothut\1'BG tangd~n la: 000,100,010,001,110,101,011,111,200, 020,002,210,201,021,211,120,102,012, 121,112,220,202,022,221,212,122,222. Nhcicl;;Lir~ngn~uA c V(n) thl Ai:dla t~phQ'pt:it cacacvecta'cua A cothanhph~nthui b~ngd. 2.2.2 Dinhnghia. Gia su trenV dO:comtjtth'lit7!tuytn t{nh,t'lic la trenV(n), n > 1 dO:comtjtth'lit7!toanphlin. Vdi A c V(n), 99i Ci(Ai:d)la IAi:dlvectadliu tiencuaV(n) cothankphlin th'lii bangd vap=max{l1a:a E A}. (i) Ph~nnenthui (i-compression)cuaA duqcdink nghfala p Ci(A) =U Ci(Ai:d)' d=O (ii) Ntu Ci(A) =A thi ta baoA co bi nend thanhph~nthti i (i-compressed). Vi dv. 2.2. Xet V(3) v6i thu t\1'BG. Cho A ={122,212,222}thl A =A3:2 nenCi(A)g6m3vectO'd~utientrongthut\1'BG cothanhph~n thu3 b~ng2. TheoVi dl,l2.1thl 3vectO'd~utien:iyla 002,102,012, tuclaC3(A)={002,102,012}. . Vi dv.2.3. Xet B(5) v6ithut\1'BG. Ta d9-t ~ = {00000,10000,01000,00100,00010,00001,11000} G = {10001,01001,00101,00011} 1l = {10100,01100,01010,01001}. Ch!1O'I1g2. Djnh If ki~uKK 20 V6i A =E uG thl CI(AI:O)g5rn8 veda'd~utiencuaB(5) cothanh ph~nthunhatla 0vaCI(AI:I) g5rn3vecta'd~utiencothanhph~nthu nhatla 1. V~yph~nlienthunhatcuaA la CI(A) =CI(AI:O) U CI(AI:I) =E U H. D~Y r~ng,trong VI d\l nay A bi lien (j thanh ph~nthu 5. Trong [12],BezrukovaGronauchor~ngthutv BG lathlchhQ'ptrenV(n). Chungtoidachirar~ngdi~unaykhongdungb~ngphanVId\lsail: Phan vi d\l 1. XetV(3)v6ithutv BG vaA C V(3): A = {000,100,010,001,110,101,011,111,200,210,201,211}. C(A) la t~phQ'pIAI =12veda'd~utiencuaV(3)trongthutv BG (xernVI d\l2.1)lien C(A) ={OOO,100,010,001,110,101,011,111,200,020,002,210}. Ta co LlA ={DO,10,01,11,20,21}. LlC(A) ={DO,10,01,11,20,02,21}. V~yILlC(A)1= 7 > ILlA!=6 lienthutv BG la khongthIchhQ'p. VI banthanthutv BG khongphaila thutv thIchhQ'plienbaibaa [12]khongth~sUachila.Trongbaibaaay,BezrukovaGronauda "chungrninh"vaSUd\lng"bE>d~"sail: ILlCi(A)1<ILlAI, i =1 hayi =n ,VA C V(n). Di~unaysai trenB(n) v6i i =1va saitrenV(n) v6i i =n,nhu trongcaephanVId\l sail: Phan vi d\l 2. ChoA ={122,212,222}c V(3)thl theoVi d\l2.2ta coC3(A)={002,102,012}.Dodo LlC3(A)= {DO,10,01,02,12}vaL1A= {12,21,22}. Ch11O'Ilg2. Dinh if ki~uKK 21 V~y ILlC3(A)1=5>ILlAJ =3. Phan vi dl,l 3. Xet B(5) vai thu tl! BG vaA =E uG C B(5) nhU' trongV{dv 2.3.D~tM ={OOOO,1000,0100,0010,0001,1100}thl LlA =M U {1001,0101,0011} LlC1(A)= M U {1010,1001,0110,0101} V~yILlC1(A)1=10> ILlAI =9. SaiH1mcuaBezrukovaGronauchotha:yr~ngvi~cchungminhdinh Iy ki~uKK kh6ngphaiIa di~udO'ngian. 2.3 K-poset cae vectd Bool Trangph~nnay,ta sechungminhr~ngB Ia K-posetb~ngca,ch chungminhr~ngthutl!V Iath{chqptrenB. Nh~cl<;1ir~ng(jdayta giaSlrVa=max{i: ai =O}vaia E B(n), a =I- gn khi tlnh a*. 2.3.1Dinh nghia. (Thutl! V). Chaa vab la 2 vectakhdcnhaucua B(n):a=ala2...an, b=b1b2...bn-Tavitta<bntu (i) wa <wb) ha(jc (ii) wa =wb vaai = 1>bi=0 vdi i = a(a,b). V~yZn= 00.. .0 lavedO'nhonha:tvagn=11. . .11avedO'Iannha:t cuaB(n). Ngoaifa, d~tB(n,k) ={aE B(n) :wa =k},0<k< n thl taco 2.3.2B6 d~.Ntu a =minB(n,k) vab =maxB(n,k) thl a =gkzn-k, b = zn-kgk (2.1) ChUng minh. N~uk =0 hayk =n thl (2.1)la hi~nnhienlienta chixet1 < k < n. Choc E B(n,k). N~uc =I- a thl coi nhonha:t, 1Ci =0 vai i=a(a,c). Suyraa<c. V~ya=minB(n,k). Ph~ncon l;;tichungminhtU'O'ngtl!. ChttO'Ilg2. Djnh 1f ki~uKK 22 Vi d\l 2.4. Cacvecta'cilaB(4)dU'qcs~ptheothutlJ tangd~nnhU'sau B(4): 0000,1000,0100,0010,0001,1100,1010,1001, 0110,0101,0011,1110,1101,1011,0111,1111. Ta co1100=minB(4,2), 0011=maxB(4,2). Tir dinh nghia,ta co ngayk~tquasail day: 2.3.3B6 d~. Vcfia E B(n) vax, Y E B(r) thi ax, ay, xa, ya ia caevectaeuaB(n+r) vataco x <y {:} ax <ay{:} xa <ya (2.2) Nh~c19-ir~nga*= 8hav6ih = Va = max{i : ai = O}. 2.3.4B6 d~.VcfiaE B(n) taco a*=max{Lla}=max{81a,...,8na} (2.3) ChUng minh. N~uwa =n tUGla a =gn thl k~tquala hi~nnhien. Coia =I- gnvachox =8ja Ella, a* =8hav6i h =Va =I- j. N~u aj =1 thl VI wx < wa*lienx < a*. Ta chixet trU'Cfnghqpaj =0 vadodowx = wa*= wa. Dodinhnghiacilah , ta coj < h vata coth~gia sir aj+l =1 (vI n~uaj =aj+l =0 thl 8ja =8j+la). Khi {£y Xj =aj+l =1>aj =aj=0vaj =a(x,a*)lienx <a*. V~ya =max{Lla}.O 2.3.5B6 d~. Vdia E B(n) taco aO=min{bE B(n+1):b*=a} Oa=max{bE B(n+ 1): b* =a} (2.4) (2.5) Chll'ngminh. Coi b E B(n +1)saGchoa =8hb=b* v6i h =Vbva tacoth~giasirh=max{i: bi=O}. N~uh =n thl b =aOlientaxeth <n, dodobh=0vabh+l=1. VI b* = a lienah = bh+l= 1 > bh= 0 vata cob > aO. V~y aD=min{bE B(n+1):b*=a}.Ta dachungminh(2.4). Cht1O'I1g2. Djnh If ki~uKK 23 Xet (2.5). D~tT =min{j : aj =1}vau =Ga. VI a =Jhb v6i h =Vb nen T < h. N~uT =h thl bl =. . . =bh =0 nenb =u. N~u T Ur =0vaT =a(u,b) nenb <u nghiala u=Oa=max{bE B(n+1):b*=a}.O 2.3.6Bo de. Vdia, b E B(n) vaa =I- b taco a <b =* a* <b* a*<b* =* a <b (2.6) ChUng minh. Ta bi~tr~nga* = Jha, b* = Jkb trongdo h=max{i :ai=O},k =max{i:bi=O}.N~ub =gnthlb*=gn-lva tacongayk~tquanentachixettrl1o-nghqpb =I- gn vadodowa*=wa vawb*=wb. N~uwa<wb thl a* <b* VI wa* <wb*. GiaSlrr~ngwa=wb thl VIa bi=0v6ii =a(a,b). VI aj =bj v6i j <i va wa=wbnencot >i saochoat=O.Vf).yh >i. Hi~n hienk >i. N~u k =h hayk >i thl a(a*,b*) =i vaai=1>bi=0 nena*<b*. N~u k=i thlbj=1,Vj >i vaaj=1,Vj >i, j =I-hnentacoa*=b*. Bay gio-gia S11a* < b* thl wa =wa* <wb* =wb. N~uwa*<wb* thl VI wa <wb nena <b. Ta xettrl1o-nghqpwa*=wb*. VI a*<b* nenai =1> bi=0v6ii =a(a*,b*),vadodocot >i saochoat=O. Mah =Va, k =VbvatheoB6d~2.3.4thla*=maxda, b* = maxdb nenh > t > i vak > i. guyraai =ai, bi = binena(a,b) = i v6i ai= 1>bi=0vadodoa <b.O 2.3.7Bo de. Vdia E B(n) vab =a-, c = a+}nghfala c -< a -< b. Taco b = { uO1grzp-1 gr+lzp-l C = { zp+lgr-l V 10zpgr trongdo p,T co the la O. ChUng minh. Chliyr~ngmQtvectC1a E B(n) comQttronghaid~ng trong(2.7)ho~ctrong(2.8). VI (2.8)la h~quacua(2.7)nenta chi ..Ineu n~u a =u1zpgr a =zpgr a =grzp a =vO1grzp (2.7) n~u (2.8)..Ineu Chl1O'ng2. Djnh 1f ki~uKK 24 c~nchungminh(2.7).N~ua =zpgrvaip >1vap+r =n thla la vectO'Ian nh:itcotrQnghrQ'ngb~ngr lienb la vectO'd~utiencotrQng hrQ'ngr + 1,dodob =gr+lzp-ItheoB6de2.3.2.NguQ'C19-i,a phaico d9-nga =u1zpgrvai p > 1var >O.D;?tx =u01grzp-Itasechung minha -<x tuc la x =b. Hi~nnhiena <x. Gia sucoy E B(n) saG choa <y <x thlwx =wy =wa. Ta vi~ty duaid9-ngy =ef vai dime =dimu. N~uco i saGcho ei >Ui ho;?cei <Ui thl Y <a ho;?c y >x. Ca haitru0'nghQ'pdelivo H liene =u vatif (2.2)tasuyra d =1zpgr <f <01grZp-I=h. N~uthanhphandaticuaf la 0thlta co fl =6If < 19rzp-I =h' vaVIWfl= wh' lientheo(2.1)taphaico f' =h' =>f =h =>y =x. N~uthanhph~nd~ucuaf la 1 thily lu~n tuO'ngtv nhutrenta coy =a. V~ya y =x ho;?cy =a liena -<x tuc la x =b.O 2.3.8Bo d~. ChoA c B(n). Ntu A to'm(JtIS thi LlA ciingto'm(Jt IS va hO'nnila, ntu A =GO+HI thi (i) G, H to'caeIS trongE(n-i). (ii) LlA =G =A* ={a* : a E A} (2.9) ChUngminh.(i) Chox <y vay E G, ta sechungminhx E G. D;?t u =xO, v =yOthl VI y E G lienv E GOc A. Ta cou < v theo (2.2).MaA lam9tIS vav E A lien u E A, tuc la xOE GOlienx E G. ChungminhtuO'ngtv choH. (ii) Hi~nnhienG c A* c LlA. Chox E LlA thl coa E A saGcho x ELla. D;?tu =xOthl u* =x <a* lienu <a vaVIA la m9tIS lien u E A. V~yx =u* E A*. HO'nnuaxOE GOlienx E G. Ta dachung minhLlAc A*c GvadodoLlA=A* =G.O 2.3.9 Bo d~. ChoA to,m(JtIS cuaB(n), n >3 vdiA =GO +HI. Ntu G =GoO+Gl1vaH =HoO+Hl1 thi H c G va HIe Hoe GleG 0 (2.10) ChUngminh. TheoB6de2.3.8thlG, H, Go,GI, Ho, HI delilaIS. Vaix E H thlxl E HI c A vaVIxO<xl lienxOE A, tuclaxOE GO lienx E G. Ta dachungminhHe G. Chttcmg2. Dinh1fki~uKK 25 Bay gi0'ta chungminh Ho C GI. Cho x E Ho thl xO E H lien x01 E HI C A. VI x10 < x01 lien x01E A =;.x10E A =;.xl E G =;.x E GI. Theoph~nd~uthlHI c HovaGI c Golien HI C Ho C GI C Go.O Vi d\l 2.5. ChoA =B(5)thlA =GO+HI vci'iGo, GI, Ho, HI nhU' trongbimgsail Bang2.1 Bangtrenchota th~ycaevectO'dU'Q'cs:iptheothli tlJ V cuaB(2) trongGo,Gl1 Ho, HI, cuaB(3) trongG, H vacuaB(4)trongGO+H1. Hemnua,Bang2.1clingchotath~y(2.10)dungvci'imQiIS trongB(4). GI Go GO HI Ho HI 00 0000 10 1000 01 0100 00 0010 0001 00 11 1100 10 1010 1001 10 01 0110 0101 01 0011 00 11 1110 1101 11 1011 10 0111 01 1111 11 ChwJng2. Dinh1fki~uKK 26 2.3.10 Dinh Iy. Cho G, H to'IS cua B(n) ,n > 2 vdi H c G va A = GO+HI. Ntu G = GoO +Gl1 vaH =HoO+Hl1 thi LlA = { G n~uHo C Gl GoO+ Ho1 lieU Gl c Ho ChUng minh. VI G, H la nhilng IS cua B(n) lien thea B6 d~2.3.8 thl LlG = Go, LlH = Ho va VI H c G lien ta co LlA = G U (LlG)OU H U (LlH)l = G U GoOU Ho1 = GoOU Gl1 U Hol. V~y n~uHo C Gl thl LlA = GoOU Gl1 = G va n~uGl LlA = GoOU Hol.O (2.11) c Ho thl 2.3.11Dinh nghia. (i) Vietabitcuaa E B(n) duqc dink nghia to'- - - - /. a= ala2...an val - - { 1 n~uai =0a. - , z 0 neu ai =1 (ii)PhlinbitcuaA C B(n) to'A ={a:a E A}. Hi~nnhienIAI =IAI vataco Ll(A)= LlA, ILl(A)1=ILlAJ (2.12) 2.3.12 Dinh If. Ntu h? thucLlC(X) c C(LlX) dungvdi m9itQ-Pcon X cuaB(n - 1), n >2thitaco I LlCn(A) I <ILlAI, VA c B(n) (2.13) ChUngminh. V6iA = MO+N1 E B(n)thlCn(A)= GO +HI v6i G = C(M), H =C(N). Thea(2.12)ta co ILl(A)1 = ILlAI = IL1AI. B~ngeachthay A b6'iA n~uc~nta co th~gilt su INI < IMJ va da do H = C(N) c G =C(M). Theagiathi~t,LlGc C(LlM), LlH c C(L1N) lien ta sur fa IL1GI <IL1MI, IL1HI<ILlNI. Ngaai fa, (L1M)O+(L1N)lc L1Alien IL1MI+IL1NI <IL1AI. Cht1O'IIg2. Dinh if ki~uKK 27 Thea (2.11)thl L1C(A) = { G n~uHoC G1 n GoO +Ho1 n~uG1C Ho V~yn~uL1Cn(A)=G thl IL1Cn(A) I = IGI = 1M! < L1Cn(A)=GoO+Ho1thl ' IL1Cn(A)1 = leal+IHol =IL1GI +IL1HI < IL1MI +IL1NI < IL1AI.O IL1AI, con n~u 2.3.13Djnh nghia. Ta baoA c B(n) la binentungph~nhayPC (partcompressed)ntu Cn(A)=A, nghialaA cod(}ngA =GO+HI vdi G, H la nhiingIS cuaB(n - 1). 2.3.14Djnh nghia. G9i r la Uj,phqp caeveeta'cuaB(n) co d(}ng uzp1vdi u =0hoq,cthanhphlin cu6/icuau la 1 va p > 1. Vdi a =uzp1 E r ta a(j,tfa =u1zp' (i) AnhX9d5n'ljJtit A c B(n) vaoB(n) auqc ainhnghianhusau 'ljJ(a)= { fa n~ua E r v~ fa rj.A a lieu ngl1qcl;;tl (ii) A c B(n) gQila 'ljJ-d6ng('ljJ-clased)n~u'ljJ(a)=a, Va E A Nh~nxetding'ljJ(a)<a lien'ljJ"d~y"A v~ph{atrl1<1c(trangthuttJ v), dadon~uA la ffi9tIS thlA la'ljJ-dong. 2.3.15Djnh If. Ntu A C B(n) la PC thi L1'ljJ(A)c'ljJ(L1A) (2.14) vadoao 1L1'ljJ(A) I < IL1AI (2.15) ChUng minh. C~nchliyr~ng'ljJ(]v~tr<licua (2.14)la anhX;;tu A vaaB(n)con'ljJ(]v~phailaanhX;;ttuL1AvaaB(n- 1).HO'nua,n~u x E L1Avax ='ljJx thl x E 'ljJ(L1A). Chttdng2. Djnh1fki~uKK 28 VI A la PC lienta coth~vi~tA =GO+H1vaiG, H lad,cIS cuaB(n - 1).NhutrongchungminhcuaB6d~2.3.12,tacoth~giaS11 HcG. Chox E Ll~(A)thlcob =~(a)E ~(A), a E A saGchox E Llb tuc lax E Ll~(a).Ta sechungminhx E ~(LlA).N~ua E GOthl~(a)=a lienx E Lla. D~tu =xOthlu <a. VI G la IS ta cou E GOlien x E G va~(x)=x tuclax E ~(LlA).V~ytachic~nxeta E H1vai3 trudnghQ'p:a tj.r, a E r va"faE A, a E r va"fatj.r. T rL1dnghqp 1. a tj.r. Trudng hQ'pnay a co d 0, dimgr =r > 2va b =~(a)=a lienx E LlA. N~ur > 3 hayx =6j(UZp)grthl 2 thanh ph~ncu6icuax la 11lienx =~(x) E ~(LlA). Gia S11a =uzp11va x =uzp1vaip >1.D~tc=u1zp1thl x E Llc. Hi~nnhienc <a E H1 vaVI A la PC lienc E H1. Suyra x =uZp1vau1zpd~u(j trongLlA va VI v~yx =~(x)E ~(LlA). TrudnghQ'p1coth~duQ'ctomt&tnhusail Bang2.2 TrL1dnghqp2. b =a =uzp1E r va"fa=u1zpE A. Nh&cl<;1ir~ngthanhph~ncu6icuau la 1ho~cu =0vaVI~(a)=a lien "fa = u1zpE A. Trudng hQ'pnay ta clingco ~(x) =x, Vx E LlA nhu duQ'cth~hi~n(j Bang 2.3ma (j dongthu tu ta co "fX=v'llzp E LlA VI b =v11zpE A. Controngdongcu6iclingta coa =wzr1zp1:::} "fa= wzr11zpE A :::}w1zr1zpE A (vIA la PC vaw1zr1zp<"fa)lien w1zrzpEllA. a x Ly dox = (x) Ghi chi uzpgr uzpgr-l IJinh nghiacua r >2 uzp11 u'll IJinh nghiacua r =2, u' E Ll(uzp) uzp11 uzp1 c<aEA:::}cEA r - 2 c - u1z 1-, - p :::}"fX= u1zpE LlA ChltO'Ilg2. Djnhif ki~uKK 29 Bang 2.3 T rL/anghqp 3. a = uzplEr va b =ulzpfj. A. Tn1C1nghqpnayta cox ='I/J(y)v6iy E L1Anhl1dl1qcth~hi~ntrong bangsail Bang 2.4 TrongBang2.4,(jdongdatitacox = 'I/J(X)neux E L1Avax = 'Ij;(y) neux fj. L1A. Phancu6iclingta phaichungminhla (2.15),nhl1ngh~thucnayla hi~nnhienVI I'I/J(L1A) I =I L1AI. 2.3.16 B6 d~. Cho A =GO+HI c B(n) vdiA to'PC va H c G thi L1A=A* = {a* : a E A} (2.16) ChUng minh. Do A* c L1Anenta chungminh chi~ungl1qcl(;1i.VI A la PC nenG, H lanhungIS cuaB(n - 1).V6ix E L1Athl coa E A saGchox E L1a,tuclax =6jav6imotj vax <a*. Gia S11a EGO. Dq.tc =xOthlc <a*O=a nenc E GOc A VIA la PC. V~yx= c* E A*. a x Ly dox = 'I/J(x) Chi ch'li uzpl uzp Dinh nghiacua'I/J p>l uOl ul Dinh nghiacua 'I/J p=l uzpl uzp-Il Ix =UlZp-1E L1A P >2, ,a=ulzp E A vlzpl v/lzpl IX =v/llzp E L1A u =vI, v' E L1v wzrlzpl wzrzpl Ix =wlzrzp E L1A u =WZr1, r >0 a b x y Chi ch'li uzpl ulzp UlZp-1 uzp-Il p>l uOl ul0 ul x x E L1A, p =1 vlzpl vllzp v/llzp v/lzpl u =vI, v' E L1v wOlzpl wOllzp wOlzp x x E L1A, u =wOl Ch11C1ng2. Dinh 1f kiiiu KK 30 Xet trU'C1nghQ'pa E HI, tuc la a =u1 v<1iu E H. TrU'<1ctien,xet x = 6na=u E H c G. Ta couOE GOlienx =(uO)*E A*. Gia 811 x =vI = 6jaV<1ij =In. D~tb =vOl thl b* =vI =x <a* lienb <a 8UYrab E A (doA la PC). V~yx =b* E A*.0 Ta dachungminhL\Ac A*vadodoL\A=A*. 2.3.17Bo d~. ChoA =GO+HI C B(n) vaiH c G vaA la PC nhungkh6ngla IS. GQie =ele2...en la vectanhdnhatcuaB(n) kh6nga trongA vaf = ili2 . . .in la vectalannhatcuaA. Taco (i) L\e- {e*}C L\A vantuen=1 thie*E L\AJ tucla L\ec L\A. (ii) (L\f - {f*})c L\(A - {f})vantu in =0 thif* ~L\ (A - {f}). ChUng minh. (i) V<1ix E L\e,d~ta =xOthl ta coa* =x <e*. N~ux =Ie*ho~cx = e*vaen= 1thl a <e lien a E A do dinhnghia cuae vadodox E L\A. V~yta co(i). (ii)Chox E L\f, x <f* thlx E L\A - {f*}.VI L\A =A* theo(2.16) lienx E A*-{f*} :::} x = a*.VI a*=x <f* liena <f:::}a E (A-{f}). V~yx =a* E L\(A - {f})vadodo(L\f- {f*})c L\(A - {f}).Ngoai ra theoB6 d~2.3.5thl n~uin =0ta cof* ~L\(A - {f}).0 Nh~clq.idingn~uy la trQitnJc ti~pcuax thl ta vi~tx -< y. 2.3.18 Dinh nghia. (i) M(jt do~n-zero(O-slice)cua B(n) la m(jt day vectacuaB( n) lien titp nhaual -<a2. . . -<as saochothanhphlin thu, l ' 0 ' ~/ ,n cua al, . . . ,as a va neu u =Ul . . .Un -< al va as -< v =VI . . .Vn thiUn =Vn =1. Dinh nghiatuangtv:chodo~n-m9t(1-slice). (ii) Ntu I la aor;r,n-zerova J la aor;r,n-m(jtthi ta vitt I -<J hay J -<I My theoI a ngaytruac J hayJ a ngaytrudc IJ tuc la I -< J n~u maxI -< mill J, J -< I n~u maxJ -< minI. 2.3.19 Bo d~. Cho I la m(jtaor;r,n-zeroJJ la m(jt aor;r,n-m(jtcua B (n), n >2 vai a =maxI va b =mill J. Ta co ChItO'ng2. Djnh1fki~uKK 31 (i) a =ugrO vdi T >1vau =0hayu codq,ngu =vO. Han nila T =1 ~ IIi >2, T >2 ~ III =1. (ii) b =ezp1vdip > 1 vae =0haye codq,nge=f1. Han nila p =1 ~ IJI >2, p >2 ~ IJI =1. Vi dl,l 2.6. B(4) dU'Q'cphanho9-chthanhcacdo9-n-zerovado9-n-mt)t theothutv tangdaTInhU'sail Hinh2.1 0 day ta co II -<J1 -<12-<J2 -<13-<J3 -<14-<J4. HO'nnua IIsl =1{::} IJsl >1, s=1,. .. ,4. Do9-n-zero Do9-n-mt)t 0000 II 1000 0100 0010 0001} J1 { 11 0012 1010 13 {0110 IDOl} J2 0101 }0011 J3 14 {1110 1101 1011 J40111 1111 Ch1.1dng2. Djnhif ki~uKK 32 ChUng minh 2.3.19. TrltC1nghQ'pn =2la hi~nnhienlienta chixet n> 2. (i) N~ua =ala2'" an vai an-l =an =0 thl a co d<:tnga =w1zp vai p >1. D~tc =W01Zp-l thl Cn =0 vaa -< c theo (2.7) lien eEl theodinhnghiacuaI, di~unaymallthu~nvaiHnhIannha:tcuaa. V~y an-l =1vatacoth~vi~ta=ugrOvai r >1vau =0hayu cothanh ph~ncu6ila 0:u =va. D~td =a- tuc d -<a. N~ur =1thl a =v010(vIn >3)thld =v100liendEl vadodo III >2. Giasitr >2. Theo(2.8)thl d = { OOgr-l v100gr-l n~u u =0 n~u u =vO TrltC1nghQ'pnaythl thanhph~ncu6icuad la 1lien d~I=}I={a} tuc la II I = 1. Ph~n(ii),dltQ'cchungminhhoantoantltO'ngt1J.O 2.3.20B6 d~. ChoI, J ttintuqtto,aog,n-zerova aog,n-m{jtcua B(n), n >3 saGchoI -<J. Taco III =1~ III >2 III >2~ IJI =1 ChUng minh. D~ta =maxI vab =mill J thl a -<b. (2.17) (2.18) Gia sit I ={a}.TheoB6d~2.3.19(i),a coth~vi~ta =ugrOvai r > 2vahO'nua,a -<ugr-l01 -<ugr-2011lienugr-l01, ugr-2011E J, nghiala III >2. Dao l~i,cho IJI > 2. TheoB6d~2.3.19,ta coth~vi~tb =vlOl =} a =vllO. D~tc =a-, nghiala c -<a. N~uv11 =gn-l thl theoB6 d~2.3.2,a la vectO'd~utiencuaB(n,n - 1)vac la vectO'cu6icling cuaB(n,n - 2) lienc =00gn-2 =} C ~I. NgltQ'cl<:ti,ta co th~vi~t Chttdng2. Dinhif kiJu KK 33 a =wzpgrOvai p > 1, r > 2vatheo(2.8)thl c =wzp-1100gr-1=:} c ~I. V~yI ={a}tucla III =1. (2.18)laphandaocua(2.17).0 2.3.21B6 d~.G9i:J la tg,phqptfttcdcacaoq,n-m{jt cuaB(n), n >3. Taco IJ*I =1,VJ E :J (2.19) ChUng minh. Ta chicanxettru0'nghQ'pIJI >2. Chox, y E J vai x <y thl x* <y*. Gia S11x* <y*. D9.tw = y*Othl w #-y VIYn= 1 vatheo(2.4),tacow X*. V~yx <w <y. Dieunaykh6ngth~xayraVI J la do(;1n-m<)tma hanhphancu6icuaw la 0.0 2.3.22Dinh Iy. Vdi m9iA c B(n) ta co L1C(A)c C(L1A) (2.20) hay turJng aurJng IL1C(A)1<IL1AI (2.21) ChUng minh. Chuyding(2.20)va(2.21)tuO'ngduO'ngVIL1C(A)la m<)tIS theoB6de2.3.8va IL1AJ=IC(L1A)1 Ta chungminhdinhly b~ngquin(;1ptheon. Tru0'nghQ'pn = 2co th~duQ'cki~mchungm3 vadinhly dung vain - 1,ta sechungminhdinhly clingdungvai n. N~uA la IS thl hi~nnhiendinhly dunglienta chixetA kh6ngla IS. Ta setungbuacchuy~nA thanhC(A) ma(j m6ibuac,ta chuy~n A thanhD vai JL1DI<IL1AI. BVdC 1 Dat AD = A Al =C (A) A2 = "/'(AI ) A3 =C (A2)'. , n, 'f', n, A4 = 1/;(A3). . ., tuc la Ar+1= { Cn(Ar) n~ur ch~n 1/;(Ar) n~ur le vaiCn(Ar)la phanlienthun cuaAr va1/;la anhX(;1demoVI A la hUll h(;1nlient5nt(;1iqsaGchoAqla PC va1/;-dong.DocaeDinhly 2.3.12va ChUdng2. DinhIf ki~uKK 34 2.3.15ta co IL1Aql< IL1Aq-11< ... < IL1AI.B~ngcachxetAqthaycho A, ta coth~gia811A 1aPC va7f-dong,tuc1aA = GO+H1 vdiG, H 1a cacIScuaB(n-1) ,HCGva7f(a)=a, Va EA. HO'nnua,L1A=A* theoB6d~2.3.16. BLldC 2. N~uH =0thlA =GO.D~tF =C(A) thl L1F=F* theoB6 d~2.3.8lien IL1C(A)1= IF*I <IFI = IAI= IGI<IL1AI vadododinh1yduqcchungminh.V~y,ta coth~gia811H #-0. BLldC 3. GQie =e1e2. . .en1avectO'nho nha:tcua B( n) khong(j trong A, f =i1i2'" in 1avectO'1dnnha:tcuaA ta coe < f VI A khong1a IS. HO'nnua, en #-in VI n~unguqc1C;1ithl e E A do A 1aPC. D~t D = (A - {f})U {e}thl hi~nnhienD 1aPC va 7f-dong.Ngoaifa, L1D=D*. N~uen=1, in =0thltheoB6d~2.3.17taco L1ec L1A=A*vaf* (j.L1(A- {f}). Dodo L1D= D* =A* - {f*}= L1A- {f*}=}IL1DI= IL1AI- 1. L~p1C;1iquatdnhnay(v6iA :=D) chod~nkhien= 0, in = 1. BLldC 4. en =0, in =1. GQi J 1adoC;1n-m9tchuaf va I 1adoC;1n-zero ngaytrudc J (tuc 1aI -< J) vaa =maxI, b =mill J. TheoB6d~ 2.3.19thlb coth~vi~tb =uzp1 v6i U =0ho~cU co dC;1ngU =v1. Do 7f(A)=A ta col'b =u1zp E A. Ngoaira l'b =mill I do (2.8).N~u e (j. I thle<l'b vaVIA 1aPC lieneE A vo1y.V~yeEl. N~up =1 tuc 1ab co dC;1ngb =v101va do B6 d~2.3.19,ta co IJI >2vatheo(2.17)thIIII =1,nghia1aI ={a}vdi a =u110.VI 7f(b)=b lienl'b =u110E A, tuc 1aa E A. Suyfa, A 1am9tIS, td.i giathi~tvadodop >2.Theo(2.18)thIIJI =1 lienb =f vaJ ={f}. VI D =(A - {f}) U {e}ta co D 1aIS nghia1aD =C(A)vatheoB6 ChtiO'11g2. Djnh If ki~uKK 35 d~2.3.17thl i1D =(i1A - {f*})U {e*}=>Ii1DI = Ii1AI. V~ydinhly duQ'cchungminh.O V{dl,lsail daysechota tha:ym(>tungdl,lngcuak~tquatren. Vi d\l 2.7. Gia S11ta co r <2ncongvi~cduQ'cmahoab~ngr vectO' datitiencuaB(n) trongthu tv v (m6icongvi~ctuO'ngungv6i m(>t vectO')vanhllngcongvi~cnaycancacthi~thi, m6ithi~tbi duQ'cma hoab~ngm(>tvecta'trongB (n - 1). Gongvi~ccomala a cancacthi~t bi comala cacvecta'trongi1a. V6im tnhanviense duQ'cxemla hoanthanhnhi~mVl,ln~uthvchi~nduQ'cm trongr cong vi~cdacho,vaseduQ'cthu<1ngn~uthvc hi~nm congvi~cnayv6is6 thi~tbi {tnha:t.HoinhanviennayphaichQnm congvi~cnaod~hoan thanhmaduQ'cnh~nthu<1ng? Hlnh2.2du6idaymota tru0'nghQ'pn =4. Thi~tbi : Hlnh2.2 Theo Dinh ly2.3.22,nhanviennayseduQ'cnh~nthu<1ngn~uchQn m congvi~ccomala mvectO'datitiencuaB (n) trongthutv V. 0 D6i chi~uv6iDinhnghia1.2.4v~K-poset,ta co 2.3.23Dinh If. T(j,phqpB eaevectaBoolla miltK-poset. ChUng minh. Ta dabi~tB la m(>tposetco hc;1ngv6i mucthun la B(n). V6in > 1thlhi~nnhieni1B(n)=B(n - 1). V6ithutv tuy~n t{nhlathutv V thltheoB6d~2.3.8tacoi1A la IS n~uA la ISvahO'n nlla,Ii1C(A)1tK-poset.O