Tài liệu Toán rời rạc 2 - Phạm Tiến Sơn

267 trang hapham 2800

Download

Bạn đang xem 20 trang mẫu của tài liệu "Tài liệu Toán rời rạc 2 - Phạm Tiến Sơn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

tai_lieu_toan_roi_rac_2_pham_tien_son.pdf

Nội dung text: Tài liệu Toán rời rạc 2 - Phạm Tiến Sơn

. TOAN´ RO` IRA. C2 . Pha.mTiˆe´nSon D- `aLa.t - 2009
Mu. clu. c L`o.i n´oid¯ˆa` u7 . . 1D- a.icuong vˆe` d¯` ˆo thi. 9 1.1 D- .inh ngh˜ıav`ac´ackh´ainiˆe.m 9 . . 1.1.1 D- `ˆo thi. c´ohu´ong 9 1.1.2 D- `ˆo thi. v`a´anhxa. d¯atri. 10 . . 1.1.3 D- `ˆo thi. vˆohu´ong 11 1.1.4 C´acd¯i.nhngh˜ıa 11 1.2 Ma trˆa.nbiˆe˙’udiˆe˜nd¯ˆo` thi. 14 1.2.1 Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung 14 1.2.2 Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh 16 1.2.3 Ma trˆa.nkˆe` 19 . 1.2.4 C´accˆa´utr´uc d˜u liˆe.ubiˆe˙’udiˆe˜nd¯ˆo` thi. 20 1.3Liˆenthˆong 26 1.3.1 Dˆaychuyˆ`env`achutr`ınh 26 1
. . 1.3.2 D- u`ong d¯iv`ama.ch 27 1.3.3 D- `ˆo thi. liˆenthˆong 28 1.3.4 Cˆa`u, k−liˆenthˆong 33 1.3.5 D- `ˆo thi. liˆenthˆongma.nh 36 1.4 Pha.m vi v`aliˆenthˆongma.nh 37 1.4.1 Ma trˆa.n pha.mvi 38 1.4.2 T`ım c´acth`anhphˆa`n liˆenthˆongma.nh 42 1.4.3 Co. so˙’. 44 1.5 D- ˇa˙’ ng cˆa´ucu˙’ a c´acd¯ˆo` thi. 47 1.5.1 1−d¯ ˇa˙’ ng cˆa´u 48 1.5.2 2−d¯ ˇa˙’ ng cˆa´u 50 1.6 C´acd¯ˆo` thi. d¯ ˇa.cbiˆe.t 52 1.6.1 D- `ˆo thi. khˆongc´oma.ch 53 1.6.2 D- `ˆo thi. phˇa˙’ ng 53 . 2 C´acsˆo´ co ba˙’ ncu˙’ ad¯ˆo` thi. 55 2.1 Chu sˆo´ 55 2.2 Sˇa´csˆo´ 58 2.2.1 C´ach t`ımsˇa´csˆo´ 62 2.3 Sˆo´ ˆo˙’nd¯i.nhtrong 63 2.4 Sˆo´ ˆo˙’nd¯i.nhngo`ai 69 2
2.5 Phu˙’ 74 2.6 Nhˆancu˙’ ad¯ˆo` thi. 78 2.6.1 C´acd¯i.nhl´yvˆe` tˆo`nta.i v`aduy nhˆa´t 78 2.6.2 Tr`ocho.iNim 81 3 C´acb`aito´anvˆe` d¯ u .`o.ng d¯i 83 3.1 D- u.`o.ng d¯igi˜u.a hai d¯ı˙’ nh 83 3.1.1 D- u.`o.ng d¯igi˜u.a hai d¯ı˙’ nh 83 3.1.2 D- `ˆo thi. liˆenthˆongma.nh 84 3.2 D- u.`o.ng d¯ingˇa´n nhˆa´tgi˜u.a hai d¯ı˙’ nh 86 . . . . . 3.2.1 Tru`ong ho. p ma trˆa.n tro.ng luo. ng khˆongˆam . . . . . . . . . . . . 87 . . . . . 3.2.2 Tru`ong ho. p ma trˆa.n tro.ng luo. ng t`uy´y 92 . . . 3.3 D- u`ong d¯ingˇa´n nhˆa´tgi˜uatˆa´tca˙’ c´accˇa.pd¯ı˙’ nh 99 . . . . . 3.3.1 Thuˆa.t to´anHedetniemi (tru`o ng ho. p ma trˆa.n tro.ng luo. ng khˆong ˆam) 99 . . . . . 3.3.2 Thuˆa.t to´anFloyd (tru`o ng ho. p ma trˆa.n tro.ng luo. ng t`uy ´y). . . . 105 3.4 Ph´athiˆe.nma.chc´od¯ˆo. d`aiˆam 112 . . . 3.4.1 Ma.ch tˆo´iuu trong d¯ˆo` thi. c´ohai tro.ng luo. ng 113 4 Cˆay 115 4.1 Mo˙’. d¯` ˆa u 115 4.2CˆayHuﬀman 117 3
4.2.1 C´acbˆo. m˜a“tˆo´t” 117 4.2.2 M˜aHuﬀman 120 4.3 Liˆe.tkˆecˆay 123 4.4 Cˆaynhi. phˆan 126 . 4.4.1 Thuˆa.t to´anxˆaydu. ng cˆayt`ımkiˆe´m nhi. phˆan 130 4.5 Cˆaybao tr`um 132 4.5.1 Thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eurˆo.ng x´acd¯i.nh cˆaybao tr`um . . . 133 4.5.2 Thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eu sˆaux´acd¯i.nh cˆaybao tr`um . . . 134 . 4.5.3 T`ım cˆaybao tr`um du. a trˆenhai ma˙’ ng tuyˆe´n t´ınh . . . . . . . . . 135 4.5.4 Thuˆa.t to´ant`ımtˆa´tca˙’ c´accˆaybao tr`um 140 . . 4.5.5 Hˆe. co so˙’ cu˙’ a c´acchu tr`ınhd¯ˆo.clˆa.p 140 4.6 Cˆaybao tr`um tˆo´i thiˆe˙’u 145 4.6.1 Thuˆa.tto´anKruskal 147 4.6.2 Thuˆa.tto´anPrim 151 4.6.3 Thuˆa.t to´anDijkstra-Kevin-Whitney . . . . . . . . . . . . . . . . 155 4.7 B`aito´anSteiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 5 B`aito´anEuler v`ab`aito´anHamilton 163 5.1B`aito´anEuler 164 5.1.1 Thuˆa.t to´ant`ımdˆaychuyˆe` nEuler 166 5.2 B`aito´anngu.`o.id¯u.athu. TrungHoa 172 4
5.3 B`aito´anHamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.3.1 C´acd¯iˆe` ukiˆe.ncˆa`nd¯ˆe˙’ tˆo`nta.i chu tr`ınhHamilton . . . . . . . . . . 181 5.3.2 C´acd¯iˆe` ukiˆe.nd¯u˙’ d¯ ˆe ˙’ tˆo`nta.i chu tr`ınhHamilton . . . . . . . . . . 182 5.3.3 C´acd¯iˆe` ukiˆe.nd¯u˙’ d¯ ˆe ˙’ tˆo`nta.ima.ch Hamilton . . . . . . . . . . . . 186 5.4M˜aGray 190 6D- `ˆo thi. phˇa˙’ ng 193 6.1 D- .inh ngh˜ıav`ac´acv´ıdu. 193 6.2 C´acbiˆe˙’udiˆe˜n kh´acnhau cu˙’ amˆo.td¯ˆo` thi. phˇa˙’ ng 195 6.3 C´act´ınhchˆa´tcu˙’ ad¯ˆo` thi. phˇa˙’ ng 199 6.4 Ph´athiˆe.n t´ınhphˇa˙’ ng 202 6.4.1 Kiˆe˙’m tra t´ınhphˇa˙’ ng 207 6.5 D- ˆo´i ngˆa˜u h`ınhho.c 213 . 6.6 D- ˆo´i ngˆa˜utˆo˙’ ho. p 216 7Ma.ng vˆa.nta˙’ i 221 7.1 Mo˙’. d¯` ˆa u 221 7.2 B`aito´anluˆo`ng l´o.n nhˆa´t 223 . 7.2.1 Thuˆa.t to´ant`ımluˆo`ng l´on nhˆa´t 229 7.2.2 D- `ˆo thi. d¯ i` ˆe uchı˙’ nh luˆo`ng 230 7.2.3 Phˆant´ıch luˆo`ng 231 7.3 Nh˜u.ng ca˙’ i biˆend¯o.n gia˙’ ncu˙’ a b`aito´anluˆo`ng l´o.n nhˆa´t 233 5
7.3.1 D- `ˆo thi. c´onhiˆ`eu nguˆo`n v`anhiˆe` ud¯´ıch 233 . 7.3.2 D- `ˆo thi. v´oi r`angbuˆo.cta.i c´accung v`ad¯ı˙’ nh 234 . . 7.3.3 D- `ˆo thi. c´ocˆa.n trˆenv`acˆa.ndu´oivˆe` luˆo`ng 235 7.4 Luˆo`ng v´o.i chi ph´ınho˙’ nhˆa´t 236 7.4.1 Thuˆa.t to´anKlein-Busacker-Gowen . . . . . . . . . . . . . . . . . 236 7.5 Cˇa.pgh´ep 239 7.5.1 C´acb`aito´anvˆe` cˇa.pgh´ep 239 . 7.5.2 Cˇa.p gh´epl´on nhˆa´t trong d¯ˆo` thi. hai phˆa`n 242 7.5.3 Cˇa.p gh´epho`anha˙’ o trong d¯ˆo` thi. hai phˆa`n 244 . AThuviˆe.n Graph.h 247 T`ailiˆe.u tham kha˙’ o 263 6
L`o.in´oid¯ˆ`au . . . . . Trong thu. ctˆe´ d¯ ˆe ˙’ miˆeuta˙’ mˆo.tsˆo´ t`ınhhuˆo´ng ngu`oi ta thu`o ng biˆe˙’u thi. bˇa`ng mˆo.th`ınh . a˙’ nh gˆo`m c´acd¯iˆe˙’m (c´acd¯ı˙’ nh) - biˆe˙’udiˆe˜n c´acthu. cthˆe˙’ -v`av˜e c´acd¯oa.n thˇa˙’ ng nˆo´icˇa.p . . . . . c´acd¯ı˙’ nh biˆe˙’udiˆe˜nmˆo´i quan hˆe. gi˜uach´ung. Nh˜ung h`ınhnhu thˆe´ thu`ong go.i l`ac´ac d¯` ˆo . . . . thi Mu.cd¯´ıch cu˙’ a gi´aotr`ınhn`aycung cˆa´pnh˜ung kiˆe´nth´uccoba˙’ nd¯ˆe˙’ nghiˆen c´uu c´ac . . d¯` ˆo thi C´acd¯ˆo` thi. xuˆa´thiˆe.n trong nhiˆ`eu l˜ınhvu. cv´oi c´actˆengo.i kh´acnhau: “cˆa´utr´uc” . . . . trong cˆongtr`ınhxˆaydu. ng, “ma.ch” trong d¯iˆe.ntu˙’ , “luo. cd¯ˆo` quan hˆe.”, “cˆa´utr´uc truyˆe` n . . thˆong”,“cˆa´utr´uc tˆo˙’ ch´uc” trong x˜ahˆo.i v`akinh tˆe´, “cˆa´utr´uc phˆantu˙’ ” trong ho´aho.c, vˆanvˆan. . . . . Do nh˜ung ´ung du.ng rˆo.ng r˜aicu˙’ a n´otrong nhiˆe` u l˜ınhvu. c, c´orˆa´t nhiˆe` u nghiˆen c´uu . xung quanh l´y thuyˆe´td¯ˆo` thi. trong nh˜ung nˇamgˆa`n d¯ˆay;mˆo.t nhˆantˆo´ chu˙’ yˆe´u g´opphˆa`n . . . th´uc d¯ˆa˙’ysu. ph´attriˆe˙’n d¯´ol`axuˆa´thiˆe.n c´acm´ayt´ınhl´onc´othˆe˙’ thu. chiˆe.n nhiˆe` u ph´ep . . . to´anv´oitˆo´cd¯ˆo. rˆa´t nhanh. Viˆe.cbiˆe˙’udiˆe˜n tru. ctiˆe´p v`achi tiˆe´t c´achˆe. thˆo´ng thu. ctˆe´, . . . . . chˇa˙’ ng ha.n c´acma.ng truyˆe` n thˆong,d¯˜ad¯uad¯ˆe´nnh˜ung d¯ˆo` thi. c´ok´ıch thu´ocl´onv`aviˆe.c . phˆant´ıch th`anhcˆonghˆe. thˆo´ng phu. thuˆo.crˆa´t nhiˆ`eu v`aoc´acthuˆa.t to´an“tˆo´t” c˜ung nhu kha˙’ nˇangcu˙’ a m´ayt´ınh. Theo d¯´o,gi´aotr`ınhn`ays˜etˆa.p trung v`aoviˆe.c ph´attriˆe˙’nv`a tr`ınhb`ayc´acthuˆa.t to´and¯ˆe˙’ phˆant´ıch c´acd¯ˆo` thi . . C´acphuong ph´apphˆant´ıch v`athiˆe´tkˆe´ c´acthuˆa.t to´antrong gi´aotr`ınhcho ph´ep . . . . sinh viˆen c´othˆe˙’ viˆe´tdˆ˜e d`angc´acchuong tr`ınhminh ho.a. Gi´aotr`ınhd¯uo. c biˆensoa.n . . cho c´acd¯ˆo´ituo. ng l`asinh viˆen To´an-Tinv`aTin ho.c. . . Gi´aotr`ınhsu˙’ du.ng ngˆonng˜u Cd¯ˆe˙’ minh ho.a, tuy nhiˆenc´othˆe˙’ dˆe˜ d`angchuyˆe˙’n . . . d¯ ˆo ˙’i sang c´acngˆonng˜u kh´ac;v`ado d¯´o,sinh viˆen cˆa`nc´omˆo.tsˆo´ kiˆe´nth´ucvˆ`e ngˆonng˜u . . . . C. Ngo`aira, hˆa`uhˆe´tc´acchuong tr`ınhthao t´actrˆencˆa´utr´uc d˜u liˆe.unhudanh s´ach liˆen 7
. kˆe´t, nˆen d¯`oiho˙’ i sinh viˆenpha˙’ i c´onh˜ung k˜ynˇanglˆa.p tr`ınhtˆo´t. . . . . Gi´aotr`ınhbao gˆo`mba˙’ y chuong v`amˆo.t phˆa`n phu. lu.cv´oinh˜ung nˆo.i dung ch´ınh nhu. sau: . . . . • Chuong th´u nhˆa´t tr`ınhb`aynh˜ung kh´ainiˆe.m cˇanba˙’ nvˆe` d¯` ˆo thi . . . . . • Chuong 2 tr`ınhb`aynh˜ung sˆo´ co ba˙’ ncu˙’ ad¯ˆo` thi Y´ ngh˜ıa thu. ctiˆe˜ncu˙’ a c´acsˆo´ n`ay. • Chu.o.ng 3 t`ımhiˆe˙’u b`aito´ant`ımd¯u.`o .ng d¯ingˇa´n nhˆa´t. . . . . • Chuong4d¯ˆe` cˆa.pd¯ˆe´n kh´ainiˆe.mvˆe` cˆay. U´ ng du.ng cu˙’ a cˆayHuﬀman trong n´en d˜u . liˆe.u. Ngo`aira xˆaydu. ng c´acthuˆa.t to´ant`ımcˆaybao tr`um nho˙’ nhˆa´t. . . . . • B`aito´anEuler v`ab`aito´anHamilton v`anh˜ung mo˙’ rˆo.ng cu˙’ ach´ung s˜ed¯uo.c n´oi d¯ ˆe´n trong Chu.o.ng 5. . . . • Chuong 6 nghiˆenc´uu c´act´ınhchˆa´t phˇa˙’ ng cu˙’ ad¯ˆo` thi.; v`acuˆo´ic`ung . . • Chuong 7 t`ımhiˆe˙’u c´acb`aito´antrˆenma.ng vˆa.nta˙’ i. . . Ngo`aira, phˆa`n phu. lu.c tr`ınhb`ayc´accˆa´utr´uc d˜u liˆe.uv`anh˜ung thu˙’ tu.ccˆa`n thiˆe´t . . . . . d¯ ˆe ˙’ d¯ o n gia˙’ n ho´ac´acd¯oa.n chuong tr`ınhminh ho.a c´acthuˆa.t to´and¯uo. c tr`ınhb`ay. . . Gi´aotr`ınhd¯uo.cbiˆen soa.nlˆa`nd¯ˆa`u tiˆennˆenkhˆongtr´anhkho˙’ i kh´anhiˆe` u thiˆe´u s´ot. . . T´acgia˙’ mong c´onh˜ung d¯´ongg´opt`u ba.nd¯o.c. . . . . . . . . Tˆoixin ca˙’ monnh˜ung gi´up d¯˜o d¯˜anhˆa.nd¯uo. ct`u nhiˆe` u ngu`oi m`akhˆongthˆe˙’ liˆe.t kˆehˆe´t, d¯ˇa.cbiˆe.t l`ac´acba.n sinh viˆen, trong qu´atr`ınhbiˆen soa.n gi´aotr`ınhn`ay. D- `aLa.t, ng`ay17 th´ang4 nˇam2009 . PHA. MTiˆe´nSon 8
Chu.o.ng 1 . . D- a.icuong vˆ`e d¯` ˆo thi. 1.1 D- .inh ngh˜ıav`ac´ac kh´ai niˆe.m . . 1.1.1 D- `ˆo thi. c´ohu´ong . . . D- `ˆo thi. c´ohu´o ng G =(V,E)gˆo`mmˆo.ttˆa.p V c´acphˆa`ntu˙’ go.il`ad¯ ı ˙’ nh (hay n´ut) v`amˆo.t . . . . . . tˆa.p E c´ac cung sao cho mˆo˜i cung e ∈ E tuong ´ung v´oimˆo.tcˇa.p c´acd¯ı˙’ nh d¯uo. csˇa´p . . . . . . . . . th´u tu. .Nˆe´uc´od¯´ung mˆo.t cung e tuong ´ung c´acd¯ı˙’ nh d¯uo. csˇa´pth´u tu. (a, b), ta s˜eviˆe´t e := (a, b). . . . Ch´ung ta s˜egia˙’ su˙’ c´acd¯ı˙’ nh d¯uo. c d¯´anhsˆo´ l`a v1,v2, ,vn hay gia˙’ ntiˆe.n, 1, 2, ,n, trong d¯´o n =#V l`asˆo´ c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi . . . . . . . Nˆe´u e l`amˆo.t cung tuong ´ung cˇa.p c´acd¯ı˙’ nh d¯uo. csˇa´pth´u tu. vi v`a vj th`ıd¯ı˙’ nh vi go.il`agˆo´c v`ad¯ı˙’ nh vj go.il`ango.n; cung e go.il`aliˆenthuˆo.c hai d¯ı˙’ nh vi v`a vj. Ch´ung ta . . . . . . s˜ethu`ong k´yhiˆe.u m =#E l`asˆo´ cung cu˙’ ad¯ˆo` thi. G. C´accung thu`ong d¯uo.c d¯´anhsˆo´ l`a e1,e2, ,em. . . . . . Mˆo.t c´ach h`ınhho.c, c´acd¯ı˙’ nh d¯uo. cbiˆe˙’udiˆe˜nbo˙’ i c´acd¯iˆe˙’m, v`acung e d¯ u o. cbiˆe˙’u . . diˆe˜nbo˙’ imˆo.tm˜ui tˆent`u d¯ i ˆe ˙’m vi d¯ ˆe´nd¯iˆe˙’m vj. . Mˆo.t cung c´ogˆo´ctr`ung v´oi ngo.ngo.il`akhuyˆen. 9
. . Nˆe´u c´onhiˆe` uhonmˆo.t cung v´oigˆo´cta.i vi v`ango.nta.i vj th`ı G go.il`ad¯ad¯ˆo` thi. . . . . . . v`ac´accung tuong ´ung go.il`asong song. D- ond¯ˆo` thi. c´ohu´ong l`ad¯ˆo` thi. khˆongkhuyˆen trong d¯´ohai d¯ı˙’ nh bˆa´tk`y vi v`a vj c´onhiˆ`eu nhˆa´tmˆo.t cung nˆo´ich´ung. - V´ı du. 1.1.1. D`ˆo thi. trong H`ınh 1.1 c´ocung e8 l`akhuyˆen;c´accung e4 v`a e9 l`asong . . . song do c`ung tuong ´ung cˇa.pd¯ı˙’ nh v3 v`a v4. Cung e5 liˆenthuˆo.c c´acd¯ı˙’ nh v1 v`a v5. e4 . v2 e3 v3 ••. • v 4 . . . . . . . . . . . e9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e1 . . e2 e6 . e7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . 5 . • . • v. 5 v1 . . . . . . e8 . . H`ınh 1.1: V´ıdu. cu˙’ ad¯ˆo` thi. c´ohu´o ng. 1.1.2 D- `ˆo thi. v`a´anhxa. d¯atri. . . V´oimˆo˜i x ∈ V, k´yhiˆe.uΓ(x) l`atˆa.p c´acd¯ı˙’ nh y ∈ V sao cho tˆo`nta.i cung v´oigˆo´cl`ad¯ı˙’ nh − x v`ango.n l`ad¯ı˙’ nh y. Khi d¯´ota c´omˆo.t ´anhxa. d¯atri. Γ: V → 2V ,x7→ Γ(x). K´yhiˆe.uΓ 1 . . l`a´anhxa. (d¯atri.) nguo. ccu˙’ aΓ. . . . . Nˆe´u G l`ad¯ond¯ˆo` thi.,th`ıd¯ˆo` thi. n`ayho`anto`and¯uo. c x´acd¯i.nh bo˙’ itˆa.p V v`a´anh . V . . . xa. d¯atri. Γt`u V v`ao2 ; trong tru`ong ho. p n`ayta c´othˆe˙’ k´yhiˆe.u G =(V,Γ). . . . . . V´ı du. 1.1.2. Nˆe´u x´oacung e9 trong H`ınh 1.1 ta nhˆa.nd¯uo. cd¯ond¯ˆo` thi. c´ohu´ong v`a . do d¯´oc´othˆe˙’ biˆe˙’udiˆe˜nbo˙’ i ´anhxa. d¯atri. Γ: Γ(v1)={v2}, Γ(v2)={v1,v3}, Γ(v3)={v4,v5}, Γ(v4)={v5}, Γ(v5)={v1,v5}. 10
. . 1.1.3 D- `ˆo thi. vˆohu´ong . Khi nghiˆenc´uumˆo.tsˆo´ t´ınhchˆa´tcu˙’ a c´acd¯ˆo` thi., ta thˆa´yrˇa`ng ch´ung khˆongphu. thuˆo.c . . . . . v`aohu´ong cu˙’ a c´accung, t´uc l`akhˆongcˆa`n phˆanbiˆe.tsu. kh´acnhau gi˜ua c´acd¯iˆe˙’mbˇa´t . . d¯` ˆa uv`akˆe´tth´uc. D- iˆe` u n`ayd¯on gia˙’ n l`amˆo˜i khi c´o´ıtnhˆa´tmˆo.t cung gi˜ua hai d¯ı˙’ nh ta . . khˆongquan tˆamd¯ˆe´nth´u tu. cu˙’ ach´ung. . . . . . . . . V´oimˆo˜i cung, t´uc l`amˆo˜icˇa.p c´oth´u tu. (vi,vj) ta cho tuong ´ung cˇa.p khˆongc´oth´u . . . . . . . tu. (vi,vj)go.i l`ac´ac ca.nh. Tu ong d¯uong, ta n´oirˇa`ng ca.nh l`amˆo.t cung m`ahu´ong d¯˜a . . . bi. bo˙’ quˆen. Vˆ`e h`ınhho.c, ca.nh (vi,vj)d¯uo. cbiˆe˙’udiˆe˜nbo˙’ i c´acd¯oa.n thˇa˙’ ng (hoˇa.c cong) . . . v`akhˆongc´om˜ui tˆenliˆen thuˆo.c hai d¯iˆe˙’mtuong ´ung hai d¯ı˙’ nh vi v`a vj. . . . . Nghiˆen c´uu c´act´ınhchˆa´t vˆohu´ong cu˙’ ad¯ˆo` thi. G =(V,E)d¯uavˆe` kha˙’ o s´attˆa.p E . . . . l`atˆa.p c´ac ca.nh, t´uc l`a,mˆo.ttˆa.ph˜uuha.n c´acphˆa`ntu˙’ m`amˆo˜i phˆa`ntu˙’ l`amˆo.tcˇa.p hai d¯ ı ˙’ nh phˆanbiˆe.thayd¯ˆo`ng nhˆa´tcu˙’ a V. . . . D- ad¯ˆo` thi. vˆohu´ong l`ad¯ˆo` thi. m`ac´othˆe˙’ c´onhiˆe` uhonmˆo.tca.nh liˆenthuˆo.c hai d¯ı˙’ nh. . D- `ˆo thi. go.il`ad¯ o n nˆe´u n´okhˆongc´okhuyˆen v`ahai d¯ı˙’ nh bˆa´tk`y c´onhiˆ`eu nhˆa´tmˆo.t ca.nh liˆenthuˆo.cch´ung. . . . V´ı du. 1.1.3. H`ınh 1.2 l`ad¯ˆo` thi. vˆohu´o ng c´o5 d¯ı˙’ nh v`a9 ca.nh. Ca.nh e1 song song v´oi ca.nh e2. Ca.nh e8 l`akhuyˆen. 1.1.4 C´acd¯i.nh ngh˜ıa Hai cung, hoˇa.c hai ca.nh go.il`akˆ`e nhau nˆe´uch´ung c´o´ıtnhˆa´tmˆo.td¯ı˙’ nh chung. Chˇa˙’ ng ha.n, hai ca.nh e1 v`a e3 trong H`ınh 1.2 l`akˆe` nhau. Hai d¯ı˙’ nh vi v`a vj go.il`akˆ`e nhau nˆe´u tˆo`nta.ica.nh hoˇa.c cung ek liˆenthuˆo.cch´ung. V´ıdu. trong H`ınh 1.2 hai d¯ı˙’ nh v2 v`a v3 l`a . . kˆ`e nhau (liˆenthuˆo.cbo˙’ ica.nh e3), nhung d¯ı˙’ nh v2 v`a v5 khˆongkˆ`e nhau. 11
e4 v2 e3 v3 •• • v 4 . . . . . . . . . . . . e9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . . e e . e 1 . . 2 6 . 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . 5 . • • v5 v1 . . . . . . . . . e8 . . . . . H`ınh 1.2: D- `ˆo thi. vˆohu´ong tuong ´ung d¯ˆo` thi. trong H`ınh 1.1. Bˆa.c + + . Bˆa.c ngo`ai cu˙’ ad¯ı˙’ nh v ∈ V, k´yhiˆe.u dG(v) (hay d (v)nˆe´u khˆongso. nhˆa`mlˆa˜n) l`asˆo´ c´ac − − cung c´od¯ı˙’ nh v l`agˆo´c. Bˆa.c trong cu˙’ ad¯ı˙’ nh v ∈ V, k´yhiˆe.u dG(v) (hay d (v)nˆe´u khˆong . so. nhˆa`mlˆa˜n) l`asˆo´ c´accung c´od¯ı˙’ nh v l`ango.n. . . + − Chˇa˙’ ng ha.n, d¯ˆo` thi. c´ohu´ong trong H`ınh 1.1 c´o d (v2)=2,d (v2)=1. Hiˆe˙’n nhiˆenrˇa`ng, tˆo˙’ng c´acbˆa.c ngo`aicu˙’ a c´acd¯ı˙’ nh bˇa`ng tˆo˙’ng c´acbˆa.c trong cu˙’ a c´ac . d¯ ı ˙’ nh v`abˇa`ng tˆo˙’ng sˆo´ cung cu˙’ ad¯ˆo` thi. G, t´ucl`a n n + − X d (vi)=X d (vi)=m. i=1 i=1 . . Nˆe´u G l`ad¯ˆo` thi. vˆohu´o ng, bˆa.c cu˙’ ad¯ı˙’ nh v ∈ V, k´yhiˆe.u dG(v) (hay d(v)nˆe´u khˆong . . . . so. nhˆa`mlˆa˜n) l`asˆo´ c´acca.nh liˆenthuˆo.cd¯ı˙’ nh v v´oi khuyˆend¯uo. cd¯ˆe´m hai lˆa`n. V´ıdu. d¯` ˆo . . thi. vˆohu´ong trong H`ınh 1.2 c´o d(v2)=3,d(v5)=5. 12
C´accung (ca.nh) liˆenthuˆo. ctˆa.p A ⊂ V. D- ˆo´ichutr`ınh . + Gia˙’ su˙’ A ⊂ V. K´yhiˆe.u ω (A) l`atˆa.ptˆa´tca˙’ c´accung c´od¯ı˙’ nh gˆo´c thuˆo.c A v`ad¯ı˙’ nh ngo.n − thuˆo.c Ac := V \ A, v`a ω (A) l`atˆa.ptˆa´tca˙’ c´accung c´od¯ı˙’ nh ngo.n thuˆo.c A v`ad¯ı˙’ nh gˆo´c thuˆo.c Ac. D- ˇa.t ω(A)=ω+(A) ∪ ω−(A). Tˆa.p c´accung hoˇa.cca.nh c´oda.ng ω(A)go.il`ad¯ ˆo´i chu tr`ınh cu˙’ ad¯ˆo` thi D- `ˆo thi. c´otro.ng sˆo´ . . . . D- `ˆo thi. c´otro. ng sˆo´ nˆe´u trˆenmˆo˜i cung (hoˇa.cca.nh) e ∈ E c´otuong ´ung mˆo.tsˆo´ thu. c w(e) . . go.i l`atro.ng luo. ng cu˙’ a cung e. . D- `ˆo thi. d¯ ˆo´ix´ung . . . D- `ˆo thi. c´ohu´ong go.il`ad¯ ˆo´ix´ung nˆe´u c´obao nhiˆeucung da.ng (vi,vj)th`ıc˜ung c´obˆa´y nhiˆeucung da.ng (vj,vi). . D- `ˆo thi. pha˙’ nd¯ˆo´ix´ung . . . D- `ˆo thi. c´ohu´ong go.il`apha˙’ nd¯ˆo´ix´ung nˆe´u c´ocung da.ng (vi,vj)th`ı khˆongc´ocung da.ng (vj,vi). D- `ˆo thi. d¯` ˆa yd¯u˙’ . . D- `ˆo thi. vˆohu´ong go.il`ad¯` ˆa yd¯u˙’ nˆe´u hai d¯ı˙’ nh bˆa´tk`y vi v`a vj tˆo`nta.imˆo.tca.nh da.ng . . . . . (vi,vj). D- ond¯ˆo` thi. vˆohu´o ng d¯ˆa`yd¯u˙’ n d¯ ı ˙’ nh d¯uo. ck´yhiˆe.ul`aKn. 13
D- `ˆo thi. con . . . . Gia˙’ su˙’ A ⊂ V. D- `ˆo thi. con d¯ u o. c sinh bo˙’ itˆa.p A l`ad¯ˆo` thi. GA := (A, EA) trong d¯´oc´ac . d¯ ı ˙’ nh l`ac´acphˆa`ntu˙’ cu˙’ atˆa.p A v`ac´accung trong EA l`ac´accung cu˙’ a G m`ahai d¯ı˙’ nh n´o liˆenthuˆo.c thuˆo.ctˆa.p A. . . Nˆe´u G l`ad¯ˆo` thi. biˆe˙’udiˆe˜nba˙’ nd¯ˆo` giao thˆongcu˙’ anu´ocViˆe.t Nam th`ıd¯ˆo` thi. biˆe˙’u diˆe˜nba˙’ nd¯ˆo` giao thˆongcu˙’ a th`anhphˆo´ D- `aLa.t l`amˆo.td¯ˆo` thi. con. D- `ˆo thi. bˆo. phˆa.n . . X´et d¯ˆo` thi. G =(V,E)v`aU ⊂ E. D- `ˆo thi. bˆo. phˆa. n sinh bo˙’ i tˆa.p U l`ad¯ˆo` thi. v´oitˆa.pd¯ı˙’ nh V v`ac´accung thuˆo.c U (c´accung cu˙’ a E \ U bi. x´oakho˙’ i G). D- `ˆo thi. con bˆo. phˆa.n . X´et d¯ˆo` thi. G =(V,E)v`aA ⊂ V,U ⊂ E. D- `ˆo thi. con bˆo. phˆa.n sinh bo˙’ itˆa.p A v`a U l`ad¯ˆo` . thi. bˆo. phˆa.ncu˙’ a GA sinh bo˙’ i U. 1.2 Ma trˆa. nbiˆe˙’ udiˆ˜end¯ˆo` thi. 1.2.1 Ma trˆa. n liˆenthuˆo. cd¯ı˙’ nh-cung Ma trˆa. n liˆenthuˆo.cd¯ı˙’ nh-cung cu˙’ ad¯ˆo` thi. G =(V,E) l`ama trˆa.n A =(aij),i = . . 1, 2, ,n,j =1, 2, ,m, v´oi c´acphˆa`ntu˙’ 0, 1v`a−1, trong d¯´omˆo˜icˆo.tbiˆe˙’udiˆ˜en . mˆo.t cung v`amˆo˜i h`angbiˆe˙’udiˆe˜nmˆo.td¯ı˙’ nh. Nˆe´u ek =(vi,vj) ∈ E th`ıtˆa´tca˙’ c´acphˆa`ntu˙’ . cu˙’ acˆo.t k bˇa`ng khˆongngoa.itr`u aik =1,ajk = −1. 14
a e1 b •• . . . . . . . . e4 . . . . . . . . e3 . . . . . . . . . e . 2 . . . . . . •• d e5 c H`ınh 1.3: V´ı du. 1.2.1. Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung cu˙’ ad¯ˆo` thi. trong H`ınh 1.3 l`a e1 e2 e3 e4 e5 a +1 +1 0 0 0  b −1 0 +1 +1 0   .  − −  c 0 1 10+1 d 000−1 −1  . Nhˇa´cla.irˇa`ng, ma trˆa.n vuˆonggo.il`aunimodular nˆe´ud¯i.nh th´uccu˙’ an´obˇa`ng 1 hoˇa.c −1. Ma trˆa.n A cˆa´p m × n go.il`aunimodular ho`anto`an nˆe´utˆa´tca˙’ c´acma trˆa.n vuˆong con khˆongsuy biˆe´ncu˙’ a A l`aunimodular. Mˆe.nh d¯ˆ`e 1.2.2. Ma trˆa. n liˆenthuˆo. cd¯ı˙’ nh-cung cu˙’ ad¯ˆo` thi. G =(V,E) l`aunimodular ho`anto`an. . . Ch´ung minh. Ch´u´yrˇa`ng ma trˆa.nliˆen thuˆo.cd¯ı˙’ nh-cung cu˙’ ad¯ˆo` thi. G =(V,E)ch´ua . d¯ung ´ hai phˆa`ntu˙’ kh´ackhˆongtrˆenmˆo˜icˆo.t, mˆo.tbˇa`ng 1 v`amˆo.tbˇa`ng −1. Do d¯´ota c´o . . thˆe˙’ ch´ung minh theo quy na.pnhusau: Hiˆe˙’n nhiˆen,tˆa´tca˙’ c´acma trˆa.n vuˆongcon khˆong . suy biˆe´ncˆa´p1cu˙’ a A l`amodular; gia˙’ su˙’ khˇa˙’ ng d¯i.nh d¯´ung cho mo.i ma trˆa.n con khˆong suy biˆe´ncˆa´p(k − 1). 0 0 . X´et ma trˆa.n vuˆongcon A cˆa´p k cu˙’ a A. Nˆe´umˆo˜icˆo.tcu˙’ a A ch´uad¯´ung hai phˆa`n . 0 0 tu˙’ kh´ackhˆongth`ıdet(A ) = 0 (thˆa.tvˆa.y, tˆo˙’ng tˆa´tca˙’ c´ach`angcu˙’ a A l`avector khˆong, 15
a e1 b •• . . . . . . e . 4 . . . . . . . . . e . 3 . . . . . . . e . 2 . . . . . •• d e5 c H`ınh 1.4: 0 . do d¯´oc´ach`angl`ad¯ˆo.clˆa.p tuyˆe´n t´ınh). Nˆe´utˆo`nta.imˆo.tcˆo.tcu˙’ a A khˆongc´ophˆa`ntu˙’ 0 0 kh´ackhˆongth`ıdet(A )=0. Cuˆo´ic`ung, nˆe´utˆo`nta.icˆo.t j cu˙’ a A sao cho c´od¯´ung mˆo.t . 0 00 00 phˆa`ntu˙’ kh´ackhˆong aij (bˇa`ng 1, hay −1) th`ıdet(A )=± det(A ), trong d¯´o A l`ama . . . 0 trˆa.n vuˆongcˆa´p(k − 1) nhˆa.nd¯uo. ct`u A bˇa`ng c´ach x´oah`ang i v`acˆo.t j. Theo gia˙’ thiˆe´t 0 . . . quy na.p, det(A )bˇa`ng 1, −1 hay 0 v`ado d¯´omˆe.nh d¯ˆ`e d¯ u o. cch´ung minh. / 1.2.2 Ma trˆa. n liˆenthuˆo. cd¯ı˙’ nh-ca. nh . . X´et d¯ˆo` thi. vˆohu´ong G =(V,E). Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh cu˙’ ad¯ˆo` thi. G l`ama trˆa.n . . A =(aij),i=1, 2, ,n,j =1, 2, ,m, v´oi c´acphˆa`ntu˙’ 0v`a1, trong d¯´omˆo˜icˆo.tbiˆe˙’u diˆe˜nmˆo.tca.nh v`amˆo˜i h`angbiˆe˙’udiˆe˜nmˆo.td¯ı˙’ nh; ngo`aira, nˆe´uca.nh ek liˆenthuˆo.c hai . . d¯ ı ˙’ nh vi v`a vj th`ıtˆa´tca˙’ c´acphˆa`ntu˙’ cu˙’ acˆo.t k bˇa`ng khˆongngoa. itr`u aik =1,ajk =1. V´ı du. 1.2.3. Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh cu˙’ ad¯ˆo` thi. trong H`ınh 1.4 l`a e1 e2 e3 e4 e5 a 11000 b 10110     c 01101 d 00011 . Tr´aiv´oi ma trˆa.nliˆen thuˆo.cd¯ı˙’ nh-cung, n´oichung ma trˆa.nliˆen thuˆo.cd¯ı˙’ nh-ca.nh 16
khˆongunimodular ho`anto`an.Chˇa˙’ ng ha.n, trong v´ıdu. trˆen,ma trˆa.n con 110 101   011 . c´od¯i.nh th´ucbˇa`ng −2. . . D- `ˆo thi. vˆohu´o ng G =(V,E)go.il`ahai phˆa`n nˆe´u c´othˆe˙’ phˆanhoa.ch tˆa.p c´acd¯ı˙’ nh . . V th`anhhai tˆa.p con r`oi nhau V1 v`a V2 sao cho d¯ˆo´iv´oimˆo˜ica.nh (vi,vj) ∈ E th`ıhoˇa.c vi ∈ V1,vj ∈ V2 hoˇa.c vj ∈ V1,vi ∈ V2. V´ı du. 1.2.4. Dˆ˜e kiˆe˙’m tra d¯ˆo` thi. K2,3 trong H`ınh 1.5 l`ahai phˆa`n. a b •• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ••• c d e H`ınh 1.5: D- `ˆo thi. hai phˆa`n K2,3. . . Mˆe.nh d¯ˆ`e 1.2.5. Ma trˆa. nliˆen thuˆo. cd¯ı˙’ nh-ca. nh cu˙’ ad¯ˆo` thi. vˆohu´o ng G =(V,E) l`a unimodular ho`anto`annˆe´u v`achı˙’ nˆe´u G l`ad¯ˆo` thi. hai phˆa`n. . . . Ch´ung minh. D- iˆe` ukiˆe. nd¯u˙’ . Gia˙’ su˙’ G l`ad¯ˆo` thi. hai phˆa`n. Ta s˜ech´ung minh theo quy . na.prˇa`ng mo.i ma trˆa.n vuˆongcon B cu˙’ a ma trˆa.nliˆen thuˆo.cd¯ı˙’ nh-ca.nh c´od¯i.nh th´uc . . det(B)=0, 1 hoˇa.c −1. D- iˆe` un`ayd¯´ung v´oi c´acma trˆa.n vuˆongcon cˆa´p 1; gia˙’ su˙’ khˇa˙’ ng . d¯ i .nh d¯´ung v´oi c´acma trˆa.n vuˆongcon cˆa´p(k − 1). X´et ma trˆa.n vuˆongcon B cˆa´p k. j . . Nˆe´umˆo˜icˆo.t B cu˙’ a B ch´uad¯´ung hai phˆa`ntu˙’ bˇa`ng 1 th`ı X Bi = X Bi, i∈I1 i∈I2 . . . trong d¯´o I1 v`a I2 l`ac´actˆa.pchı˙’ sˆo´ tuong ´ung hai phˆanhoa.ch cu˙’ atˆa.p c´acd¯ı˙’ nh V v`a Bi l`avector h`angcu˙’ a B. C´acvector h`angphu. thuˆo.c tuyˆe´n t´ınh,nˆendet(B)=0. 17
. . . Nguo.cla.i, nˆe´utˆo`nta.icˆo.tc´od¯´ung mˆo.t phˆa`ntu˙’ bˇa`ng 1, chˇa˙’ ng ha.n bij =1, th`ı bˇa`ng quy na.p ta c´o det(B)=± det(C)(=0, 1 hoˇa.c − 1, . . . trong d¯´o C l`ama trˆa.n nhˆa.nd¯uo. ct`u B bˇa`ng c´ach x´oah`ang i v`acˆo.t j. . D- iˆe` ukiˆe. ncˆa`n. Dˆ˜e d`angch´ung minh rˇa`ng ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh cu˙’ ad¯ˆo` thi. l`a . . mˆo.t chu tr`ınhd¯ˆo. d`aile˙’ (t´uc l`asˆo´ ca.nh trˆenchu tr`ınhl`ale˙’ -xem Phˆa`n 1.3) c´od¯i.nh th´uc . bˇa`ng ±2. Do d¯´o G khˆongch´ua chu tr`ınhd¯ˆo. d`aile˙’ v`av`ıvˆa.y n´ol`ahai phˆa`n theo bˆo˙’ d¯` ˆe sau. / . . . Bˆo˙’ d¯` ˆe 1.2.6. D- `ˆo thi. vˆohu´ong G l`ahai phˆa`nnˆe´u v`achı˙’ nˆe´u G khˆongch´ua chu tr`ınh c´od¯ˆo. d`aile˙’ . . . . Ch´ung minh. D- iˆe` ukiˆe.ncˆa`n. Do V d¯ u o. c phˆanhoa.ch th`anh V1 v`a V2 : V = V2 ∪ V2,V1 ∩ V2 = ∅. Gia˙’ thiˆe´ttˆo`nta.imˆo.t chu tr`ınhc´od¯ˆo. d`aile˙’ µ = {vi1 ,vi2 , ,viq ,vi1 } ˙’ v`akhˆongmˆa´t t´ınhtˆong qu´at,lˆa´y vi1 ∈ V1. Do G l`ahai phˆa`n, nˆenhai d¯ı˙’ nh liˆentiˆe´p trˆen chu tr`ınh µ pha˙’ i c´omˆo.td¯ı˙’ nh thuˆo.c V1 v`ad¯ı˙’ nh kia thuˆo.c V2. Do d¯´o vi2 ∈ V2,vi3 ∈ V1, , ˙’ ∈ ´ ∈ ´ ˜ v`atˆong qu´at, vik V1 nˆeu k le˙’ v`a vik V2 nˆeu k chˇan. M`achu tr`ınh µ c´od¯ˆo. d`aile˙’ nˆen . - ` ˜ . viq ∈ V1 v`abo˙’ ivˆa.y vi1 ∈ V2. Diˆeu n`aymˆauthuˆanv´oi V1 ∩ V2 = ∅. . D- iˆe` ukiˆe.nd¯u˙’ . Khˆongmˆa´t t´ınhtˆo˙’ng qu´atgia˙’ thiˆe´td¯ˆo` thi. G liˆenthˆong.Gia˙’ su˙’ khˆong tˆo`nta.i chu tr`ınhc´od¯ˆo. d`aile˙’ . Cho.nd¯ı˙’ nh bˆa´tk`y, chˇa˙’ ng ha.n vi v`ag´annh˜ancho n´ol`a“ + ”. Sau d¯´olˇa.pla.i c´ac ph´epto´ansau: . . . . . Cho.nd¯ı˙’ nh d¯˜ad¯uo. c g´annh˜an vj v`ag´annh˜annguo. cv´oi nh˜ancu˙’ a vj cho tˆa´tca˙’ . c´acd¯ı˙’ nh kˆe` v´oid¯ı˙’ nh vj. . . . Tiˆe´ptu.c qu´atr`ınhn`aycho d¯ˆe´n khi xa˙’ y ra mˆo.t trong hai tru`ong ho. p: 18
. . (a) Tˆa´tca˙’ c´acd¯ı˙’ nh d¯˜ad¯uo. c g´annh˜anv`ahai d¯ı˙’ nh bˆa´tk`ykˆe` nhau c´onh˜ankh´acnhau (mˆo.t mang dˆa´u+v`amˆo.t mang dˆa´u −); hoˇa.c ` ˙’ . . (b) Tˆonta.id¯ı˙’ nh, chˇang ha.n vjk , d¯ u o. c g´anhai nh˜ankh´acnhau. . . . . . Trong Tru`ong ho. p (a), d¯ˇa.t V1 l`atˆa.ptˆa´tca˙’ c´acd¯ı˙’ nh d¯uo. c g´annh˜an“+” v`a V2 l`atˆa.p . . . tˆa´tca˙’ c´acd¯ı˙’ nh d¯uo. c g´annh˜an“−”. Do tˆa´tca˙’ c´acca.nh liˆenthuˆo.cgi˜ua c´accˇa.pd¯ı˙’ nh c´onh˜ankh´acnhau nˆen d¯ˆo` thi. G l`ahai phˆa`n. . . . . . ` Trong Tru`ong ho. p (b), d¯ı˙’ nh vjk d¯ u o. c g´annh˜an“+” do.c theo mˆo.t dˆaychuyˆen µ1 . . . . n`aod¯´o,v´oi c´acd¯ı˙’ nh d¯uo. c g´annh˜an“+” v`a“−” xen k˜enhau xuˆa´t ph´att`u vi v`akˆe´t . . . . . − ` th´uc ta.i vjk . Tu ong tu. ,d¯ı˙’ nh vjk d¯ u o. c g´annh˜an“ ”do.c theo mˆo.t dˆaychuyˆen µ2 n`ao . . . . d¯´o,v´oi c´acd¯ı˙’ nh d¯uo.c g´annh˜an“+” v`a“−”xenk˜e nhau xuˆa´t ph´att`u vi v`akˆe´tth´uc . . ´ . ´ . . ta.i vjk . Nhung nhu thˆe chu tr`ınhd¯ido.c theo µ1 t`u d¯ ı ˙’ nh vi d¯ ˆe nd¯ı˙’ nh vjk sau d¯´od¯inguo. c . la.ido.c theo µ2 vˆ`e la.i vi c´od¯ˆo. d`aile˙’ .D- iˆe` u n`aymˆauthuˆa˜nv´oi gia˙’ thiˆe´t, v`ado d¯´okhˆong . . . . . . thˆe˙’ xa˙’ y ra Tru`ong ho. p (b). D- .inh l´yd¯uo. cch´ung minh. / 1.2.3 Ma trˆa. nkˆe` . Gia˙’ su˙’ G =(V,E) l`ad¯ˆo` thi. sao cho c´onhiˆ`eu nhˆa´tmˆo.t cung liˆenthuˆo.c hai d¯ı˙’ nh bˆa´tk`y vi v`a vj. Ma trˆa.nkˆe` hay ma trˆa. n liˆenthuˆo.cd¯ı˙’ nh-d¯ı˙’ nh l`ama trˆa.n vuˆong A =(aij)cˆa´p . . n × n v´oi c´acphˆa`ntu˙’ 0 hoˇa.c1: ( 1nˆe´u(vi,vj) ∈ E, aij := . . 0nˆe´u nguo. cla.i. V´ı du. 1.2.7. D- `ˆo thi. G trong H`ınh 1.6 c´oma trˆa.nkˆe` l`a 01100 11111   A(G)=11011 .     01100   01100 . T`u d¯ i .nh ngh˜ıa,dˆe˜ d`angsuy ra 19
. . . b a •. • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . . d . ce•• H`ınh 1.6: . . . T´ınh chˆa´t 1.2.8. Gia˙’ su˙’ A =(aij)n×n l`ama trˆa. nkˆe` cu˙’ ad¯ˆo` thi. vˆohu´ong G. Khi d¯´o (a) aii =1nˆe´u v`achı˙’ nˆe´u G c´okhuyˆen ta. id¯ı˙’ nh i. . (b) A l`ama trˆa. nd¯ˆo´ix´ung. (c) Nˆe´u G khˆongkhuyˆen (v`akhˆongc´oca. nh song song) th`ıbˆa. ccu˙’ amˆo. td¯ı˙’ nh bˇa`ng sˆo´ . . . c´acsˆo´ 1 trong h`anghay cˆo. ttuong ´ung. . . . . . . . . (d) Ho´anvi. c´ach`angv`ac´accˆo. ttuong ´ung tuong d¯uong v´oiviˆe. c d¯´anhsˆo´ la. i c´acd¯ı˙’ nh. . . Tuy nhiˆencˆa`nch´u´yrˇa`ng, c´ach`angv`ac´accˆo. tcˆa`nd¯uo. csˇa´pxˆe´p theo c`ung mˆo. t . . . . . th´u tu. . Do d¯´onˆe´u hai h`angthay d¯ˆo˙’ith`ı hai cˆo. ttuong ´ung c˜ung cˆa`n pha˙’ i thay d¯ ˆo ˙’i. . . . . . . . . Trong tru`ong ho. pd¯ˆo` thi. vˆohu´o ng, ma trˆa.nkˆe` cu˙’ ad¯ond¯ˆo` thi. c˜ung c´othˆe˙’ d¯ u o. c . . . d¯ i .nh ngh˜ıa bˇa`ng c´ach xem mˆo˜ica.nh (vi,vj)tuong ´ung hai cung (vi,vj)v`a(vj,vi). Trong . . . . tru`ong ho. p n`ay, ma trˆa.nkˆe` l`ad¯ˆo´ix´ung. . 1.2.4 C´accˆa´utr´ucd˜uliˆe.ubiˆe˙’ udiˆe˜nd¯ˆo` thi. . . D- ˆe ˙’ mˆota˙’ mˆo.td¯ˆo` thi., ta c´othˆe˙’ su˙’ du.ng mˆo.tsˆo´ c´ach biˆe˙’udiˆe˜n kh´acnhau. V´oi quan . . . . d¯ i ˆe ˙’mlˆa.p tr`ınh,n´oichung c´acbiˆe˙’udiˆe˜n n`aykhˆongtuong d¯uong theo kh´ıa ca.nh hiˆe.u qua˙’ cu˙’ a thuˆa.t to´an. . . C´ohai c´ach biˆe˙’udiˆe˜nch´ınh: Th´u nhˆa´t, su˙’ du.ng ma trˆa.nkˆe` hoˇa.c c´acdˆa˜n xuˆa´t . . cu˙’ a n´o;th´u hai, su˙’ du. ng ma trˆa.n liˆenthuˆo.c hoˇa.c c´acdˆa˜n xuˆa´tcu˙’ a n´o. 20
. Su˙’ du. ng ma trˆa.nkˆ`e Ch´ung ta biˆe´trˇa`ng c´acma trˆa.nkˆe` cho ph´ep miˆeuta˙’ c´acd¯ˆo` thi. khˆongc´oca.nh (cung) . . . song song. V´oi c´ach biˆe˙’udiˆe˜nd¯ˆo` thi. qua ma trˆa.nkˆe` , ta thˆa´ysˆo´ luo. ng thˆongtin, gˆo`m . . 2 . . . . c´acbit 0 v`a1, cˆa`nluutr˜u l`a n . C´acbit c´othˆe˙’ d¯ u o. ckˆe´tho. p trong c´act`u.K´yhiˆe.u w . . . l`ad¯ˆo. d`aicu˙’ at`u (t´uc l`asˆo´ c´acbit trong mˆo.tt`u m´ayt´ınh). Khi d¯´omˆo˜i h`angcu˙’ ama . . . . 1 . . trˆa.nkˆe` c´othˆe˙’ d¯ u o. cviˆe´tnhumˆo.t d˜ay n bit trong dn/we t`u . Do d¯´osˆo´ c´act`u d¯ ˆe ˙’ luu . tr˜u ma trˆa.nkˆe` l`a ndn/we. . . . . . . Ma trˆa.nkˆe` cu˙’ ad¯ˆo` thi. vˆohu´ong l`ad¯ˆo´ix´ung, nˆenta chı˙’ cˆa`nluutr˜u nu˙’ a tam gi´ac trˆencu˙’ a n´o,v`ado d¯´ochı˙’ cˆa`n n(n − 1)/2 bit. Tuy nhiˆen, v´o.i c´ach lu.utr˜u. n`ay, s˜etˇang . . d¯ ˆo. ph´ucta.p v`ath`oi gian t´ınhto´antrong mˆo.tsˆo´ b`aito´an. . . . . 2 . ` . . 1 Trong tru`ong ho. p c´acma trˆa.nthua(m n v´oid¯ˆothi. c´ohu´o ng; m 2 n(n+1) . . . d¯ ˆo´iv´oid¯ˆo` thi. vˆohu´ong) c´ach biˆe˜udiˆe˜n n`ayl`al˜angph´ı. Do d¯´ota s˜et`ımc´ach biˆe˙’udiˆe˜n chı˙’ c´acphˆa`ntu˙’. kh´ackhˆong. . . . V`ımu.cd¯´ıch n`ayta s˜esu˙’ du.ng mˆo.t ma˙’ ng danh s´ach kˆe` cho d¯ˆo` thi. c´ohu´o ng. D- `ˆo . . . . . thi. c´ohu´o ng d¯uo. cbiˆe˙’udiˆe˜nbo˙’ imˆo.tma˙’ ng c´accon tro˙’ V out[1],V out[2], ,V out[n], . . . . . . . trong d¯´omˆo˜i con tro˙’ tuong ´ung v´oimˆo.td¯ı˙’ nh trong d¯ˆo` thi. c´ohu´ong. Mˆo˜i phˆa`ntu˙’ cu˙’ a . . . . . . ma˙’ ng V out[i]chı˙’ d¯ ˆe´nmˆo.tn´ut d¯ˆa`uluutr˜u mu.cd˜u liˆe.ucu˙’ an´ut tuong ´ung d¯ı˙’ nh vi v`a . . . . ch´uamˆo.t con tro˙’ chı˙’ d¯ ˆe´nmˆo.t danh s´ach liˆen kˆe´tcu˙’ a c´acd¯ı˙’ nh kˆe` (d¯ı˙’ nh d¯uo. cnˆo´iv´oi vi . . . . . theo hu´ong t`u vi ra). Mˆo˜in´ut kˆ`e c´ohai tru`ong: . . . . 1. Tru `o ng sˆo´ nguyˆen:luutr˜u sˆo´ hiˆe.ucu˙’ ad¯ı˙’ nh kˆe` ;v`a 2. Tru.`o .ng liˆenkˆe´t chı˙’ d¯ ˆe´nn´ut kˆe´ tiˆe´p trong danh s´ach kˆe` n`ay. . . C´ach biˆe˙’udiˆe˜nma˙’ ng danh s´ach kˆ`e V out[] cu˙’ ad¯ˆo` thi. c´ohu´o ng trong H`ınh1.7 . . . . . . . . . . d¯ u o.c cho tuong ´ung trong H`ınh 1.8 (gia˙’ su˙’ c´acmu.cd˜u liˆe.utuong ´ung c´acd¯ı˙’ nh theo . . th´u tu. l`a A,B,C,D,E,F). . Thay v`ı con tro˙’ chı˙’ d¯ ˆe´nmˆo.t danh s´ach c´acd¯ı˙’ nh t`u vi d¯ira trong V out[i], ta tro˙’ . . d¯ ˆe´n danh s´ach c´acd¯ı˙’ nh d¯ i d¯ ˆe´n vi v`ado d¯´oc´othˆe˙’ luutr˜u d¯` ˆo thi. thˆongqua ma˙’ ng c´ac 1 . K´yhiˆe.u dxe l`asˆo´ nguyˆennho˙’ nhˆa´t khˆongb´ehon x. 21
v1 v2 •• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v6 • . • . . . . . . . . . v3 . . . . . . . . . . . . . . . . . . . . . . . . . . • • v5 v4 H`ınh 1.7: N´ut d¯ˆa`u . . . . . . . . . . . . . . . V out[1] . • v4 . • v5 . • A . . . NULL . . . . . . . . . . . . . . . . . . V out[2] . • v1 . • v3 . • B . . . NULL . . . . . . . . . . . . . V out[3] . • v3 . • C . . NULL . . . . . . . . . . . . . . . . . V out[4] . • v2 . • v3 . • D . . . NULL . . . . . . . . . . . . . . . . . . V out[5] . • v3 . • v6 . • E . . . NULL . . . . . . . . . . . . . V out[6] . • v1 . • F . . NULL . . . . . H`ınh 1.8: Danh s´ach kˆe` V out[] tuong ´ung d¯ˆo` thi. trong H`ınh 1.7. danh s´ach kˆ`e V in[i]. H`ınh 1.9 minh ho.ama˙’ ng c´acdanh s´ach kˆe` V in[] cu˙’ ad¯ˆo` thi. c´o hu.´o.ng trong H`ınh 1.7. D- ˆe ˙’ yrˇa´ `ng, c´acsˆo´ trong n´ut kˆ`e cu˙’ a V out[] (tu.o.ng ´u.ng, V in[]) l`anh˜u.ng chı˙’ sˆo´ . . . . cˆo.t (tuong ´ung, h`ang)trong ma trˆa.nkˆe` cu˙’ ad¯ˆo` thi. m`ao˙’ d¯´osˆo´ 1 xuˆa´thiˆe.n. Ngo`aira, . . . . . trong tru`ong ho. pd¯ˆo` thi. vˆohu´ong, hai danh s´ach kˆe` n`ayl`atr`ung nhau. . . . Khi d¯ˆo` thi. c´o tro.ng sˆo´,t´ucl`anˆe´umˆo˜i cung hoˇa.cca.nh e ∈ E c´omˆo.t tro.ng luo. ng . w(e), ta chı˙’ cˆa`nmo˙’ rˆo.ng cˆa´utr´uc cu˙’ amˆo˜in´ut trong danh s´ach kˆe` bˇa`ng c´ach thˆemmˆo.t . . . . . . tru`ong luutr˜u tro.ng luo. ng cu˙’ a cung. . . . . C´ach biˆe˙’udiˆe˜nbˇa`ng danh s´ach kˆe` cu˙’ ad¯ˆo` thi. c´ohu´ong c´othˆe˙’ d¯ u o. c c`aid¯ˇa.t trong 22
. . . ngˆonng˜u lˆa.p tr`ınhC v´oi c´ackhai b´aotrong thu viˆe.n Graph.h (xem Phu. lu.c A). D- ˆe ˙’ . . xˆaydu. ng ma˙’ ng c´acdanh s´ach kˆ`e V out[] v`a V in[] cho mˆo.td¯ˆo` thi., ta c´othˆe˙’ su˙’ du. ng . . . c´acthu˙’ tu.c MakeV out() v`aMakeV in() tuong ´ung. N´ut d¯ˆa`u . . . . . . . . . . . . . . . . V in[1] . • v2 . • v6 . • A . . . NULL . . . . . . . . . . . . . . V in[2] . • v4 . • B . . NULL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V in[3] . • v2 . • v3 . • v4 . • v5 . • C . . . . . NULL . . . . . . . . . . . . . . . V in[4] . • v1 . • D . . NULL . . . . . . . . . . . . V in[5] . • v1 . • E . . NULL . . . . . . . . . . . . V in[6] . • v5 . • F . . NULL . . . . . H`ınh 1.9: Danh s´ach kˆ`e V in[] tuong ´ung d¯ˆo` thi. trong H`ınh 1.7. . Su˙’ du. ng c´acma trˆa.n liˆenthuˆo. cd¯ı˙’ nh-cung hoˇa.cd¯ı˙’ nh-ca.nh Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung hoˇa.cd¯ı˙’ nh-ca.nh cho ph´ep ch´ung ta mˆota˙’ d¯` ˆa yd¯u˙’ cˆa´utr´uc . cu˙’ amˆo.t d¯ a d¯` ˆo thi. khˆongc´okhuyˆen. Tuy nhiˆen,do chı˙’ c´ohai phˆa`ntu˙’ kh´ackhˆongtrong . . . mˆo˜icˆo.t, nˆen c´othˆe˙’ biˆe˙’udiˆe˜n thˆongtin o˙’ da.ng th´ıch ho. phon. . Ch´ung ta d¯i.nh ngh˜ıa hai ma˙’ ng tuyˆe´n t´ınh α[] v`a β[] chiˆe` u m trong d¯´ov´oimˆo˜i cung hoˇa.cca.nh ek,k =1, 2, ,m, c´acgi´atri. α[k]v`aβ[k] l`ac´acchı˙’ sˆo´ cu˙’ a c´acd¯ı˙’ nh . . . . . m`a ek liˆenthuˆo.c. Trong tru`o ng ho. pc´ohu´ong, ch´ung ta quyˆe´td¯i.nh α[k]l`ad¯ı˙’ nh gˆo´cv`a β[k] l`ad¯ı˙’ nh ngo.ncu˙’ a cung ek. . . Ch´u´yrˇa`ng, tr´aiv´oi ma trˆa.nkˆe` , c´ach biˆe˙’udiˆe˜n n`ayc˜ung c´othˆe˙’ d¯ ˇa.c trung cho c´acd¯ad¯ˆo` thi. c´okhuyˆen. . . Chˇa˙’ ng ha.n, d¯ad¯ˆo` thi. cu˙’ a H`ınh1.10 trong d¯´oc´accung d¯uo. c d¯´anhsˆo´, ta nhˆa.n 23
v1 • . . . . . . . . e5 . . . . . . . . . . . . . . . . . e e e 1 . 2 . 3 . . . . . e4 . . . . . . . . . . . . . . . . . . e6 • • v2 e8 v3 e7 H`ınh 1.10: . . d¯ u o.c k 1 2 3 4 5 6 7 8 α 1 3 1 2 2 3 2 2 β 3 1 3 1 1 2 3 2 . . . . . Trong tru`ong ho. pd¯ˆo` thi. c´otro.ng sˆo´, ta chı˙’ cˆa`n thˆemmˆo.tma˙’ ng w[] k´ıch thu´o c m . . . . . . . . luutr˜u tro.ng luo. ng cu˙’ amˆo˜ica.nh hoˇa.c cung v´oituong ´ung mˆo.t-mˆo.t c´acma˙’ ng α[] v`a β[]. . . . . Vˆ`e c´ach kh´acbiˆe˙’udiˆe˜nhiˆe.u qua˙’ honcu˙’ ad¯ˆo` thi. vˆohu´o ng su˙’ du. ng danh s´ach c´ac ca.nh xem [43]. . Mˆo´iliˆen hˆe. gi˜ua c´acbiˆe˙’ udiˆe˜n . . . Dˆ˜e d`angthˆa´yrˇa`ng tˆo`nta.i c´acthuˆa.t to´and¯ath´ucd¯ˆe˙’ chuyˆe˙’nd¯ˆo˙’igi˜ua c´ackiˆe˙’ud˜u liˆe.u trˆend¯ˆo` thi H`ınh 1.11 minh ho.a c´ackha˙’ nˇangc´othˆe˙’ c´o. . . . . . D- ˆe ˙’ chuyˆe˙’nd¯ˆo˙’igi˜ua c´ackiˆe˙’ud˜u liˆe.u, cˆa`n c´acchuong tr`ınhthu. chiˆe.nd¯iˆe` u n`ay(b`ai . . tˆa.p). C´acbiˆe˙’udiˆe˜n n`ayc´othˆe˙’ ca˙’ i biˆencho ph`uho. pv´oiyˆeucˆa`u. Chˇa˙’ ng ha.n, d¯ˆo` thi. . . . . . c´otro.ng sˆo´ c´othˆe˙’ d¯ u o. cbiˆe˙’udiˆe˜nbo˙’ imˆo.t ma trˆa. n tro. ng luo. ng (c`ongo.il`ama trˆa.nchi . . . ph´ı hay khoa˙’ ng c´ach)cˆa´p n × n trong d¯´ophˆa`ntu˙’ (i, j)bˇa`ng tro.ng luo. ng cu˙’ aca.nh hay cung (vi,vj). Tuy nhiˆen,cˆa`nch´u´yrˇa`ng, t´ınhhiˆe.u qua˙’ cu˙’ a nhiˆe` uvˆa´nd¯ˆ`e phu. thuˆo.c v`ao 24
. . Ma trˆa.nkˆe` d¯ u o. ckˆe´t theo h`ang ↑| ↑| O(n2) O(m) ↓| ↓| . . . . Ma trˆa.nkˆe` da.ng tu`ong minh Ma trˆa.nkˆe` d¯ u o. ckˆe´t theo cˆo.t ↑| ↑| O(mn) O(m) ↓| ↓| Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung hoˇa.c ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh hoˇa.c ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh . . da.ng tu`o ng minh da.ng kˆe´t theo h`ang ↑| ↑| O(mn) O(m) ↓| ↓| Ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-cung hoˇa.c ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh-ca.nh da.ng kˆe´t theo cˆo.t . . H`ınh 1.11: Mˆo´i liˆenhˆe. v`ad¯ˆo. ph´ucta.p t´ınhto´ankhi chuyˆe˙’nd¯ˆo˙’igi˜ua c´acbiˆe˙’udiˆe˜n kh´ac nhau trong d¯ˆo` thi . . . biˆe˙’udiˆe˜ncu˙’ ad¯ˆo` thi Do d¯´o,viˆe.ccho.nlu. a c´accˆa´utr´uc d˜u liˆe.umˆo.t c´ach th´ıch ho. pl`a quan tro.ng. 25
1.3 Liˆen thˆong 1.3.1 Dˆaychuyˆe` n v`achu tr`ınh . . . . Gia˙’ su˙’ v0,vk l`ac´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. vˆohu´o ng G := (V,E). Dˆaychuyˆe` n µ t`u v0 d¯ ˆe´n vk . d¯ ˆo. d`ai k l`amˆo.t d˜ayxen k˜e(k + 1) d¯ı˙’ nh v`a k ca.nh bˇa´td¯ˆa`ut`u v0 v`akˆe´tth´uc ta.i vk, µ := {v0,e1,v1,e2,v2, ,vk−1,ek,vk}, . . trong d¯´oca.nh ei liˆenthuˆo.c c´acd¯ı˙’ nh vi−1 v`a vi,i =1, 2, ,k. D- ˆe ˙’ gia˙’ ntiˆe.n, ta thu`ong viˆe´t µ := {e1,e2, ,ek}. . . . . . . . Dˆaychuyˆ`end¯uo. cgo.il`ad¯ o n gia˙’ n (tuong ´ung, so cˆa´p)nˆe´u n´okhˆongd¯ihai lˆa`n . . . qua c`ung mˆo.tca.nh (tuong ´ung, d¯ı˙’ nh). . Chu tr`ınh l`amˆo.t dˆaychuyˆ`en trong d¯´od¯ı˙’ nh d¯ˆa`utr`ung v´oid¯ı˙’ nh cuˆo´i. Chu tr`ınh . . qua mˆo˜ica.nh d¯´ung mˆo.tlˆa`ngo.il`ad¯ o n gia˙’ n. Chu tr`ınhl`a so cˆa´p nˆe´u n´od¯iqua mˆo˜i . . d¯ ı ˙’ nh d¯´ung mˆo.tlˆa`ntr`u d¯ ı ˙’ nh d¯ˆa`u tiˆenhai lˆa`n (mˆo.tlˆa`nl´uc xuˆa´t ph´atv`amˆo.tl´uc tro˙’ vˆ`e). D- `ˆo thi. trong H`ınh 1.12 c´o (a, e1,b,e2,c,e3,d,e4,b) . . l`adˆaychuyˆ`ent`u d¯ ı ˙’ nh a d¯ ˆe´nd¯ı˙’ nh b c´od¯ˆo. d`aibˆo´n. C´acchu tr`ınhsau l`aso cˆa´p (b, e2,c,e3,d,e4,b), v`a (b, e5,f,e7,e,e6,b). . . . . Trong tru`ong ho. pd¯ˆo` thi. khˆongc´o ca.nh song song (t´uc l`ahai d¯ı˙’ nh c´onhiˆ`eu nhˆa´t . . . mˆo.tca.nh liˆenthuˆo.cch´ung), d¯ˆe˙’ d¯ o n gia˙’ n dˆaychuyˆ`en µ d¯ u o. cviˆe´tla.i µ = {v0,v1,v2, ,vk}. 26
e1 b e2 a ••• c . . . . e4 e3 . . . . . . • . . . . d e5 . e6 . . . . . . . . . . . . . f •• • g e7 e e8 H`ınh 1.12: . . 1.3.2 D- u`ong d¯iv`ama.ch . . . . . . Gia˙’ su˙’ v0,vk l`ac´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. c´ohu´ong G := (V,E). D- u`o ng d¯i µ t`u v0 d¯ ˆe´n vk d¯ ˆo. . d`ai k l`amˆo.t d˜ayxen k˜e(k + 1) d¯ı˙’ nh v`a k cung bˇa´td¯ˆa`ut`u v0 v`akˆe´tth´uc ta.i vk, µ := {v0,e1,v1,e2,v2, ,vk−1,ek,vk}, trong d¯´ocung ei liˆenthuˆo.c c´acd¯ı˙’ nh vi−1 v`a vi,i =1, 2, ,k. D- ˆe ˙’ gia˙’ ntiˆe.n, ta c´othˆe˙’ . . k´yhiˆe.ud¯u`ong d¯i µ l`a {e1,e2, ,ek}. Do d¯´otrong H`ınh 1.13 d˜ayc´accung µ1 := {e6,e5,e9,e8,e4} µ2 := {e1,e6,e5,e9} µ3 := {e1,e6,e5,e9,e10,e6,e4} l`ac´acd¯u.`o.ng d¯i. . . . . . . D- u`o ng d¯il`a d¯ o n gia˙’ n nˆe´u khˆongch´ua cung n`aoqu´amˆo.tlˆa`n. Suy ra c´acd¯u`ong . . . . . . d¯ i µ1,µ2 l`ad¯on gia˙’ n, nhung d¯u`ong d¯i µ3 khˆongd¯on gia˙’ n do n´osu˙’ du.ng cung e6 hai lˆa`n. . . . . . D- u`o ng d¯il`a so cˆa´p nˆe´u khˆongd¯iqua d¯ı˙’ nh n`aoqu´amˆo.tlˆa`n. Khi d¯´od¯u`ong d¯i µ2 . . . . . . . . l`aso cˆa´pnhung c´acd¯u`o ng d¯i µ1 v`a µ3 l`akhˆongso cˆa´p. Hiˆe˙’n nhiˆen,d¯u`ong d¯iso cˆa´p . . . . . . l`ad¯on gia˙’ nnhung nguo. cla.i khˆongnhˆa´t thiˆe´td¯´ung. Chˇa˙’ ng ha.n, ch´u´yrˇa`ng d¯u`ong d¯i . . . . . . . . . . . µ1 l`ad¯on gia˙’ nnhung khˆongso cˆa´p, d¯u`ong d¯i µ2 v`uad¯on gia˙’ nv`av`uasocˆa´p, d¯u`ong . . d¯ i µ3 khˆongd¯on gia˙’ nc˜ung khˆongso cˆa´p. 27
. . . . Ch´u´yrˇa`ng, kh´ainiˆe.m dˆaychuyˆe` n l`aba˙’ n sao khˆongc´ohu´ong cu˙’ ad¯u`ong d¯iv`a . . ´ap du.ng cho c´acd¯ˆo` thi. m`akhˆongd¯ˆe˙’ yd¯ˆ´ e´nhu´ong cu˙’ a c´accung. v2 • . . . . . . . e10 . e1 . . . . . . . . . . . . . . . v1 •. . •. v3 . e . . . 3 . . . . . . . . . . . . . . . . . . e . e e 2 . . 7 9 . . . . . . . . . . . . . . . . . . . . v6 • e6 . • v4 . . e8 . . . . . . . . e4 . e5 . . . . . . . • v5 H`ınh 1.13: . . . . . D- u`o ng d¯ic˜ung c´othˆe˙’ d¯ u o. cbiˆe˙’udiˆe˜nbo˙’ i d˜ayc´acd¯ı˙’ nh m`ach´ung d¯iqua trong . . . . tru`ong ho. p khˆongc´o cung song song (t´uc hai cung c´oc`ung gˆo´cv`ac`ung ngo.n). Do d¯´o, . . . d¯ u `ong d¯i µ1 c´othˆe˙’ biˆe˙’udiˆe˜nbo˙’ i d˜ayd¯ı˙’ nh {v2,v5,v4,v3,v5,v6}. . . . Ma.ch l`amˆo.td¯u`ong d¯i {e1,e2, ,ek} trong d¯´od¯ı˙’ nh gˆo´ccu˙’ a cung e1 tr`ung v´oi . . d¯ ı ˙’ nh ngo.ncu˙’ a cung ek. Do d¯´od¯u`ong d¯i {e5,e9,e10,e6} trong H`ınh 1.13 l`ama.ch. 1.3.3 D- `ˆo thi. liˆenthˆong . . D- `ˆo thi. vˆohu´ong go.il`aliˆenthˆong nˆe´utˆa´tca˙’ c´accˇa.pd¯ı˙’ nh vi v`a vj tˆo`nta.i dˆaychuyˆ`en . t`u vi d¯ ˆe´n vj. Quan hˆe. viRvj nˆe´uv`achı˙’ nˆe´u vi = vj hoˇa.ctˆo`nta.imˆo.t dˆaychuyˆ`ennˆo´i . . . . . hai d¯ı˙’ nh vi v`a vj l`a quan hˆe. tuong d¯uong (pha˙’ nxa.,d¯ˆo´ix´ung v`abˇa´ccˆa`u). . . . . . . . . . . L´optuong d¯uong trˆen V x´acd¯i.nh bo˙’ i quan hˆe. tuong d¯uong R phˆanhoa.ch tˆa.p . V th`anhc´actˆa.p con r`oi nhau V1,V2, ,Vp. Sˆo´ p go.il`asˆo´ th`anhphˆa`n liˆenthˆong cu˙’ ad¯ˆo` thi Theo d¯i.nh ngh˜ıa,d¯ˆo` thi. liˆenthˆongnˆe´uv`achı˙’ nˆe´usˆo´ th`anhphˆa`n liˆenthˆongbˇa`ng . mˆo.t. C´acd¯ˆo` thi. con G1,G2, ,Gp sinh bo˙’ i c´actˆa.p con V1,V2, ,Vp go.i l`ac´ac th`anh phˆa`n liˆenthˆong cu˙’ ad¯ˆo` thi Mˆo˜i th`anhphˆa`n liˆenthˆongl`amˆo.td¯ˆo` thi. liˆenthˆong. 28
H`ınh 1.14 minh ho.ad¯ˆo` thi. c´oba th`anhphˆa`n liˆenthˆong. v1 v5 v3 . • •. • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •• ••. • v2 v4 v7 v8 v6 H`ınh 1.14: D- `ˆo thi. c´oba th`anhphˆa`n liˆenthˆong. . . Nhˆa.nx´et 1.3.1. D- `ˆo thi. vˆohu´ong G c´o p th`anhphˆa`n liˆenthˆong G1,G2, ,Gp nˆe´uv`a . chı˙’ nˆe´u ma trˆa.nkˆe` A cu˙’ a G c´othˆe˙’ viˆe´to˙’ da.ng A1 0 ··· 0   0 A2 ··· 0  A =   ,  . . .   . . .    00··· Ap trong d¯´o Ai,i=1, 2, ,p, l`ama trˆa.nkˆe` cu˙’ a th`anhphˆa`n liˆenthˆong Gi. . . . . Ta c˜ung c´onhˆa.n x´ettuong tu. d¯ ˆo´iv´oi ma trˆa.n liˆenthuˆo.cd¯ı˙’ nh ca.nh. . . X´acd¯i.nh sˆo´ th`anhphˆa`n liˆenthˆongcu˙’ ad¯ˆo` thi. l`amˆo.t trong nh˜ung b`aito´anco ba˙’ n . . cu˙’ a l´ythuyˆe´td¯ˆo` thi. v`ac´onhiˆe` u´ung du.ng trong thu. ctiˆe˜n; chˇa˙’ ng ha.n, x´acd¯i.nh t´ınh liˆenthˆongcu˙’ ama.ch d¯iˆe.n, ma.ng d¯iˆe.n thoa.i, v.v. . Ch´ung ta s˜etr`ınhb`aymˆo.tsˆo´ thuˆa.t to´anc´oth`oi gian O(m) gia˙’ i b`aito´ann`ayv`ı . n´ocho ph´ep t`ıml`oi gia˙’ icu˙’ amˆo.tsˆo´ b`aito´ankh´ac. . . . Bˇa´td¯ˆa`uv´oid¯ı˙’ nh n`aod¯´ocu˙’ ad¯ˆo` thi.,ch´ung ta liˆe.tkˆe c´acd¯ı˙’ nh theo th´u tu. cu˙’ a . . . thuˆa.t to´an t`ımkiˆe´m theo chiˆe` u sˆau,t´ucl`ach´ung ta d¯i,d¯ˆa`u tiˆen,xa nhˆa´t c´othˆe˙’ d¯ u o. c . trˆend¯ˆo` thi. m`akhˆongta.o th`anhchu tr`ınh,v`asau d¯´otro˙’ vˆ`e vi. tr´ır˜enh´anhgˆa`n d¯ˆay . nhˆa´tm`ach´ung ta d¯˜abo˙’ qua, v`atiˆe´ptu.c cho d¯ˆe´n khi tro˙’ vˆ`e d¯ ı ˙’ nh xuˆa´t ph´at.Do d¯´otˆa.p c´acd¯ı˙’ nh bˇa´tgˇa.ps˜eta.o th`anhth`anhphˆa`n liˆenthˆongd¯ˆa`u tiˆen. 29
. . . . Nˆe´utˆa´tca˙’ c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. d¯ u o. c duyˆe.tth`ıd¯ˆo` thi. liˆenthˆong;nguo. cla.i, ch´ung . . . . . . ta kho˙’ id¯ˆa`ula.ithu˙’ tu.c trˆenv´oimˆo.td¯ı˙’ nh m´oi chuad¯uo. cviˆe´ng thˇam;do d¯´ota xˆay . . . . du. ng d¯uo. c th`anhphˆa`n liˆenthˆongth´u hai, v`avˆanvˆan. . . . Thuˆa.t to´andu´o i d¯ˆaytr`ınhb`aygiai d¯oa.nd¯ˆa`u tiˆen,t´uc l`at`ımth`anhphˆa`nliˆen . . thˆongch´uamˆo.td¯ı˙’ nh d¯˜acho-nˆe´u th`anhphˆa`n n`aych´uatˆa´tca˙’ c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. th`ı d¯` ˆo thi. liˆenthˆong. K´yhiˆe.u num(i) l`asˆo´ hiˆe.ucu˙’ ad¯ı˙’ nh vi trong qu´atr`ınht`ımkiˆe´m. Nˆe´u ta bˇa´td¯ˆa`u . . . bˇa`ng d¯ı˙’ nh s th`ıd¯ˇa.t num(s)=1. K´yhiˆe.u P (i) l`ad¯ı˙’ nh d¯´ung liˆe` n tru´o cd¯ı˙’ nh vi trong . . . . . . cˆayc´ogˆo´c (xem Chuong 4) d¯uo. c xˆaydu. ng trong qu´atr`ınhthu. chiˆe.n thuˆa.t to´an. . . ˙’ . - + X´et d¯ˆo` thi. d¯ u o. cbiˆeudiˆ˜enbo˙’ i ´anhxa. d¯atri. Γ. Dˇa.t di l`asˆo´ c´acd¯ı˙’ nh kˆ`e d¯ ı ˙’ nh + . . vi : di := #Γ(vi). V´oimˆo˜i k =1, 2, ,n, k´yhiˆe.uΓk(vi) l`ad¯ı˙’ nh th´u k trong tˆa.pΓ(vi). . . . D- ˆe ˙’ thu. chiˆe.n t`ımkiˆe´m trˆend¯ˆo` thi.,ta.imˆo˜ibu´o ccu˙’ a thuˆa.t to´anch´ung ta d¯ˇa.t n(i) . . . . . l`achı˙’ sˆo´ cu˙’ ad¯ı˙’ nh d¯uo. cviˆe´ng thˇamcuˆo´ic`ung t`u d¯ ı ˙’ nh vi. Kho˙’ id¯ˆa`uv´oi n(i)=0,i = 1, 2, ,n. . . . Du´oi d¯ˆayl`athuˆa.t to´an(da.ng khˆongd¯ˆe. qui) cu˙’ aTr´emaux d¯ua ra nˇam1882 v`a . . sau d¯´od¯uo. c Tarjan ca˙’ itiˆe´n [53]. . Thuˆa.t to´anTr´emaux-Tarjan t`ım th`anhphˆa` n liˆenthˆongch´uad¯ı˙’ nh s. . - + . 1. [Kho˙’ ita.o] Dˇa.t P (i)=0,di := #Γ(vi)v`an(i)=0v´oimo.id¯ı˙’ nh vi,i=1, 2, ,n; k =0, num(s)=1,P(s)=s (t`uy ´y,kh´ackhˆong), i = s. . . . 2. [Bu´oclˇa.p] Trong khi (n(i) =6 d(i)) hoˇa.c(i =6 s) thu. chiˆe.n . . • Nˆe´u n(i)=d(i)d¯ˇa.t i = P (i) (lˆa`n nguo. c); . . • nguo. cla.i, d¯ˇa.t n(i)=n(i) + 1 (viˆe´ng thˇamd¯ı˙’ nh kˆe´ tiˆe´p trong Γ(vi)), v`a j =Γn(i)(vi). Nˆe´u P (j) = 0 th`ıg´an P (j)=i, i = j, k = k +1, num(i)=k. . . Kˆe´tth´uc thuˆa.t to´an,nˆe´u k = n th`ıd¯ˆo` thi. liˆenthˆong;nguo. cla.i th`anhphˆa`n liˆenthˆong . . ch´uad¯ı˙’ nh s gˆo`m k d¯ ı ˙’ nh m`anum(i) nhˆa.n c´acgi´atri. t`u 1d¯ˆe´n k. 30
. . . . V´ı du. 1.3.2. X´et d¯ˆo` thi. trong H`ınh 1.15. C´acd¯ı˙’ nh s˜ed¯uo. cviˆe´ng thˇamtheo th´u tu. 1, 4, 2, 3 v`a5. Qu´atr`ınht`ımkiˆe´m c´othˆe˙’ biˆe˙’udiˆe˜n th`anhcˆayc´ogˆo´c (d¯ı˙’ nh gˆo´cl`av1) v5 • v4 v •• • v 1 2 .• v3 H`ınh 1.15: trong H`ınh 1.16. v5 • 5 . v4 . v1 •• • v2 12. 3 . 4 • v3 H`ınh 1.16: Thuˆa.t to´ant`ım kiˆe´m theo chiˆe` u sˆau 1. Thˇamd¯ı˙’ nh xuˆa´t ph´at s. 2. V´o.imˆo˜id¯ı˙’ nh w kˆ`e v´o.i v (c´ohu.´o.ng t`u. v d¯ ˆe´n w) l`amc´acbu.´o .c sau: . . . . . Nˆe´u w chuad¯uo. c thˇam,´apdu.ng thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eu sˆauv´oi w nhu l`ad¯ı˙’ nh xuˆa´t ph´at. 31
Trong c´ach t`ımkiˆe´m theo chiˆ`eu sˆau,ta d¯itheo d¯u.`o.ng t`u. d¯ ı ˙’ nh xuˆa´t ph´atcho d¯ˆe´n . . khi d¯a.td¯ˆe´nmˆo.td¯ı˙’ nh c´otˆa´tca˙’ c´acd¯ı˙’ nh kˆe` n´od¯˜ad¯uo. cviˆe´ng thˇam. Sau d¯´ota quay . . . . . . la.id¯ı˙’ nh cuˆo´ic`ung v`uad¯uo. c thˇamdo.c theo d¯u`ong n`aysao cho c´acd¯ı˙’ nh kˆe` v´oi n´o(c´o . . . . . . . . . . hu´ong t`u n´od¯ira trong tru`ong ho. pd¯ˆo` thi. c´ohu´ong) c´othˆe˙’ thˇamd¯uo. c. D- ˆe ˙’ c´othˆe˙’ . . . . . quay tro˙’ la.i, ta luutr˜u c´acd¯ı˙’ nh do.c theo d¯u`ong n`aytrong mˆo.t ngˇanxˆe´p. Nˆe´uthu˙’ tu.c . . . . . . . d¯ u o.cviˆe´tda.ng d¯ˆe. quy th`ıngˇanxˆe´p n`ayd¯uo. cba˙’ o tr`ımˆo.t c´ach tu. d¯ ˆo.ng; trong tru`ong . . . . . ho. p nguo. cla.i, cˆa`nmˆo.tma˙’ ng d¯´anhdˆa´u c´acd¯ı˙’ nh d¯˜ad¯uo. cviˆe´ng thˇam. Thuˆa.t to´ant`ım kiˆe´m theo chiˆe` urˆo.ng . . Trong thuˆa.t to´ann`ay, ch´ung ta thˇamc´acd¯ı˙’ nh theo t`ung m´ucmˆo.t, v`akhi thˇammˆo.t . . . . . . d¯ ı ˙’ nh o˙’ m´uc n`aod¯´o,ta pha˙’ iluutr˜u n´od¯ˆe˙’ c´othˆe˙’ tro˙’ la.i khi d¯ihˆe´tmˆo.tm´uc, v`ıvˆa.yc´o . . thˆe˙’ thˇamc´acd¯ı˙’ nh kˆe` cu˙’ a n´o.Thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eurˆo.ng du´oid¯ˆayd`ung mˆo.t . h`angd¯o. i theo c´ach n`ay. 1. Thˇamd¯ı˙’ nh xuˆa´t ph´at. . . . 2. Kho˙’ id¯ˆo.ng mˆo.t h`angd¯o. ichı˙’ ch´uad¯ı˙’ nh xuˆa´t ph´at. . . . 3. Trong khi h`angd¯o. i khˆongrˆo˜ng l`amc´acbu´o c sau: . . Lˆa´ymˆo.td¯ı˙’ nh v t`u h`angd¯o. i. V´o.itˆa´tca˙’ c´acd¯ı˙’ nh w kˆ`e v´o.i v, l`amc´acbu.´o .c sau: . . . Nˆe´u(w chuad¯uo. c thˇam)th`ı: Thˇam w. . Thˆem w v`aoh`angd¯o. i. . C´acthuˆa.t to´ant`ımkiˆe´m theo chiˆ`eurˆo.ng v`at`ımkiˆe´m theo chiˆ`eu sˆaul`arˆa´tcoba˙’ n . cho nhiˆ`eu thuˆa.t to´ankh´acd¯ˆe˙’ xu˙’ l´yd¯ˆo` thi V´ıdu.,d¯ˆe˙’ duyˆe.tmˆo.td¯ˆo` thi., ta c´othˆe˙’ ´ap . du.ng nhiˆe` ulˆa`nmˆo.t trong c´acc´ach n´oitrˆen,cho.n c´acd¯ı˙’ nh xuˆa´t ph´atm´oinˆe´ucˆa`n thiˆe´t, . . cho d¯ˆe´n khi tˆa´tca˙’ c´acd¯ı˙’ nh d¯uo. c thˇam. 32
1.3.4 Cˆa` u, k−liˆenthˆong . D- iˆe˙’m kh´op cu˙’ ad¯ˆo` thi. l`amˆo.td¯ı˙’ nh m`ax´oan´os˜etˇangsˆo´ th`anhphˆa`nliˆen thˆong; cˆa`u . . . . . l`aca.nh m`ax´oan´oc˜ung c´oa˙’ nh huo˙’ ng tuong tu. .D- `ˆo thi. trong H`ınh 1.15 c´omˆo.td¯iˆe˙’m . kh´op l`ad¯ı˙’ nh v4 v`ahai cˆa`u l`ac´acca.nh (v1,v4)v`a(v4,v5). V´ı du. 1.3.3. Trong mˆo.td¯ˆo` thi. khˆongc´ochu tr`ınh,c´acd¯ı˙’ nh khˆongpha˙’ i l`ad¯ı˙’ nh treo, . . . . t´ucd¯ı˙’ nh c´obˆa.c ≥ 2, l`ad¯iˆe˙’m kh´op. Nguo. cla.i, d¯ˆo` thi. c´ochu tr`ınhHamilton (xem Phˆa`n 5.3) khˆongc´od¯iˆe˙’m kh´o.p. . . . . . . V´ı du. 1.3.4. [Ma.ng thˆongtin] Gia˙’ su˙’ V l`atˆa.pho. pnh˜ung ngu`oi thuˆo.cmˆo.ttˆo˙’ ch´uc . . . . . . n`aod¯´o;ta d¯ˇa.t(a, b) ∈ E nˆe´u ngu`o i a v`a b c´othˆe˙’ b´aotin v´oi nhau. Nh˜ung ngu`oi liˆen . . . . . . la.cl`anh˜ung d¯iˆe˙’m kh´op. Nh˜ung ngu`oi d¯´ol`anh˜ung mˇa´tx´ıch quan tro.ng, v`ımˆa´tho. s˜e . . . ph´av˜o t´ınhthˆo´ng nhˆa´t v`asu. liˆenkˆe´tcu˙’ atˆo˙’ ch´uc. . D- .inh l´y 1.3.5. Gia˙’ su˙’ G =(V,E) l`ad¯ˆo` thi. liˆenthˆong.Khi d¯´od¯ı˙’ nh v ∈ V l`ad¯iˆe˙’m . . kh´opnˆe´u v`achı˙’ nˆe´utˆo`nta. i hai d¯ı˙’ nh a v`a b sao cho mo. i dˆaychuyˆ`ennˆo´i a v´oi b d¯` ˆe ud¯i qua v. . . . Ch´ung minh. D- iˆe` ukiˆe.ncˆa`n. Nˆe´ud¯ˆo` thi. con sinh bo˙’ itˆa.pho. p V \{v} khˆongliˆen thˆong . 0 . th`ın´och´ua ´ıtnhˆa´t hai th`anhphˆa`n C v`a C ; gia˙’ su˙’ a l`amˆo.td¯ı˙’ nh n`aod¯´ocu˙’ a C v`a b l`a 0 mˆo.td¯ı˙’ nh n`aod¯´ocu˙’ a C . Trong d¯ˆo` thi. liˆenthˆongban d¯ˆa`u G mo.i dˆaychuyˆ`enbˆa´tk`ynˆo´i a v´o.i b d¯` ˆe u pha˙’ i d¯iqua v. . D- iˆe` ukiˆe.nd¯u˙’ . Nˆe´umˆo.t dˆaychuyˆe` nbˆa´tk`ynˆo´i a v´oi b d¯` ˆe u d¯iqua v th`ıd¯ˆo` thi. con sinh . . . ra bo˙’ i V \{v} khˆongthˆe˙’ liˆenthˆong;bo˙’ ivˆa.yd¯ı˙’ nh v l`ad¯iˆe˙’m kh´op. / Tac´othˆe˙’ d¯ i .nh ngh˜ıa: d¯ˆo` thi. n d¯ ı ˙’ nh (n ≥ 3) l`a2−liˆenthˆong hay d¯` ˆo thi. khˆong . . . t´ach d¯uo. c nˆe´u v`achı˙’ nˆe´u n´oliˆenthˆongv`akhˆongc´od¯iˆe˙’m kh´op. C´acd¯ˆo` thi. con 2−liˆen . thˆongcu. cd¯a.icu˙’ a G ta.o th`anhmˆo.t phˆanhoa.ch cu˙’ a G, v`ago.i l`ac´ac th`anhphˆa`n 2−liˆen thˆong cu˙’ a G. . . D- ˆe ˙’ t`ımc´acd¯iˆe˙’m kh´op v`ac´acth`anhphˆa`n2−liˆenthˆongta c´othˆe˙’ su˙’ du.ng thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eu sˆau. 33
. . . . V´oimˆo˜id¯ı˙’ nh vi, x´et tˆa.p D(i) c´acd¯ı˙’ nh d¯´ung liˆe` n tru´ocd¯ı˙’ nh vi trong cˆay T x´ac . . d¯ i .nh bo˙’ i thuˆa.t to´ant`ımkiˆe´m theo chiˆ`eu sˆau.Khi d¯´o,v´oimo.id¯ı˙’ nh vj ∈ D(i) ta c´o l(j) = min (num(k)) k∈Γ(vj) . . . . l`asˆo´ nho˙’ nhˆa´td¯uo. c g´ancho d¯ı˙’ nh kˆe` v´oid¯ı˙’ nh vj trong G. Bˆaygi`o ta d¯i.nh ngh˜ıamˆo.t chı˙’ sˆo´ m´o.i inf(i) := min l(j). vj∈D(i) . . . . . . Do d¯´ochı˙’ sˆo´ n`aytuong ´ung cu. ctiˆe˙’ucu˙’ a num(i) v`asˆo´ nho˙’ nhˆa´td¯uo. c g´ancho c´ac . . . d¯ ı ˙’ nh m`ac´othˆe˙’ d¯ ˆe´nd¯uo. cbˇa`ng d¯´ung mˆo.tca.nh t`u mˆo.t trong c´ac hˆa. uduˆe. cu˙’ a vi trong cˆay T. . . Do d¯´o,trong V´ıdu. 1.3.2 (H`ınh1.16), d¯ı˙’ nh v2 c´od¯´ung mˆo.td¯ı˙’ nh tru´o cliˆe` nkˆe` l`a d¯ ı ˙’ nh v4, v`ado d¯´oinf(2) = num(4) = 2. . . . Ch´u´yrˇa`ng inf(i) ≤ num(i)v`ı kho˙’ id¯ˆa`ut`u tiˆe` nbˆo´i cu˙’ a vi n´oc´othˆe˙’ tro˙’ vˆ`e vi. . . . Honn˜ua, dˆe˜ d`angchı˙’ ra rˇa`ng, nˆe´u inf(i) = num(i) th`ıd¯ı˙’ nh vi l`ad¯iˆe˙’m kh´opcu˙’ a . d¯` ˆo thi Ngo`aira, c´acd¯ı˙’ nh bˇa´tgˇa.p khi duyˆe.t tro˙’ la.id¯ı˙’ nh vi ta.o th`anhmˆo.t th`anhphˆa`n 2−liˆenthˆong. . . . . . Thuˆa.t to´andu´oi d¯ˆaytr`ınhb`ayphuong ph´apx´acd¯i.nh c´acd¯iˆe˙’m kh´opcu˙’ ad¯ˆo` thi. liˆenthˆongxuˆa´t ph´att`u. d¯ ı ˙’ nh s. . Thuˆa.t to´anTarjan t`ım d¯iˆe˙’ m kh´opcu˙’ ad¯ˆo` thi. liˆenthˆong . - + . 1. [Kho˙’ ita.o] Dˇa.t P (i)=0,di := #Γ(vi),n(i) = 0 v`ainf(i)=∞ v´oimo.id¯ı˙’ nh vi,i=1, 2, ,n; k =0, num(s)=1,P(s)=s, i = s. . . . 2. [Bu´oclˇa.p] Trong khi (n(i) =6 d(i)) hoˇa.c(i =6 s) thu. chiˆe.n • Nˆe´u n(i)=d(i)d¯ˇa.t q = inf(i),i= P (i), inf(i) = min(q,inf(i)). . Nˆe´u inf(i) =num(i)th`ıvi l`ad¯iˆe˙’m kh´op (v`ata c´othˆe˙’ x´acd¯i.nh th`anhphˆa`n 2−liˆenthˆong). 34
. . . • Nguo. cla.i, t´ucl`an(i) =6 d(i) (viˆe´ng thˇamd¯ı˙’ nh kˆe´ tiˆe´p trong Γ(vi)) Nˆe´u j = P (i) th`ıg´an n(i)=n(i)+1,j =Γn(i)(i). Nˆe´u P (j) = 0 th`ıg´an inf(i) = min(inf(i), num(i)),P(j)=i, i = j, k = k +1, num(i)=k. . . Nguo. cla.inˆe´u P (j) =6 0 g´aninf(i) = min(inf(i), num(j)). . . . . Dˆ˜e d`angkiˆe˙’m tra v´oiv´ıdu. tru´oc, d¯ı˙’ nh v4 l`ad¯iˆe˙’m kh´op. Ch´u´yrˇa`ng c´othˆe˙’ x´ac . . . d¯ i .nh th`anhphˆa`n2−liˆenthˆongbˇa`ng c´ach su˙’ ad¯ˆo˙’iBu´oc 2 trong Thuˆa.t to´anTarjan. . . Mˆe.nh d¯ˆ`e 1.3.6. Th`oi gian thu. chiˆe.n c´acthuˆa. t to´anTr´emaux-Tarjan v`aTarjan l`a O(m). . Ch´ung minh. B`aitˆa.p. / Thiˆe´tdiˆe.n A cu˙’ ad¯ˆo` thi. liˆenthˆong G =(E,V ) l`atˆa.p con A ⊂ V sao cho d¯ˆo` thi. . . . con GV \A nhˆa.nd¯uo. ct`u G bˇa`ng c´ach x´oac´acd¯ı˙’ nh trong A (v`ac´acca.nh liˆenthuˆo.c n´o) khˆongliˆen thˆong. D- `ˆo thi. go.il`ak−liˆenthˆong nˆe´uv`achı˙’ nˆe´u n´oliˆenthˆong,c´osˆo´ d¯ ı ˙’ nh n ≥ k +1, v`a . . . . khˆongch´uamˆo.t thiˆe´tdiˆe.n c´olu. cluo. ng (k − 1). . C´acd¯ˆo` thi. con k−liˆenthˆongcu. cd¯a.icu˙’ a G ta.o th`anhmˆo.t phˆanhoa.ch cu˙’ a G v`a go.i l`ac´ac th`anhphˆa`n k−liˆenthˆong. . . . C´acth`anhphˆa`n3−liˆenthˆongcu˙’ ad¯ˆo` thi. c´othˆe˙’ nhˆa.nd¯uo. c trong th`oi gian O(m) . . . bˇa`ng thuˆa.t to´antuong tu. cu˙’ a Tarjan. D- ad¯ˆo` thi. liˆenthˆong G go.il`ak−ca.nh liˆenthˆong nˆe´u n´ovˆa˜n c`onliˆen thˆongkhi . x´oad¯i´ıthon k ca.nh. . Do d¯´o,d¯ad¯ˆo` thi. l`a2−liˆenthˆongnˆe´u v`achı˙’ nˆe´u n´oliˆenthˆongv`akhˆongch´uacˆa`u. . . Bˇa`ng c´ach su˙’ ad¯ˆo˙’ila.i thuˆa.t to´anTarjan, ta c´othˆe˙’ x´acd¯i.nh c´accˆa`u trong th`oi gian . . O(m). X´et t´ınh2−ca.nh liˆenthˆongc´onhiˆ`eu´ung du. ng trong thu. ctˆe´:ma.ng d¯iˆe.n, d¯iˆe.n thoa.i, v.v., pha˙’ i2−ca.nh liˆenthˆong! 35
1.3.5 D- `ˆo thi. liˆenthˆongma.nh . . . . D- `ˆo thi. c´ohu´ong go.il`aliˆenthˆongma.nh nˆe´utˆa´tca˙’ c´accˇa.pd¯ı˙’ nh vi v`a vj tˆo`nta.id¯u`ong . d¯ i tu ` vi d¯ ˆe´n vj. . . . X´et quan hˆe. viRvj nˆe´u v`achı˙’ nˆe´u hoˇa.c vi = vj hoˇa.ctˆo`nta.id¯u`ong d¯it`u d¯ ı ˙’ nh vi . . . . . . . d¯ ˆe´nd¯ı˙’ nh vj v`ad¯u`ong d¯it`u d¯ ı ˙’ nh vj d¯ ˆe´nd¯ı˙’ nh vi. Dˆ˜e thˆa´y d¯ˆayl`a quan hˆe. tuong d¯uong . (pha˙’ nxa.,d¯ˆo´ix´ung v`abˇa´ccˆa`u). . . . . . . . . . . L´optuong d¯uong trˆen V x´acd¯i.nh bo˙’ i quan hˆe. tuong d¯uong R phˆanhoa.ch tˆa.p . V th`anhc´actˆa.p con r`oi nhau V1,V2, ,Vp. Sˆo´ p go.il`asˆo´ th`anhphˆa`n liˆenthˆongma.nh . cu˙’ ad¯ˆo` thi C´acd¯ˆo` thi. con G1,G2, ,Gp sinh bo˙’ i c´actˆa.p con V1,V2, ,Vp go.i l`ac´ac th`anhphˆa`n liˆenthˆongma.nh cu˙’ a G. Theo d¯i.nh ngh˜ıa,d¯ˆo` thi. liˆenthˆongma.nh nˆe´uv`a chı˙’ nˆe´usˆo´ th`anhphˆa`n liˆenthˆongma.nh bˇa`ng mˆo.t. . . . . Nhˆa.n x´etrˇa`ng, th`anhphˆa`n liˆenthˆongma.nh Cl ch´uad¯ı˙’ nh vl d¯ u o. cchobo˙’ i C = Γˆ ∩ Γˆ−1, l vl vl . . . . . v`at`u d¯´osuy ra mˆo.t thuˆa.t to´anrˆa´td¯on gia˙’ n th`oi gian d¯ath´uc O(m)du. a trˆenthuˆa.t . to´ant`ımkiˆe´m theo chiˆ`eu sˆaum`ac´othˆe˙’ su˙’ du.ng n´od¯ˆe˙’ t`ım Cl. Do d¯´ot´ınhliˆen thˆongma.nh dˆe˜ d`angkiˆe˙’m tra. Chı˙’ cˆa`n x´etkhi n`ao Cl ≡ V. (H˜ay gia˙’ i b`aito´ann`aybˇa`ng ma trˆa.n). Nˆe´umˇa.t kh´ac,ch´ung ta muˆo´n t`ımtˆa´tca˙’ c´acth`anhphˆa`n liˆenthˆongma.nh, ta s˜e . su˙’ du. ng Thuˆa.t to´anTarjan. . . Thˆa.tvˆa.ytas˜ech´ung minh rˇa`ng, thuˆa.t to´anTarjan ´apdu.ng v´oi c´acd¯ˆo` thi. c´o . . hu´ong, cho ph´ep t`ımc´acth`anhphˆa`n liˆenthˆongma.nh. . . . Ch´ung ta kho˙’ id¯ˆa`uv´oi thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆau,nhu trong c´acthuˆa.t . . to´ant`ımkiˆe´m theo chiˆe` u sˆauv`aTarjan. V´oimˆo˜id¯ı˙’ nh vi x´et mˆo.tchı˙’ sˆo´ m´oi l`asˆo´ nho˙’ . nhˆa´tcu˙’ achı˙’ sˆo´ d¯ ı ˙’ nh m`ac´othˆe˙’ d¯ ˆe´n n´obˇa`ng chı˙’ mˆo.t cung t`u mˆo.t hˆa. uduˆe. cu˙’ a vi trong . . . cˆaygia pha˙’ . Chı˙’ sˆo´ m´oi n`ayd¯uo. ck´yhiˆe.u l`ainf(i). Nhˆa.nx´et rˇa`ng ch´ung ta luˆonluˆonc´oinf(i) ≤ num(i). Dˆ˜e d`angchı˙’ ra rˇa`ng khi . . ch´ung ta tro˙’ la.i trong cˆaygia pha˙’ ,th`ımˆo.td¯ı˙’ nh m`axa˙’ y ra d¯ˇa˙’ ng th´uc inf(i) = num(i)s˜e 36
phˆanhoa.ch d¯ˆo` thi. th`anh´ıtnhˆa´t hai th`anhphˆa`n liˆenthˆongma.nh, v`amˆo.t trong ch´ung . . . . . . . . tuong ´ung tˆa.p c´acd¯ı˙’ nh m`ad¯˜ad¯uo. cviˆe´ng thˇamtru´oc khi t´oid¯ı˙’ nh vi. D- `ˆo thi. trong H`ınh 1.17 c´oba th`anhphˆa`n liˆenthˆongma.nh: C1 = {a, b, c, d, e}, C6 = {g,f}, C8 = {h}. a c e • •. • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f . . . • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • g b d . • h H`ınh 1.17: . . Ch´ung ta su˙’ du.ng thuˆa.tng˜u d¯` ˆo thi. thu go. n d¯ ˆe ˙’ biˆe˙’udiˆe˜nd¯ˆo` thi. G qua quan hˆe. liˆenthˆongma.nh Gr := G/R. Do d¯´oc´acd¯ı˙’ nh cu˙’ a Gr l`ac´acth`anhphˆa`n liˆenthˆongma.nh . cu˙’ a G v`atˆo`nta.i cung gi˜ua hai d¯ı˙’ nh Ci v`a Cj nˆe´uv`achı˙’ nˆe´utˆo`nta.i ´ıtnhˆa´tmˆo.t cung . gi˜uamˆo.td¯ı˙’ nh cu˙’ a Ci v`a Cj trong G. Hiˆe˙’n nhiˆend¯ˆo` thi. Gr khˆongc´oma.ch. H`ınh 1.18 l`a . . . d¯` ˆo thi. thu go.ncu˙’ ad¯ˆo` thi. c´ohu´o ng trong H`ınh 1.17. Nghiˆen c´uu c´acth`anhphˆa`n liˆen . . thˆongma.nh v`at`ımd¯ˆo` thi. thu go.n l`anh˜ung b`aito´anthu. ctiˆe˜n quan tro.ng; chˇa˙’ ng ha.n . trong mˆo´i liˆenhˆe. v´oi x´ıch Markov, trong phˆant´ıch cˆa´utr´uc cu˙’ amˆo.thˆe. thˆo´ng (xem [30]). Phˆa`ntiˆe´p theo ch´ung ta s˜ed¯ˆe` cˆa.pthˆemvˆ`e vˆa´nd¯ˆ`e n`ay. 1.4 Pha.mviv`aliˆen thˆongma.nh . . Ta biˆe´trˇa`ng hˆe. thˆo´ng truyˆe` n thˆongcu˙’ amˆo.ttˆo˙’ ch´uc c´othˆe˙’ xem nhu mˆo.td¯ˆo` thi. trong . . . . . . . . d¯´omˆo˜i ngu`o ituong ´ung mˆo.td¯ı˙’ nh v`ac´ackˆenhtruyˆe` n thˆongtuong ´ung c´accung. Cˆau . . . . ho˙’ id¯ˇa.t ra l`atrong hˆe. thˆo´ng n`ay, thˆongtin t`u vi c´othˆe˙’ d¯ ˆe´nd¯uo. c vj khˆong?T´uc l`ac´o 37
C6 .• •• C1 C8 H`ınh 1.18: . . . . . tˆo`nta.id¯u`ong d¯it`u vi d¯ ˆe´n vj?Nˆe´ud¯u`ong d¯id¯´otˆo`nta.i ta n´oi vj thuˆo.c pha.mvicu˙’ a . . . . vi. Ch´ung ta c˜ung quan tˆamd¯ˆe´nc´od¯u`o ng d¯it`u vi d¯ ˆe´n vj v´oisˆo´ cung ha.n chˆe´ khˆong? . Mu.cd¯´ıch cu˙’ a phˆa`n n`ayl`atha˙’ o luˆa.nmˆo.t v`aikh´ainiˆe.mcoba˙’ n liˆenquan d¯ˆe´n c´act´ınh . . . chˆa´t pha.m vi v`aliˆenthˆongma.nh cu˙’ a c´acd¯ˆo` thi. v`agi´oi thiˆe.umˆo.tsˆo´ thuˆa.t to´anco so˙’ . . . Theo thuˆa.tng˜u cu˙’ ad¯ˆo` thi. biˆe˙’udiˆe˜n cho mˆo.ttˆo˙’ ch´uc, phˆa`n n`aykha˙’ o s´atmˆo.tsˆo´ cˆauho˙’ i: . . . . . . . 1. Sˆo´ ngu`oi ´ıtnhˆa´tm`amˆo˜i ngu`oi trong tˆo˙’ ch´ucc´othˆe˙’ liˆenla.cd¯uo. cbˇa`ng bao nhiˆeu? . . . . . 2. Sˆo´ ngu`oi nhiˆe` u nhˆa´t c´othˆe˙’ liˆenla.cd¯uo. cv´oi nhau bˇa`ng bao nhiˆeu? . 3. Hai b`aito´antrˆenc´oquan hˆe. g`ıv´oi nhau? 1.4.1 Ma trˆa. n pha. mvi . Ma trˆa. n pha. mviR =(rij)d¯i.nh ngh˜ıanhu sau: . . . ( 1nˆe´utˆo`nta.id¯u`ong d¯it`u d¯ ı ˙’ nh vi d¯ ˆe´nd¯ı˙’ nh vj, rij := . . 0nˆe´u nguo. cla.i. . . . Tˆa.p R(vi) c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. G c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u d¯ ı ˙’ nh vi gˆo`m c´acd¯ı˙’ nh vj sao . . . . cho phˆa`ntu˙’ rij bˇa`ng 1. Theo d¯i.nh ngh˜ıa,tˆa´tca˙’ c´acphˆa`ntu˙’ trˆend¯u`ong ch´eo cu˙’ ama trˆa.n pha.mvibˇa`ng 1. . . . . . Do Γ(vi) l`atˆa.p c´acd¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u vi theo mˆo.td¯u`ong d¯ic´od¯ˆo. d`ai1 nˆen 2 . . . . . . tˆa.p Γ(Γ(vi)) = Γ (vi)gˆo`mnh˜ung d¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u vi theo mˆo.td¯u`o ng d¯ic´od¯ˆo. 38
. . . p . . . . . . d`ai2. Tuong tu. ,Γ(vi) l`atˆa.pnh˜ung d¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u vi theo mˆo.td¯u`ong d¯ic´o . . . d¯ ˆo. d`ai p. Do vˆa.y, tˆa.p c´acd¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u vi l`a 1 2 R(vi)={vi}∪Γ (vi) ∪ Γ (vi) ∪··· . . . . . . . . . . . Nhung do d¯ˆo` thi. d¯ u o. cx´et l`ah˜uuha.n v`amo.id¯u`ong d¯id¯ˆ`euch´uamˆo.td¯u`o ng d¯icon so cˆa´p trong d¯´o,nˆentˆo`nta.i p sao cho 1 2 p R(vi)={vi}∪Γ (vi) ∪ Γ (vi) ∪···∪Γ (vi). (1.1) . . . . . . Suy ra tˆa.p pha.mviR(vi) c´othˆe˙’ nhˆa.nd¯uo. ct`u Phuong tr`ınh(1.1) bˇa`ng c´ach thu. chiˆe.n . . . . c´acph´epto´anho. pt`u tr´aisang pha˙’ i cho d¯ˆe´n khi tˆa.phiˆe.n h`anhkhˆongtˇangk´ıch thu´oc . trong lˆa`nlˇa.pkˆe´ tiˆe´p. Sˆo´ c´acph´epto´anho. p phu. thuˆo.c v`aod¯ˆo` thi.,mˇa.cd`uhiˆe˙’n nhiˆen rˇa`ng p ≤ n − 1, trong d¯´o n l`asˆo´ d¯ ı ˙’ nh cu˙’ ad¯ˆo` thi . . . . . Vˆa.y ma trˆa.n pha.m vi c´othˆe˙’ d¯ u o. c xˆaydu. ng nhu sau. T`ım tˆa.p R(vi)v´oimˆo˜id¯ı˙’ nh . . vi theo trˆen.D- ˇa.t rij =1nˆe´u vj ∈ R(vi), v`a rij =0nˆe´u nguo. cla.i. . . . Ma trˆa. nd¯a. td¯uo. c Q =(qij)d¯i.nh ngh˜ıanhu sau: . . . ( 1nˆe´utˆo`nta.id¯u`ong d¯it`u d¯ ı ˙’ nh vi d¯ ˆe´nd¯ı˙’ nh vj, qij := . . 0nˆe´u nguo. cla.i. . t T`u d¯ i .nh ngh˜ıata c´o Q = R . . . . . . . K´yhiˆe.u Q(vi) l`atˆa.p c´acd¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. cd¯ı˙’ nh vi. Tu ong tu. nhu trˆenta c˜ung c´o −1 −2 −p Q(vi)={vi}∪Γ (vi) ∪ Γ (vi) ∪···∪Γ (vi), (1.2) −2 −1 −1 trong d¯´oΓ (vi)=Γ (Γ (vi)), V´ı du. 1.4.1. X´et d¯ˆo` thi. G trong H`ınh 1.19. Ma trˆa.nkˆe` cu˙’ a G l`a v1 v2 v3 v4 v5 v6 v7 v1 0100100 v2 0101000   v  0001000 3    A = v4 0000100.   v  0000100 5    v6 0010001   v7 0001010 39
v1 .• . . . v • 2 v6 •. . . . . . . . . . . . . . . . . . . • • v 3 v7 • • v5 . . . . v4 . . H`ınh 1.19: . . . . C´actˆa.p pha.m vi c´othˆe˙’ x´acd¯i.nh t`u Phuong tr`ınh(1.1) nhu sau R(v1)={v1}∪{v2,v5}∪{v2,v4,v5}∪{v2,v4,v5} = {v1,v2,v4,v5}, R(v2)={v2}∪{v2,v4}∪{v2,v4,v5}∪{v2,v4,v5} = {v2,v4,v5}, R(v3)={v3}∪{v4}∪{v5}∪{v5} = {v3,v4,v5}, R(v4)={v4}∪{v5}∪{v5} = {v4,v5}, R(v5)={v5}∪{v5} = {v5}, R(v6)={v6}∪{v3,v7}∪{v4,v6}∪{v3,v5,v7}∪{v4,v5,v6} = {v3,v4,v5,v6,v7}, R(v7)={v7}∪{v4,v6}∪{v3,v5,v7}∪{v4,v5,v6} = {v3,v4,v5,v6,v7}. 40
Do d¯´oma trˆa.n pha.mvic´oda.ng v1 v2 v3 v4 v5 v6 v7 v1 1101100 v2 0101100   v  0011100 3    R = v4 0001100.   v  0000100 5    v6 0011111   v7 0011111 . Cˆa`nch´u´yrˇa`ng, do R v`a Q l`ac´acma trˆa.n Bool, mˆo˜i h`angcu˙’ ach´ung c´othˆe˙’ luu . . . da.ng mˆo.t hoˇa.chonmˆo.tt`u (word). Viˆe.c t`ımc´acma trˆa.n n`ayl`amˆo.t t´ınhto´and¯on gia˙’ n . do chı˙’ du. a v`aoc´acph´epto´anlogic. . . . . T`u d¯ i .nh ngh˜ıa, R(vi) ∩ Q(vj) l`atˆa.p c´acd¯ı˙’ nh vk m`ac´o´ıtnhˆa´tmˆo.td¯u`ong d¯it`u vi d¯ ˆe´n vj qua d¯ı˙’ nh vk. C´acd¯ı˙’ nh n`aygo.il`acˆo´tyˆe´u.Tˆa´tca˙’ c´acd¯ı˙’ nh vk ∈/ R(vi) ∩ Q(vj) . . . . . . go.il`akhˆongcˆo´tyˆe´u hay du th`ua do bo˙’ ch´ung d¯ikhˆonga˙’ nh huo˙’ ng d¯ˆe´n c´acd¯u`ong d¯i . t`u vi d¯ ˆe´n vj. C´acma trˆa.n R v`a Q d¯ i .nh ngh˜ıa trˆenl`atuyˆe.td¯ˆo´i theo ngh˜ıa sˆo´ c´accung trˆen . . . . . . d¯ u `ong d¯it`u vi d¯ ˆe´n vj khˆongbi. ha.n chˆe´.Mˇa.t kh´acta c˜ung c´othˆe˙’ d¯ i .nh ngh˜ıatuong tu. . . . . . . . . . c´acma trˆa.n n`ayv´oisˆo´ cung trˆend¯u`ong d¯ikhˆongvuo. t qu´amˆo.tsˆo´ cho tru´oc. V´oimo˙’ . . . . rˆo.ng n`ayta c˜ung c´othˆe˙’ t´ınhd¯uo. c c´acma trˆa.nha.n chˆe´ theo luo. cd¯ˆo` trˆen. . . D- `ˆo thi. d¯ u o. cgo.il`abˇa´ccˆa`u nˆe´utˆo`nta.i c´accung (vi,vj)v`a(vj,vk)th`ıc˜ung tˆo`nta.i 0 cung (vi,vk). Bao d¯´ongbˇa´ccˆa`u cu˙’ ad¯ˆo` thi. G =(V,E) l`ad¯ˆo` thi. Gtc =(V,E ∪ E ) trong 0 . . . d¯ ´o E l`ac´accung d¯uo. c thˆemv`ao´ıtnhˆa´td¯ˆe˙’ d¯` ˆo thi. Gtc c´ot´ınh bˇa´ccˆa`u. Dˆ˜e d`angch´ung minh rˇa`ng ma trˆa.nkˆe` cu˙’ ad¯ˆo` thi. Gtc ch´ınh l`ama trˆa.n pha.mviR v`abˇa`ng A + A2 + ···+ Ap, (p ≤ n − 1), trong d¯´o A l`ama trˆa.nkˆe` cu˙’ a G. (Ta.i sao?) 41
1.4.2 T`ımc´acth`anhphˆa` n liˆenthˆongma.nh . . Th`anhphˆa`n liˆenthˆongma.nh d¯i.nh ngh˜ıa trong phˆa`n tru´oc l`ad¯ˆo` thi. con liˆenthˆongma.nh . . . l´on nhˆa´t trong G. V`ıv´oid¯ˆo` thi. liˆenthˆongma.nh, v´oimo.icˇa.pd¯ı˙’ nh vi,vj, luˆonluˆontˆo`n . . . . . ta.imˆo.td¯u`ong d¯it`u d¯ ı ˙’ nh vi d¯ ˆe´nd¯ı˙’ nh vj v`anguo.cla.i, nˆentˆo`nta.i duy nhˆa´tmˆo.t th`anh . . . phˆa`n liˆenthˆongma.nh ch´uamˆo.td¯ı˙’ nh cho tru´o cv`avi s˜exuˆa´thiˆe.n trong tˆa.p c´acd¯ı˙’ nh cu˙’ amˆo.t v`achı˙’ mˆo.t th`anhphˆa`n liˆenthˆongma.nh. Khˇa˙’ ng d¯i.nh n`ayl`ahiˆe˙’n nhiˆen(ta.i sao?). . . . . Nˆe´ud¯ı˙’ nh vi d¯ u o. c coi v`ua l`axuˆa´t ph´atv`ual`akˆe´tth´uc th`ıtˆa.p c´acd¯ı˙’ nh cˆo´tyˆe´u . . . . . . tuong ´ung v´oi hai d¯ı˙’ nh tr`ung nhau n`ay(t´uc l`atˆa.p c´acd¯ı˙’ nh thuˆo.cma.ch n`aod¯´och´ua . . . . vi) x´acd¯i.nh bo˙’ i R(vi) ∩ Q(vi). V`ıtˆa´tca˙’ c´acd¯ı˙’ nh cˆo´tyˆe´u n`ayc´othˆe˙’ d¯ ˆe´nt`u vi v`anguo. c . . . . . la.inˆench´ung c˜ung c´othˆe˙’ d¯ ˆe´nd¯uo. c c´acd¯ı˙’ nh kh´actrong tˆa.p n`ayv`anguo. cla.i. Hon . n˜ua, dˆe˜ thˆa´yrˇa`ng tˆa.p R(vi) ∩ Q(vi) x´acd¯i.nh c´acd¯ı˙’ nh cu˙’ a th`anhphˆa`n liˆenthˆongma.nh . . . . duy nhˆa´ttuong ´ung v´oid¯ı˙’ nh vi. Nˆe´u ta loa.i c´acd¯ı˙’ nh n`aykho˙’ id¯ˆo` thi. G =(V,Γ) th`ıc´othˆe˙’ ´apdu.ng t`ımth`anh . . 0 . phˆa`n liˆenthˆongma.nh trˆend¯ˆo` thi. con nhˆa.nd¯uo. c G v´oitˆa.pd¯ı˙’ nh V \ (R(vi) ∩ Q(vi)). . . Qu´atr`ınhn`aylˇa.pla.i cho d¯ˆe´n khi tˆa´tca˙’ c´acth`anhphˆa`nliˆen thˆongma.nh d¯uo. c t`ım. . . Kˆe´tth´uc ta c´od¯ˆo` thi. G d¯ u o. c phˆanhoa. ch th`anhc´acth`anhphˆa`n liˆenthˆongma.nh. V´ı du. 1.4.2. X´et d¯ˆo` thi. trong H`ınh 1.20. Ch´ung ta h˜ayt`ımth`anhphˆa`nliˆen thˆong . ma.nh ch´uad¯ı˙’ nh v1. T`u. c´acphu.o.ng tr`ınh(1.1) v`a(1.2) ta c´o R(v1)={v1,v2,v4,v5,v6,v7,v8,v9,v10} v`a Q(v1)={v1,v2,v3,v5,v6}. . Do d¯´oth`anhphˆa`n liˆenthˆongma.nh ch´uad¯ı˙’ nh v1 l`ad¯ˆo` thi. con hR(v1) ∩ Q(v1)i = h{v1,v2,v5,v6}i. . . . . . Tu ong tu. , th`anhphˆa`n liˆenthˆongma.nh ch´uad¯ı˙’ nh v8 l`ad¯ˆo` thi. con h{v8,v10}i, ch´ua . . d¯ ı ˙’ nh v7 l`ad¯ˆo` thi. con h{v4,v7,v9}i, ch´uad¯ı˙’ nh v11 l`ad¯ˆo` thi. con h{v11,v12,v13}i, v`ach´ua . . d¯ ı ˙’ nh v3 l`ad¯ˆo` thi. con h{v3}i. D- `ˆo thi. thu go.n Gr d¯ u o. c cho trong H`ınh 1.21. 42
v1 v6 v10 v11 • . • . •. . •. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • v . . 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • •. • . . . . . . v2 v5 . v8 . v12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •• . • v9 . . v v . 3 7 . . . . . . . . . . . . . . . . . . . .• v4 H`ınh 1.20: D- `ˆo thi. G. . . C´acph´ep to´and¯uo. c miˆeuta˙’ trˆend¯ˆe˙’ t`ımc´acth`anhphˆa`nliˆen thˆongma.nh cu˙’ a . . . mˆo.td¯ˆo` thi. c˜ung c´othˆe˙’ su˙’ du.ng tru. ctiˆe´pd¯ˆo´iv´oi c´acma trˆa.n R v`a Q d¯ i .nh ngh˜ıaphˆa`n . . . . . tru´oc. Do d¯´onˆe´utak´yhiˆe.u R ⊗ Q c´ongh˜ıa l`ama trˆa.n nhˆa.nd¯uo. ct`u R v`a Q bˇa`ng . . . . . c´ach nhˆanc´acphˆa`ntu˙’ tuong ´ung th`ıphˆa`ntu˙’ (R ⊗ Q)ij = rij qij bˇa`ng 1 nˆe´utˆo`nta.i . . . . . . . . d¯ u `ong d¯it`u vi d¯ ˆe´n vj v`abˇa`ng 0 trong tru`ong ho. p nguo. cla.i. Do d¯´ohai d¯ı˙’ nh thuˆo.c . . . c`ung mˆo.t th`anhphˆa`n liˆenthˆongma.nh nˆe´u v`achı˙’ nˆe´u c´ach`ang(hoˇa.ccˆo.t) tuong ´ung . . . . . . bˇa`ng nhau. C´acd¯ı˙’ nh m`ah`angtuong ´ung ch´uamˆo.t phˆa`ntu˙’ 1o˙’ cˆo.t vj ta.o th`anhtˆa.p . d¯ ı ˙’ nh cu˙’ a th`anhphˆa`n liˆenthˆongma.nh ch´ua vi. Hiˆe˙’n nhiˆenrˇa`ng c´othˆe˙’ biˆe´nd¯ˆo˙’i ma trˆa.n . . R ⊗ Q bˇa`ng ph´epho´anvi. c´ach`angv`ac´accˆo.t sao cho ma trˆa.nthud¯uo. cc´oda.ng khˆo´i . . . . ch´eo; mˆo˜i ma trˆa.n con ch´eo tuong ´ung v´oimˆo.t th`anhphˆa`n liˆenthˆongma.nh cu˙’ a G v`a . . . . . c´oc´acphˆa`ntu˙’ bˇa`ng 1, c´acphˆa`ntu˙’ kh´acbˇa`ng 0. V´oiv´ıdu. trˆen,ma trˆa.n R ⊗ Q d¯ u o. c 43
∗ ∗ v1 = {v1,v2,v5,v6} v2 = {v8,v10} • • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∗ . • { } . v = v11,v12,v13 . . 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • ∗ ∗ v5 = {v3} v3 = {v4,v7,v9} H`ınh 1.21: D- `ˆo thi. thu go.n Gr. sˇa´pxˆe´pla.ic´oda.ng v1 v2 v5 v6 v8 v10 v4 v7 v9 v11 v12 v13 v3 v1  1111  v2  1111      v5  1111    v  1111  6     v8  11    v  11  10    R ⊗ Q = v4  111 .   v  111  7     v9  111    v  111  11    v12 111    v  111  13    v3 1 1.4.3 Co. so˙’. . . Tˆa.p B c´acd¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. cmo.id¯ı˙’ nh cu˙’ ad¯ˆo` thi. v`anho˙’ nhˆa´t theo ngh˜ıa khˆongc´o . . . . tˆa.p con thu. csu. n`aocu˙’ a n´oc´ot´ınhchˆa´t n`aygo.il`aco so˙’ . Do d¯´onˆe´u ta viˆe´t R(B)l`a 44
tˆa.p pha.mvicu˙’ a B : R(B)=∪vi∈BR(vi), th`ı B l`aco. so˙’. nˆe´uv`achı˙’ nˆe´u 1. B(V )=V ;v`a . 2. v´oimo.itˆa.p con S ⊂ B th`ı R(S) =6 V. . . . . . . . D- iˆe` ukiˆe.nth´u hai tuong d¯uong v´oid¯iˆe` ukiˆe.n vj ∈/ R(vi)v´oi hai d¯ı˙’ nh phˆanbiˆe.t vi,vj ∈ B; . . . . t´uc l`amˆo.td¯ı˙’ nh thuˆo.c B khˆongthˆe˙’ d¯ ˆe´nd¯uo. ct`u mˆo.td¯ı˙’ nh kh´actrong B. D- iˆe` u n`ayc´o thˆe˙’ ch´u.ng minh nhu. sau: . 0 0 Do v´oi hai tˆa.p con H v`a H ⊂ H ta c´o R(H ) ⊂ R(H)nˆen d¯iˆe` ukiˆe.n R(S) =6 V . . . . . . . v´oimo.i S ⊂ B tuong d¯uong v´oi R(B \{vj}) =6 V v´oimo.i vj ∈ B. N´oic´ach kh´ac, . R(vj) 6⊂ R(B \{vj}). Nhung d¯iˆe` ukiˆe.n n`aytho˙’ a m˜annˆe´uv`achı˙’ nˆe´u vj ∈/ R(B \{vj}), . . t´ucl`avj ∈/ R(vi)v´oimo.i vi,vj ∈ B. . . Vˆa.y, co so˙’ l`amˆo.ttˆa.p B c´acd¯ı˙’ nh tho˙’ a m˜anhai d¯iˆ`eukiˆe.n sau: . . . 1. tˆa´tca˙’ c´acd¯ı˙’ nh cu˙’ a G c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u d¯ ı ˙’ nh n`aod¯´ocu˙’ a B;v`a . . . 2. khˆongd¯ı˙’ nh n`aotrong B c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u mˆo.td¯ı˙’ nh thuˆo.c B. . T`u hai d¯iˆe` ukiˆe.n n`ayta suy ra . . Mˆe.nh d¯ˆe` 1.4.3. (a) Khˆongtˆo`nta. i hai d¯ı˙’ nh trong co so˙’ B sao cho ch´ung thuˆo. cc`ung mˆo. t th`anhphˆa`n liˆenthˆongma. nh cu˙’ a G. . . (b) D- `ˆo thi. khˆongma. ch c´oduy nhˆa´tmˆo. tcoso˙’ gˆo`mtˆa. p c´acd¯ı˙’ nh c´obˆa. c trong bˇa`ng khˆong. . . . Ch´ung minh. Suy tru. ctiˆe´pt`u d¯ i .nh ngh˜ıa. / Theo mˆe.nh d¯ˆ`e trˆenv`ado d¯ˆo` thi. thu go.n Gr cu˙’ ad¯ˆo` thi. G khˆongc´oma.ch nˆen tˆa.p . . . . co so˙’ Br cu˙’ a Gr l`atˆa.p c´acd¯ı˙’ nh c´obˆa.c trong bˇa`ng khˆong.C´actˆa.pcoso˙’ cu˙’ a G c´othˆe˙’ 45
. x´acd¯i.nh du. a v`ao Br. Cu. thˆe˙’ l`anˆe´u Br = {S1,S2, ,Sk}, trong d¯´o k l`asˆo´ c´actˆa.pd¯ı˙’ nh . . { } . ∈ Sj trong co so˙’ Br cu˙’ a Gr, th`ı B l`atˆa.pda.ng vi1 ,vi2 , ,vik v´oi vij Sj,j =1, 2, ,k. . . . V´ı du. 1.4.4. V´oid¯ˆo` thi. trong H`ınh 1.20, d¯ˆo` thi. thu go.n trong H`ınh 1.21. Co so˙’ cu˙’ a ∗ ∗ ∗ ∗ d¯` ˆo thi. n`ayl`a {v4,v5} do v4 v`a v5 l`ahai d¯ı˙’ nh duy nhˆa´tcu˙’ a G c´obˆa.c trong bˇa`ng khˆong. . . Suy ra c´actˆa.pcoso˙’ cu˙’ a G l`a {v3,v11}, {v3,v12} v`a {v3,v13.} . . . . . D- ˆo´i ngˆa˜uv´oi kh´ainiˆe.mcoso˙’ c´othˆe˙’ d¯ i .nh ngh˜ıatheo thuˆa.tng˜u cu˙’ a c´actˆa.pho. p . Q(vi)nhusau. . . D- ˆo´icoso˙’ l`atˆa.p B¯ c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. G =(V,Γ) tho˙’ a m˜an ¯ Q(B)= [ Q(vi)=V, vi∈B ∀S ⊂ B,Q¯ (S) =6 V. . . . . T´ucl`aB¯ l`atˆa.p nho˙’ nhˆa´t c´acd¯ı˙’ nh c´othˆe˙’ d¯ ˆe´nd¯uo. ct`u c´acd¯ı˙’ nh kh´ac.C´act´ınhchˆa´t . . . . . . . . cu˙’ a B¯ tuong tu. v´oicu˙’ a B trong d¯´oc´ackh´ainiˆe.mvˆe` hu´o ng d¯uo. c thay bˇa`ng ba˙’ n sao . . nguo. cla.i. . . Do vˆa.y, d¯ˆo´icoso˙’ cu˙’ ad¯ˆo` thi. thu go.n Gr l`atˆa.p c´acd¯ı˙’ nh cu˙’ a Gr c´obˆa.c ngo`aibˇa`ng . . . . . . . . . . . khˆong,v`at`u d¯´ota c´othˆe˙’ nhˆa.nd¯uo. cd¯ˆo´icoso˙’ cu˙’ a G tuong tu. nhu d¯˜athu. chiˆe.no˙’ trˆen. . Trong v´ıdu. cu˙’ ad¯ˆo` thi. G trong H`ınh 1.20, d¯ˆo` thi. thu go.n Gr chı˙’ ch´uamˆo.td¯ı˙’ nh ∗ . . ∗ . . . v3 c´obˆa.c ngo`aibˇa`ng khˆong.Do d¯´od¯ˆo´icoso˙’ cu˙’ a Gr l`a {v3} v`abo˙’ ivˆa.yd¯ˆo´icoso˙’ cu˙’ a G l`a {v4}, {v7} v`a {v9}. . Ap´ du. ng trong cˆa´utr´uc tˆo˙’ ch´uc . . . . Nˆe´ud¯ˆo` thi. biˆe˙’udiˆ˜encˆa´utr´uc a˙’ nh huo˙’ ng cu˙’ amˆo.ttˆo˙’ ch´uc th`ıc´acphˆa`ntu˙’ cu˙’ amˆo.t . . . . . th`anhphˆa`n liˆenthˆongma.nh cu˙’ a G c´oa˙’ nh huo˙’ ng v`ach´uc nˇangngang nhau. Mˆo.tcoso˙’ . . . cu˙’ a G c´othˆe˙’ hiˆe˙’u l`amˆo.t “liˆen minh” c´osˆo´ ngu`o i ´ıtnhˆa´tnhung l˜anhd¯a.omo.i c´anhˆan trong tˆo˙’ ch´u.c. . 0 Trˆentˆa.p c´acd¯ı˙’ nh biˆe˙’udiˆe˜n c´acth`anhviˆen cu˙’ ac`ung tˆo˙’ ch´uc, ta x´etd¯ˆo` thi. G . . . d¯ u o.c xˆaydu. ng d¯ˆe˙’ biˆe˙’udiˆe˜n c´ackˆenh truyˆe` n thˆongsao cho tˆo`nta.i cung (vi,vj)nˆe´u vi 46
. 0 . . . c´othˆe˙’ giao tiˆe´pv´oi vj. D- `ˆo thi. G d˜ınhiˆenc´oliˆen quan v´oi G. Sˆo´ ngu`oi ´ıtnhˆa´t m`abiˆe´t . . . . 0 hoˇa.c c´othˆe˙’ nhˆa.ntˆa´tca˙’ c´acsu. kiˆe.nvˆe` tˆo˙’ ch´ucta.o th`anhmˆo.td¯ˆo´icoso˙’ cu˙’ a G . Ta c´o . . . . thˆe˙’ n´oirˇa`ng mˆo.tliˆen minh hiˆe.u qua˙’ d¯ ˆe ˙’ l˜anhd¯a.otˆo˙’ ch´ucl`atˆa.p H nh˜ung ngu`o i tho˙’ a m˜an: H = B(G) ∪ B¯(G0), 0 . . . . 0 . . trong d¯´o B(G)v`aB¯(G ) l`amˆo.t trong c´acco so˙’ v`ac´acd¯ˆo´icoso˙’ cu˙’ a G v`a G tuong . . . u´ng d¯uo. ccho.n sao cho #H nho˙’ nhˆa´t. . . . Kˆe´ tiˆe´px´etco so˙’ lu˜yth`ua l`atˆa.p c´acd¯ı˙’ nh Bp ⊂ V sao cho R(Bp)=V, Q(Bp)=Bp, R(S) =6 V, ∀S ⊂ Bp. . . . . . D- iˆe` ukiˆe.nth´u hai ngh˜ıa l`achı˙’ nh˜ung ngu`oibˆen trong Bp m´oi c´othˆe˙’ c´oa˙’ nh . . . . . . . . huo˙’ ng d¯ˆe´n ngu`oi kh´acc˜ung trong Bp v`ac´othˆe˙’ thay bˇa`ng d¯iˆ`eukiˆe.ntuong d¯uong: R(V \ Bp) ∩ Bp = ∅. D- iˆe` ukiˆe.n n`aychı˙’ ra rˇa`ng nˆe´umˆo.td¯ı˙’ nh trong th`anhphˆa`nliˆen thˆongma.nh cu˙’ a G thuˆo.c Bp th`ımo.id¯ı˙’ nh kh´actrong c`ung th`anhphˆa`n liˆenthˆongma.nh . . n`ayc˜ung thuˆo.c Bp. Do tˆa.pcoso˙’ cu˙’ a Gr l`atˆa.p c´acd¯ı˙’ nh c´obˆa.c trong bˇa`ng khˆongnˆen . . . tˆa.pcoso˙’ l˜uy th`uacu˙’ a G ch´ınh l`a Bp = [ Si. ∗ Si∈B . . . Chˇa˙’ ng ha.nd¯ˆo` thi. trong H`ınh 1.20 c´oco so˙’ l˜uy th`ual`a{v3,v11,v12,v13}. Cˆa`nch´u . . . . . . yrˇa´ `ng, nˆe´ud¯ˆo` thi. n`aytuong ´ung mˆo.ttˆo˙’ ch´ucth`ıv3 c´othˆe˙’ xem l`angu`o i l˜anhd¯a.o cao ∗ ∗ ∗ nhˆa´tcu˙’ a c´acnh´om v1,v2 v`a v3. 1.5 D- ˇa˙’ ng cˆa´ucu˙’ ac´ac d¯ˆo` thi. . . Ta d¯˜abiˆe´trˇa`ng c`ung mˆo.td¯ˆo` thi. c´othˆe˙’ d¯ u o. cbiˆe˙’udiˆe˜nbˇa`ng nhiˆe` u h`ınhv˜ekh´acnhau. . . . . . Viˆe.c nhˆa.nbiˆe´td¯uo. c trong tru`ong ho. p n`aohai h`ınh v˜ebiˆe˙’udiˆe˜nc`ung mˆo.td¯ˆo` thi., trong . . . . tru`ong ho. p n`aobiˆe˙’udiˆe˜n hai d¯ˆo` thi. kh´acnhau, l`amˆo.tvˆa´nd¯ˆ`e khˆongd¯on gia˙’ n. . . R˜or`angl`ahai h`ınhcho tru´o cbiˆe˙’udiˆe˜nc`ung mˆo.td¯ˆo` thi. chı˙’ khi c´acd¯iˆ`eukiˆe.n sau . . d¯ˆayd¯uo. c tho˙’ a m˜an: 47
1. Sˆo´ d¯ ı ˙’ nh bˇa`ng nhau; 2. Sˆo´ ca.nh bˇa`ng nhau; 3. Sˆo´ d¯ ı ˙’ nh c`ung bˆa.cbˇa`ng nhau. . D- ´o l `a n hu ˜ ng d¯iˆ`eukiˆe.ncˆa`n: hai h`ınh khˆongtho˙’ a m˜anmˆo.t trong c´acd¯iˆ`eukiˆe.nd¯´o . th`ıkhˆongbiˆe˙’udiˆe˜nc`ung mˆo.td¯ˆo` thi Nhung ch´ung c˜ung khˆongpha˙’ il`ad¯iˆ`eukiˆe.nd¯u˙’ (h˜aycho v´ıdu.). Hiˆe˙’n nhiˆenrˇa`ng D- .inh l´y 1.5.1. D- iˆe` ukiˆe. ncˆa`n v`ad¯u˙’ d¯ ˆe ˙’ hai h`ınhbiˆe˙’udiˆe˜n c`ungmˆo. td¯ˆo` thi. l`atˆo`nta. i . . . . mˆo. ttuong ´ung mˆo. t-mˆo. t lˆengi˜ua c´acd¯ı˙’ nh cu˙’ a hai h`ınhsao cho nˆe´u hai d¯ı˙’ nh cu˙’ a h`ınh . . . . . . . . . n`ayd¯uo. cnˆo´ibo˙’ imˆo. tca. nh th`ıhai d¯ı˙’ nh tuong ´ung cu˙’ a h`ınhkia c˜ung d¯uo. cnˆo´iv´oi . . . nhau bo˙’ imˆo. tca. nh v`anguo. cla. i. . Viˆe.ct`ımmˆo.t tiˆeuchuˆa˙’nd¯on gia˙’ nv`ahiˆe.u qua˙’ d¯ ˆe ˙’ ph´athiˆe.n t´ınhd¯ˇa˙’ ng cˆa´ucu˙’ a c´ac . . . . d¯` ˆo thi. vˆa˜n l`ab`aito´anmo˙’ cu˙’ a l´ythuyˆe´td¯ˆo` thi. v`ad¯angc`ond¯uo.ctiˆe´ptu.c nghiˆen c´uu. 1.5.1 1−d¯ ˇa˙’ ng cˆa´u . . D- `ˆo thi. c´oc´acd¯iˆe˙’m kh´opgˆo`m ´ıtnhˆa´t hai d¯ˆo` thi. con khˆongc´od¯iˆe˙’m kh´op. Mˆo˜id¯ˆo` thi. . . con liˆen thˆongl´on nhˆa´t khˆongc´od¯iˆe˙’m kh´opgo.il`akhˆo´i. D- `ˆo thi. trong H`ınh 1.22 c´onˇam . . khˆo´i (v`aba d¯iˆe˙’m kh´op a, b v`a c). Ch´u´yrˇa`ng d¯ˆo` thi. liˆenthˆongkhˆongc´od¯iˆe˙’m kh´opchı˙’ c´omˆo.t khˆo´i. • •. • . . . . . . . . . . . a c . . b . . . . • •. • • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . • • . . . . . . . . . . •. H`ınh 1.22: So s´anhd¯ˆo` thi. khˆongliˆen thˆongtrong H`ınh 1.23 v`ad¯ˆo` thi. trong H`ınh 1.22. Hiˆe˙’n . nhiˆenhai d¯ˆo` thi. n`aykhˆongd¯ˇa˙’ ng cˆa´u(ch´ung c´osˆo´ d¯ ı ˙’ nh kh´acnhau); nhung ch´ung c´o 48
. mˆo´i liˆenhˆe. l`ac´ackhˆo´i trong H`ınh 1.22 d¯ˇa˙’ ng cˆa´uv´oi c´acth`anhphˆa`ncu˙’ ad¯ˆo` thi. trong . H`ınh 1.23. C´acd¯ˆo` thi. n`aygo.il`a1-d¯ˇa˙’ ng cˆa´u.Ch´ınh x´achon: . D- .inh ngh˜ıa1.5.2. Hai d¯ˆo` thi. G1 v`a G2 go.il`a1−d¯ ˇa˙’ ng cˆa´u nˆe´uch´ung tro˙’ th`anhd¯ˇa˙’ ng . cˆa´uv´oi nhau sau khi ´apdu. ng mˆo.tsˆo´ lˆa`n ph´epto´ansau: . Ph´epto´an1. “T´ach” mˆo.td¯iˆe˙’m kh´op th`anhhai d¯ı˙’ nh d¯ˆe˙’ ta.o th`anhhai d¯ˆo` thi. con khˆongc´od¯iˆe˙’m kh´o.pr`o.i nhau. y • • • . . . . . . . . . . a1 . . b. 1 . . . . . . . • • •. ••• • . . . . . . . a3 . b2 c1 c2 . . . . . . . . . . . . • a2 •. • • . . . x . . . . . . . . . . . . . . . . . . . . •. H`ınh 1.23: . . T`u d¯ i .nh ngh˜ıasuy ra rˇa`ng hai d¯ˆo` thi. khˆongc´od¯iˆe˙’m kh´op l`a1-d¯ˇa˙’ ng cˆa´unˆe´uv`a chı˙’ nˆe´uch´ung d¯ˇa˙’ ng cˆa´u. D- iˆe` ug`ıs˜exa˙’ y ra khi ta nˆo´i hai th`anhphˆa`ncu˙’ aH`ınh 1.23 bˇa`ng c´ach “d´an”hai . . d¯ ı ˙’ nh (chˇa˙’ ng ha.n x v`a y)? Ch´ung ta nhˆa.nd¯uo. cd¯ˆo` thi. trong H`ınh 1.24. . Hiˆe˙’n nhiˆenc´acd¯ˆo` thi. trong H`ınh 1.24 l`a1−d¯ ˇa˙’ ng cˆa´uv´oid¯ˆo` thi. trong H`ınh 1.23. . V`ı c´ackhˆo´icu˙’ ad¯ˆo` thi. trong H`ınh 1.24 d¯ˇa˙’ ng cˆa´uv´oi c´ackhˆo´icu˙’ ad¯ˆo` thi. trong H`ınh 1.22, nˆen hai d¯ˆo` thi. n`ayl`a1−d¯ ˇa˙’ ng cˆa´u. Do d¯´oba d¯ˆo` thi. trong c´acH`ınh 1.22, 1.23 v`a 1.24 l`ad¯ˆoimˆo.t1−d¯ ˇa˙’ ng cˆa´u. 49
•. • . . . . . . . . . a . 1 . . . . . . • ••• • . . . . c1 c2 . b2 . . . . . . . xy • a2 •. • . . . . . . . . . b1 . . . • •. . . . . . . . a3 . . . . . . . . . . . . . . . • •. H`ınh 1.24: 1.5.2 2−d¯ ˇa˙’ ng cˆa´u Trong phˆa`n trˆench´ung ta d¯˜atˆo˙’ng qu´ath´oakh´ainiˆe.md¯ˇa˙’ ng cˆa´ubˇa`ng kh´ainiˆe.m1−d¯ ˇa˙’ ng . . . . cˆa´u. C´acd¯ˆo` thi. d¯ ˇa˙’ ng cˆa´uth`ı1−d¯ ˇa˙’ ng cˆa´unhung nguo. cla.i khˆongd¯´ung. Su. tˆo˙’ng qu´at . . . h´oarˆa´th˜uu ´ıch trong viˆe.c nghiˆen c´uu c´acd¯ˆo` thi. c´od¯iˆe˙’m kh´op. . . Ch´ung ta c`onc´othˆe˙’ mo˙’ rˆo.ng kh´ainiˆe.m n`aycho c´acd¯ˆo` thi. 2−liˆenthˆongnhu sau. Trong d¯ˆo` thi. 2−liˆenthˆong G x´et hai d¯ı˙’ nh x v`a y m`ax´oach´ung (v`ac´acca.nh liˆen thuˆo.cch´ung) th`ıd¯ˆo` thi. mˆa´t t´ınhliˆen thˆong.N´oic´ach kh´ac, G gˆo`mmˆo.td¯ˆo` thi. con g1 . v`aphˆa`nb`ucu˙’ an´o¯g1 sao cho g1 v`a¯g1 c´od¯´ung hai d¯ı˙’ nh chung: x v`a y. Gia˙’ su˙’ rˇa`ng . ch´ung ta thu. chiˆe.n ph´epto´ansau trˆen G: Ph´epto´an2. “T´ach” d¯ı˙’ nh x th`anh x1 v`a x2 v`ad¯ı˙’ nh y th`anh y1 v`a y2 sao cho ta . . . . thu d¯uo.ct`u G hai th`anhphˆa`n g1 v`a¯g1. Gia˙’ su˙’ c´acd¯ı˙’ nh x1 v`a y1 thuˆo.c th`anhphˆa`n g1 . . . v`a x2 v`a y2 thuˆo.c¯g1. Bˆaygi`o nˆo´i hai d¯ˆo` thi. g1 v`a¯g1 bˇa`ng c´ach ho. p nhˆa´td¯ı˙’ nh x1 v´oi . . d¯ ı ˙’ nh y2 v`ad¯ı˙’ nh x2 v´oid¯ı˙’ nh y1. (Hiˆe˙’n nhiˆenc´acca.nh m`aliˆenthuˆo.cv´oi x hoˇa.c y trong . . . . . . . . G d¯ i cung ` v´oi g1 hoˇa.c¯g1, khˆonga˙’ nh huo˙’ ng d¯ˆe´nd¯ˆo` thi. thu d¯uo. co˙’ bu´oc cuˆo´i). . Hai d¯ˆo` thi. go.il`a2−d¯ ˇa˙’ ng cˆa´u nˆe´uch´ung tro˙’ th`anhd¯ˇa˙’ ng cˆa´u sau Ph´epto´an1 hoˇa.c . Ph´epto´an2, hoˇa.cca˙’ hai ph´epto´ansau mˆo.tsˆo´ lˆa`n thu. chiˆe.n. H`ınh 1.25 chı˙’ ra hai d¯ˆo` thi. trong H`ınh 1.25(a) v`a(d) l`a2−d¯ ˇa˙’ ng cˆa´u. Ch´u´yrˇa`ng trong H`ınh 1.25(a), bˆa.ccu˙’ a d¯ ı ˙’ nh x bˇa`ng bˆo´n, c`ontrong H`ınh 1.25(d) khˆongc´od¯ı˙’ nh n`aobˆa.cbˆo´n. . . . . . T`u d¯ i .nh ngh˜ıa, suy ra 1−d¯ ˇa˙’ ng cˆa´ul`a2−d¯ ˇa˙’ ng cˆa´u, nhung nguo. cla.ichuachˇa´c 50
x x1 x2 • •. • • •. . . . . . . . . . . . . . . . . . . . . • . • . . . . . . . . . . . . . g¯1 . . . . . . . . . g1 . . . . . . . . . . . . . . . . . •• • •• y y1 y2 (a) (b) x1 x2 . • • •. • •. . . . . . . . . . . . . . . . . . . . . g1 . . . . . . . . . . . . . g¯1 . . . . . . . . . • . • . . . . . . . . . . . . . . . . . • •• •• y1 y2 (c) (d) H`ınh 1.25: . . d¯ung. ´ Tuy nhiˆen,v´oi c´acd¯ˆo` thi. k−liˆenthˆongv´oi k ≥ 3 th`ıba kh´ainiˆe.md¯ˇa˙’ ng cˆa´u, . 1−d¯ ˇa˙’ ng cˆa´uv`a2−d¯ ˇa˙’ ng cˆa´u l`anhu nhau (ta.i sao?). Tu.o.ng ´u.ng chu tr`ınh . . . Hai d¯ˆo` thi. G1 v`a G2 go.i l`acho mˆo.t tuong ´ung chu tr`ınh nˆe´uch´ung tho˙’ ad¯iˆe` ukiˆe.n sau: . . . . . . . . Tˆo`nta.ituong ´ung mˆo.t-mˆo.tgi˜ua c´acca.nh cu˙’ a G1 v`a G2 v`amˆo.ttuong ´ung gi˜ua c´ac . . . chu tr`ınhcu˙’ a G1 v`a G2 sao cho mˆo.t chu tr`ınhtrong G1 d¯ u o. cta.obo˙’ i c´acca.nh cu˙’ a G1 . . . . . . . . . c´omˆo.t chu tr`ınhtuong ´ung trong G2 d¯ u o. cta.obo˙’ i c´acca.nh tuong ´ung trong G2, v`a . . . . . . nguo. cla.i. T`u d¯ i .nh ngh˜ıasuy ra c´acd¯ˆo` thi. d¯ ˇa˙’ ng cˆa´uc´otuong ´ung chu tr`ınh. . V`ı trong d¯ˆo` thi. c´od¯iˆe˙’m kh´op G, mˆo˜i chu tr`ınhthuˆo.cmˆo.t khˆo´i n`aod¯´o,nˆen mˆo˜i . . . . chu tr`ınhtrong G vˆa˜ntuong ´ung c´acca.nh cu˙’ a n´okhi thu. chiˆe.n Ph´epto´an1 trˆen G. . . . Do d¯´o,c´acd¯ˆo` thi. 1−d¯ ˇa˙’ ng cˆa´u c´ot´ınhchˆa´ttuong ´ung chu tr`ınh. . . . . Tu ong tu. , x´etchu tr`ınh µ trong d¯ˆo` thi. G sau khi thu. chiˆe.n Ph´epto´an2 trˆen G. 51
. . . . V´oi chu tr`ınh µ, ta c´oba tru`ong ho. pxa˙’ y ra: 1. C´acca.nh thuˆo.c µ nˇa`m ho`anto`antrong g1; hoˇa.c 2. C´acca.nh thuˆo.c µ nˇa`m ho`anto`antrongg ¯1; hoˇa.c . . . 3. C´acca.nh thuˆo.c µ nˇa`m trong ca˙’ hai d¯ˆo` thi. con g1 v`a¯g1; v`atrong tru`ong ho. p n`ay µ pha˙’ ich´u.aca˙’ hai d¯ı˙’ nh x v`a y. . . . . . Trong c´acTru`ong ho. p 1 v`a2, chu tr`ınh µ khˆonga˙’ nh huo˙’ ng qua Ph´epto´an2. Trong . . . . . Tru `ong ho. p3,µ vˆa˜ngˆo`m c´acca.nh c˜u, ngoa.itr`u dˆaychuyˆe` ngi˜ua c´acd¯ı˙’ nh x v`a y trong . . g1 (thuˆo.c chu tr`ınh µ)bi. “d¯a˙’ o nguo. cla.i”. Do d¯´o,mˆo˜i chu tr`ınhsau Ph´epto´an2 vˆa˜n . . . . gˆo`mch´ınh nh˜ung ca.nh c˜u. Suy ra c´acd¯ˆo` thi. 2−d¯ ˇa˙’ ng cˆa´uc˜ung c´ot´ınhchˆa´ttuong ´ung chu tr`ınh. . . . D- .inh l´y 1.5.3. Hai d¯ˆo` thi. l`a 2−d¯ ˇa˙’ ng cˆa´unˆe´u v`achı˙’ nˆe´uch´ung c´otuong ´ung chu tr`ınh. . . . . Ch´ung minh. D- iˆe` ukiˆe.nd¯u˙’ suy t`u c´acl´yluˆa.n trˆen.Ch´ung minh d¯iˆ`eukiˆe.ncˆa`n kh´ohon v`ac´othˆe˙’ xem [55]. / . . . . Nhu s˜ethˆa´y sau, c´ackh´ainiˆe.m2−d¯ ˇa˙’ ng cˆa´uv`atuong ´ung chu tr`ınhd¯´ongvai tr`o . quan tro.ng khi nghiˆenc´uud¯ˆo´i ngˆa˜ucu˙’ a c´acd¯ˆo` thi. phˇa˙’ ng. 1.6 C´ac d¯ˆo` thi. d¯ ˇa.cbiˆe.t . . . . Phˆa`n n`aygi´oi thiˆe.umˆo.tsˆo´ d¯` ˆo thi. d¯ ˇa.cbiˆe.tthu`ong gˇa.p trong c´acmˆoh`ınhthu. ctˆe´. C´ac . . d¯` ˆo thi. n`ayd¯uo. c quan tˆamnhiˆe` uv`ı: . • T`u ph´atbiˆe˙’umˆo.tsˆo´ b`aito´an; . • T`u c´act´ınhchˆa´td¯ˇa.cbiˆe.tcu˙’ ach´ung; • Phu.cvu. cho mˆo.tsˆo´ thuˆa.t to´an. 52
1.6.1 D- `ˆo thi. khˆongc´oma.ch . . . . D- ˆa y l `a d¯` ˆo thi. thu`ong gˇa.p nhˆa´t khi biˆe˙’udiˆe˜n c´acquan hˆe. th´u tu. bˆo. phˆa.n trˆenc´acphˆa`n . . . . tu˙’ :v´oimˆo.t quan hˆe. th´u tu. ≤ trˆentˆa.p V, x´et d¯ˆo` thi. G =(V,E) trong d¯´o (vi,vj) ∈ E ⇔ i ≤ j. C´acb`aito´anluˆo`ng trˆenma.ng vˆa.nta˙’ i x´etc´acd¯ˆo` thi. n`ay(c˜ung xem c´acb`aito´anlˆa.p li.ch trong [30]). 1.6.2 D- `ˆo thi. phˇa˙’ ng . . 2 . D- `ˆo thi. vˆohu´o ng G go.il`aphˇa˙’ ng nˆe´uc´othˆe˙’ biˆe˙’udiˆe˜n trˆenmˆo.tmˇa.t phˇa˙’ ng R v´oi c´ac . . . 2 . . . . . . d¯ ı ˙’ nh tuong ´ung c´acd¯iˆe˙’m phˆanbiˆe.t trˆen R v`ac´acd¯u`ong cong khˆongtu. cˇa´ttuong ´ung . . . c´acca.nh sao cho hai d¯u`o ng cong bˆa´tk`y khˆongcˇa´t nhau ngoa.itr`u ta.i c´acd¯ı˙’ nh chung. . . . . . C´acd¯ˆo` thi. phˇa˙’ ng s˜ed¯uo. c nghiˆen c´uu trong Chuong 6. . V´ı du. 1.6.1. D- `ˆo thi. trong H`ınh 1.26(a) l`aphˇa˙’ ng v`ıch´ung ta c´othˆe˙’ v˜ela.inhutrong H`ınh 1.26(b). a a . • • e •• e •• b b . . . . . . . . . . . . . . . . . . . . . . . . . •• •• d c d c (a) (b) . . H`ınh 1.26: D- `ˆo thi. (a) d¯uo. cbiˆe˙’udiˆe˜nla.i trong h`ınh(b) l`aphˇa˙’ ng. 53
Chu.o.ng 2 . C´acsˆo´ co ba˙’ ncu˙’ ad¯ˆo` thi. 2.1 Chu sˆo´ . . . . Kh´ainiˆe.mm`ach´ung ta s˜ed¯ˆ`e cˆa.po˙’ d¯ˆay khˆongphu. thuˆo.c v`aosu. d¯. i nh hu´ong: ta s˜en´oi . . . vˆ`e ca.nh ch´u khˆongpha˙’ i cung. D- ˆe ˙’ tˆo˙’ng qu´atx´et d¯ad¯ˆo` thi. vˆohu´ong G := (V,E)c´on d¯ ı ˙’ nh, m ca.nh v`a p th`anhphˆa`n liˆenthˆong.D- ˇa.t ρ(G):=n − p, ν(G):=m − ρ(G)=m − n + p. Ta go.i ν(G)l`achu sˆo´ cu˙’ ad¯ˆo` thi. G. . . V´ı du. 2.1.1. D- `ˆo thi. vˆohu´o ng G trong h`ınh 2.1 c´o n =5d¯ı˙’ nh, m =7ca.nh v`a p =1 th`anhphˆa`n liˆenthˆongnˆen c´ochu sˆo´ bˇa`ng ν(G)=m − n + p =7− 5+1=3. . . . 0 . . D- .inh l´y 2.1.2. Cho d¯ad¯ˆo` thi. vˆohu´ong G =(V,E). Gia˙’ su˙’ G l`ad¯ˆo` thi. nhˆa. nd¯uo. c . . . t`u G bˇa`ng c´achnˆo´i hai d¯ı˙’ nh a v`a b cu˙’ a G bo˙’ imˆo. tca. nh m´oi; nˆe´u a v`a b tr`ung nhau . . hoˇa. c c´othˆe˙’ nˆo´iv´oi nhau bo˙’ imˆo. t dˆaychuyˆ`encu˙’ a G th`ı ρ(G0)=ρ(G),ν(G0)=ν(G)+1; . . . . . trong tru`ong ho. p nguo. cla. i ρ(G0)=ρ(G)+1,ν(G0)=ν(G). 55
v1 • v 5 v4 •• . •. v2 . . . . . . . . . . . . . . . . . . • v3 H`ınh 2.1: . . 0 0 0 Ch´ung minh. Theo c´ach xˆaydu. ng, d¯ad¯ˆo` thi. G c´o n = n d¯ ı ˙’ nh, m = m +1ca.nh v`a gia˙’ su˙’. G0 c´o p0 th`anhphˆa`n liˆenthˆong. . 0 Nˆe´u a ≡ b hoˇa.c c´omˆo.t dˆaychuyˆe` nnˆo´i a v´oi b. Khi d¯´oph´epbiˆe´nd¯ˆo˙’i G th`anh G khˆongthay d¯ˆo˙’isˆo´ th`anhphˆa`n liˆenthˆong,t´u.cl`ap = p0. Do d¯´o ρ(G0)=n0 − p0 = n − p = ρ(G), ν(G0)=m0 − ρ(G0)=ν(G)+1. . . Nguo.cla.i, nˆe´u a =6 b v`akhˆongtˆo`nta.i dˆaychuyˆ`ennˆo´i a v`a b, th`ıdo c´ach x´acd¯i.nh G0 ta c´o p0 = p − 1. Suy ra ρ(G0)=n0 − p0 = n − (p − 1) = n − p +1=ρ(G)+1, ν(G0)=m0 − ρ(G0)=(m +1)− (ρ(G)+1)=m − ρ(G)=ν(G). / Hˆe. qua˙’ 2.1.3. ρ(G) ≥ 0 v`a ν(G) ≥ 0. . . Ch´ung minh. Thˆa.tvˆa.y, xuˆa´t ph´att`u d¯` ˆo thi. th`anhlˆa.pbˇa`ng c´acd¯ı˙’ nh cu˙’ a d¯ad¯ˆo` thi. vˆo . . . . 0 . . hu´ong G, d¯ ı ˙’ nh no. cˆolˆa.pv´oid¯ı˙’ nh kia, ta xˆaydu. ng G dˆa`ndˆa`nt`ung ca.nh mˆo.t; kho˙’ i d¯` ˆa u ta c´o ρ =0,ν = 0; mˆo˜i khi thˆemmˆo.tca.nh, th`ıhoˇa.c ρ tˇangv`al´uc d¯´o ν khˆongd¯ˆo˙’i, . . 0 hoˇa.c ν tˇangv`al´uc d¯´o ρ khˆongd¯ˆo˙’i. Nhu vˆa.y, trong qu´atr`ınhxˆaydu. ng d¯ˆo` thi. G , c´ac sˆo´ ρ v`a ν chı˙’ c´othˆe˙’ tˇang. / . D- ˆe ˙’ c´othˆe˙’ vˆa.ndu.ng nh˜ung kˆe´t qua˙’ phong ph´ucu˙’ ad¯a.isˆo´ vector trong viˆe.c nghiˆen 56
. . . . . . . . . c´uu, ngu`oi ta thu`ong d¯ˇa.ttuong ´ung mˆo˜i chu tr`ınhtrong G v´oimˆo.t vector theo c´ach sau d¯ˆay. . . . . Mˆo˜ica.nh cu˙’ a d¯ad¯ˆo` thi. G d¯` ˆe ud¯uo. cd¯i.nh hu´ong mˆo.t c´ach t`uy ´y;nˆe´u chu tr`ınh µ . . . . . . d¯iqua ca.nh ek,rk lˆa`n thuˆa.nhu´o ng v`a sk lˆa`n nguo. chu´ong th`ıta d¯ˇa.t ck := rk − sk (nˆe´u . . ek l`amˆo.t khuyˆen th`ıta luˆonqui u´oc sk =0). Vector m chiˆ`eu (c1,c2, ,cm) . . . . go.il`avector chu tr`ınh tuong ´ung v´oi µ v`ak´yhiˆe.ul`a~µ (hay l`a µ nˆe´u khˆongthˆe˙’ gˆayra nhˆa`mlˆa˜n). 0 00 . . . C´acchu tr`ınh µ, µ ,µ , go.il`ad¯ ˆo. clˆa.p nˆe´u c´acvector chu tr`ınhtuong ´ung d¯ˆo.c . . lˆa.p tuyˆe´n t´ınh. Ch´u´yrˇa`ng, d¯i.nh ngh˜ıan`aykhˆongphu. thuˆo.c v`aohu´ong g´ancho c´ac ca.nh. . D- .inh l´y 2.1.4. Chu sˆo´ ν(G) cu˙’ a G =(V,E) bˇa`ng sˆo´ cu. cd¯a. i c´acchu tr`ınh d¯ˆo. clˆa. p. . . . . Ch´ung minh. Tiˆe´n h`anhnhu trong Hˆe. qua˙’ 2.1.3: d¯ˆa`u tiˆenta lˆa´yd¯ˆo` thi. vˆohu´ong khˆong . . 0 . c´oca.nh v´oitˆa.p c´acd¯ı˙’ nh l`a V. Sau d¯´ota xˆaydu. ng d¯ad¯ˆo` thi. G bˇa`ng c´ach thˆemt`ung . ca.nh mˆo.t v`ao.Theo D- .inh l´y2.1.2, chu sˆo´ s˜etˇangmˆo.td¯onvi. nˆe´uca.nh thˆemv`aolˆa.pra . . . . . . c´acchu tr`ınhm´oi, chu sˆo´ khˆongthay d¯ˆo˙’i trong tru`o ng ho. p nguo. cla.i. . . . . . Gia˙’ su˙’ , tru´oc khi thˆemca.nh ek ta d¯˜ac´omˆo.tcoso˙’ gˆo`m c´acchu tr`ınh d¯ˆo.c . . lˆa.p: µ1,µ2,µ3, ; v`asau khi thˆemca.nh ek xuˆa´thiˆe.n thˆemc´acchu tr`ınhso cˆa´pm´oi γ1,γ2, , n`aod¯´o.Hiˆe˙’n nhiˆen γ1 khˆongthˆe˙’ biˆe˙’udiˆe˜n tuyˆe´n t´ınhqua hˆe. c´acchu tr`ınh . . . . µj (v`ıc´acvector tuong ´ung c´acchu tr`ınh µj c´oth`anhphˆa`nth´u k bˇa`ng khˆong,trong . . . . khi vector tuong ´ung chu tr`ınh γ1 c´oth`anhphˆa`nth´u k kh´ackhˆong). Mˇa.t kh´acc´ac vector γ2,γ3, c´othˆe˙’ biˆe˙’udiˆe˜n tuyˆe´n t´ınhqua γ1,µ1,µ2,µ3, T´omla.imˆo˜ikhichu . . sˆo´ tˇangmˆo.td¯onvi. th`ısˆo´ cu. cd¯a.i c´acchu tr`ınhd¯ˆo.clˆa.p tuyˆe´nt´ınhc˜ung tˇanglˆen mˆo.t . . . . d¯ o nvi D- .inh l´yd¯uo. cch´ung minh. / T`u. kˆe´t qua˙’ n`ay, dˆ˜e d`angsuy ra: . . Hˆe. qua˙’ 2.1.5. (a) D- ad¯ˆo` thi. vˆohu´ong G khˆongc´ochu tr`ınh nˆe´u v`achı˙’ nˆe´u ν(G)=0. . . (b) D- ad¯ˆo` thi. vˆohu´ong G c´od¯´ung mˆo. t chu tr`ınhnˆe´u v`achı˙’ nˆe´u ν(G)=1. 57
. . . D- .inh l´y 2.1.6. Trong d¯ˆo` thi. c´ohu´ong liˆenthˆongma. nh, chu sˆo´ bˇa`ng sˆo´ cu. cd¯a. i c´ac ma. ch d¯ˆo. clˆa. p tuyˆe´n t´ınh. . . . . Ch´ung minh. Thˆa.tvˆa.y, x´etd¯ˆo` thi. vˆohu´ong lˆa.pbo˙’ i c´accung kh´acnhau cu˙’ a G (mˆo˜i . . . . cung tuong ´ung mˆo.tcˇa.pca.nh) v`amˆo.t chu tr`ınhso cˆa´p µ; ta phˆanhoa.ch tˆa.p c´acd¯ı˙’ nh . trˆenchu tr`ınhn`ayth`anh:tˆa.p S c´acd¯ı˙’ nh c´omˆo.t cung t´oi n´ov`amˆo.t cung ra kho˙’ i n´o, 0 00 . tˆa.p S c´acd¯ı˙’ nh c´ohai cung cu˙’ a µ ra kho˙’ i n´ov`atˆa.p S c´acd¯ı˙’ nh c´ohai cung cu˙’ a µ d¯it´oi . 0 00 . 0 0 0 n´o.V`ısˆo´ c´accung d¯ira bˇa`ng sˆo´ c´accung d¯it´oinˆen#S =#S ; gia˙’ su˙’ v1,v2, ,vk l`a . 0 00 00 00 . 00 c´acphˆa`ntu˙’ cu˙’ a S v`a v1,v2 , ,vk l`ac´acphˆa`ntu˙’ cu˙’ a S . Trˆenchu tr`ınh µ, c´acphˆa`ntu˙’. cu˙’ a S0 v`acu˙’ a S00 xen k˜e nhau v`ata gia˙’ su˙’. rˇa`ng 0 00 sau d¯ı˙’ nh vi th`ıd¯ı˙’ nh d¯ˆa`u tiˆenbˇa´tgˇa.p (khˆongthuˆo.c S)l`avi ; cuˆo´ic`ung, nˆe´u µ0 l`amˆo.t . . . . . . . d¯ u `ong d¯igˇa.pd¯ı˙’ nh x tru´ocd¯ı˙’ nh y th`ıta k´yhiˆe.u µ0[x, y] l`ad¯u`o ng d¯ibˆo. phˆa.ncu˙’ a µ0 t`u 0 00 x d¯ ˆe´n y. V`ıd¯ˆo` thi. liˆenthˆongma.nh nˆentˆo`nta.ima.ch µ1 d¯iqua vi+1 v`a vi v`ad`ung c´ac . 0 00 . cung cu˙’ a µ d¯ ˆe ˙’ d¯ i tu ` vi+1 d¯ ˆe´n vi . Chu tr`ınh µ l`amˆo.ttˆo˙’ ho. p tuyˆe´n t´ınhcu˙’ a c´acma.ch v`ı ta c´othˆe˙’ viˆe´t 0 00 0 00 0 00 µ = µ[v1,v1] − µ1[v2,v1 ]+µ[v2,v2]+··· 0 00 00 0 0 00 00 0 = µ[v1,v1]+µ1[v1,v2]+µ[v2,v2]+µ2[v2,v3]+···−(µ1 + µ2 + ···). . . . Vˆa.ymo.i chu tr`ınhso cˆa´pd¯ˆ`eul`atˆo˙’ ho. p tuyˆe´n t´ınhcu˙’ a c´acma.ch, d¯ˆo´iv´oi c´acchu . . tr`ınhbˆa´tk`yd¯iˆ`eud¯´oc˜ung d¯´ung (v`ın´ol`atˆo˙’ ho. p tuyˆe´n t´ınhcu˙’ a c´acchu tr`ınhso cˆa´p). m . . . Trong R , c´acma.ch lˆa.p th`anhmˆo.tcoso˙’ cu˙’ a khˆonggian vector con sinh bo˙’ i c´ac . . . chu tr`ınh,v`atheo D- .inh l´y2.1.4 th`ıcoso˙’ n`ayc´osˆo´ chiˆ`eul`aν(G). Vˆa.ysˆo´ cu. cd¯a.i c´ac ma.ch d¯ˆo.clˆa.p tuyˆe´n t´ınhbˇa`ng ν(G)./ 2.2 Sˇa´csˆo´ . . . . Gia˙’ su˙’ ch´ung ta c´omˆo.td¯ˆo` thi. vˆohu´o ng G v´oi n d¯ ı ˙’ nh v`acˆa`n tˆom`auc´acd¯ı˙’ nh sao cho hai d¯ı˙’ nh kˆe` nhau c´om`aukh´acnhau. Hiˆe˙’n nhiˆenl`ac´othˆe˙’ d`ung n m`aud¯ˆe˙’ tˆoc´acd¯ı˙’ nh . . . d¯´o,nhung nhu thˆe´ vˆa´nd¯ˆ`e d¯ ˇa.t ra la.i khˆongmang t´ınhthu. ctiˆe˜n. Thˆe´ th`ısˆo´ m`autˆo´i . . thiˆe˙’u d¯`oiho˙’ i l`abao nhiˆeu?D- ˆaych´ınhl`ab`aito´antˆom`au.Khi c´acd¯ı˙’ nh d¯uo. ctˆo,ch´ung . . ta c´othˆe˙’ nh´omch´ung v`aoc´actˆa.p kh´acnhau-mˆo.ttˆa.pgˆo`m c´acd¯ı˙’ nh d¯uo. c tˆom`aud¯o˙’ , 58
. . mˆo.ttˆa.p c´acd¯ı˙’ nh d¯uo. c tˆom`auxanh, vˆanvˆan.D- ˆay ch´ınh l`ab`aito´anphˆanhoa.ch. B`ai . . to´antˆom`auv`aphˆanhoa.ch d˜ı nhiˆenc´othˆe˙’ x´et trˆenc´acca.nh cu˙’ ad¯ˆo` thi Trong tru`ong . ho. pd¯ˆo` thi. phˇa˙’ ng thˆa.mch´ı c´othˆe˙’ quan tˆamd¯ˆe´nviˆe.c tˆom`auc´acdiˆe.n. . . Trong phˆa`n n`ayta chı˙’ x´et c´acd¯ˆo` thi. vˆohu´ong liˆenthˆong. . . D- .inh ngh˜ıa2.2.1. Cho tru´o cmˆo.tsˆo´ nguyˆen p, ta n´oirˇa`ng d¯ˆo` thi. G l`a p−sˇa´c nˆe´u bˇa`ng p m`aukh´acnhau ta c´othˆe˙’ tˆom`auc´acd¯ı˙’ nh, sao cho hai d¯ı˙’ nh kˆe` nhau khˆongc`ung . mˆo.t m`au.Sˆo´ p nho˙’ nhˆa´t, m`ad¯ˆo´iv´oisˆo´ d¯ ´o G l`a p−sˇa´cgo.il`asˇa´csˆo´ cu˙’ ad¯ˆo` thi. G v`ak´y hiˆe.ul`aγ(G). V´ı du. 2.2.2. H`ınh 2.2 minh ho.a ba c´ach tˆom`aukh´acnhau cu˙’ ad¯ˆo` thi Dˆ˜e d`angkiˆe˙’m tra rˇa`ng d¯ˆo` thi. n`ayl`a2−sˇa´c. . . . •. r •. r •. r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .• .• .• b b b gy•• gy•• rr•• • • • p r b (a) (b) (c) H`ınh 2.2: . V´ı du. 2.2.3. Ba˙’ nd¯ˆo` d¯. i al´y.Ta v˜etrˆenmˇa.t phˇa˙’ ng mˆo.tba˙’ nd¯ˆo`.Go.i V l`atˆa.pho. p c´ac . . . . . . nu´oc, d¯ˇa.t(i, j) ∈ E nˆe´u c´acnu´o c i v`a j c´obiˆengi´oi chung. D- `ˆo thi. G =(V,E)d¯ˆo´ix´ung v`ac´ot´ınhchˆa´trˆa´td¯ˇa.cbiˆe.t l`a:c´othˆe˙’ v˜en´olˆen mˇa.t phˇa˙’ ng m`akhˆongc´ohai ca.nh n`ao . . . cˇa´t nhau (tr`u ta.i c´acd¯ı˙’ nh chung); n´oic´ach kh´ac, G l`a d¯` ˆo thi. phˇa˙’ ng. Ngu`oi ta d¯˜abiˆe´t . . rˇa`ng sˇa´csˆo´ cu˙’ amo.id¯ˆo` thi. phˇa˙’ ng d¯ˆe` u nho˙’ hon hoˇa.cbˇa`ng bˆo´n(D- .inh l´y6.4.7). Nhu vˆa.y bˇa`ng bˆo´nm`auc˜ung d¯u˙’ d¯ ˆe ˙’ tˆom`auba˙’ nd¯ˆo` phˇa˙’ ng sao cho hai nu.´o.ckˆ`e nhau khˆongc`ung mˆo.t m`au. . T`u d¯ i .nh ngh˜ıadˆe˜ d`angsuy ra 1. Mˆo.td¯ˆo` thi. chı˙’ c´oc´acd¯ı˙’ nh cˆolˆa.pl`a1−sˇa´c. 59
2. Mˆo.td¯ˆo` thi. c´omˆo.t hoˇa.c hai ca.nh (khˆongpha˙’ il`amˆo.t khuyˆen) c´osˇa´csˆo´ ´ıtnhˆa´t bˇa`ng hai. 3. D- `ˆo thi. d¯` ˆa yd¯u˙’ n d¯ ı ˙’ nh Kn l`a n−sˇa´c. . . 4. D- `ˆo thi. l`amˆo.t chu tr`ınhd¯on gia˙’ nv´oi n d¯ ı ˙’ nh, n>3, l`a2−sˇa´cnˆe´u n chˇa˜nv`a3−sˇa´c nˆe´u n le˙’ . 5. Hiˆe˙’n nhiˆen,mo.id¯ˆo` thi. 2−sˇa´c l`ahai phˆa`ndoch´ung ta c´othˆe˙’ phˆanhoa.ch tˆa.p c´ac . . . . . d¯ ı ˙’ nh V th`anhhai tˆa.p con theo m`aud¯uo. c tˆotrˆenc´acd¯ı˙’ nh. Tuong tu. ,d¯ˆo` thi. hai . . . . . . phˆa`nl`a2−sˇa´c, v´oimˆo.t tru`ong ho. p ngoa.ilˆe. tˆa`mthu`ong: d¯ˆo` thi. c´o´ıtnhˆa´t hai . d¯ ı ˙’ nh cˆolˆa.p v`akhˆongc´oca.nh l`ahai phˆa`nnhung l`a1−sˇa´c. . D- .inh ngh˜ıa2.2.4. Ta go.i sˇa´cl´op cu˙’ ad¯ˆo` thi. G l`asˆo´ nguyˆen q c´oc´act´ınhchˆa´t sau: 1. C´othˆe˙’ d`ung q m`aukh´acnhau d¯ˆe˙’ tˆom`auc´acca.nh cu˙’ a G sao cho hai ca.nh kˆ`e nhau c´om`aukh´acnhau; . . . 2. D- iˆe` u n`aykhˆongthˆe˙’ l`amd¯uo. cv´oi(q − 1) m`au. . V´ı du. 2.2.5. D- `ˆo thi. G trong h`ınh 2.2 c´osˇa´cl´opbˇa`ng 4. . 0 Nhˆa.nx´et rˇa`ng sˇa´cl´opcu˙’ ad¯ˆo` thi. G =(V,E)ch´ınh l`asˇa´csˆo´ cu˙’ ad¯ˆo` thi. G = 0 0 . . . 0 . . . (V ,E)d¯uo. c x´acd¯i.nh nhu sau: mˆo˜id¯ı˙’ nh cu˙’ a G tuong ´ung mˆo.tca.nh cu˙’ a G;ca.nh 0 0 0 0 . . . . 0 0 e =(v1,v2) ∈ E nˆe´u c´acca.nh e1 v`a e2 (tuong ´ung v´oi hai d¯ı˙’ nh v1,v2)kˆ`e nhau. . . . . . . Nhu vˆa.y b`aito´ansˇa´cl´opd¯uavˆ`e b`aito´ansˇa´csˆo´.Du´o i d¯ˆayl`amˆo.t v`aikˆe´t qua˙’ co ba˙’ nvˆe` sˇa´csˆo´. . . D- .inh l´y 2.2.6. [K¨onig] D- `ˆo thi. vˆohu´ong G l`a 2−sˇa´cnˆe´u v`achı˙’ nˆe´u n´okhˆongc´ochu tr`ınh c´od¯ˆo. d`aile˙’ . . . Ch´ung minh. D- iˆe` ukiˆe.ncˆa`n. Nˆe´ud¯ˆo` thi. G l`a2−sˇa´c, th`ıtˆa´t nhiˆen G khˆongch´ua chu . tr`ınhc´od¯ˆo. d`aile˙’ , v`ıc´acd¯ı˙’ nh cu˙’ amˆo.t chu tr`ınhloa.inhuvˆa.y khˆongthˆe˙’ tˆobˇa`ng hai m`autheo nhu. quy tˇa´c d¯˜achı˙’ ra o˙’. trˆen. . . D- iˆe` ukiˆe.nd¯u˙’ . Gia˙’ su˙’ d¯` ˆo thi. G khˆongc´ochu tr`ınhc´od¯ˆo. d`aile˙’ ,tach´ung minh n´ol`a 2−sˇa´c. Khˆonggia˙’ mtˆo˙’ng qu´atcoi G l`aliˆenthˆong. Ta s˜etˆom`audˆa`n c´acd¯ı˙’ nh cu˙’ a G theo quy tˇa´c sau: 60
• tˆom`auxanh cho mˆo.td¯ı˙’ nh a n`aod¯´o; . . . • nˆe´umˆo.td¯ı˙’ nh x n`aod¯´od¯˜ad¯uo. c tˆoxanh, th`ıta tˆod¯o˙’ tˆa´tca˙’ c´acd¯ı˙’ nh kˆe` v´oi n´o; . . . nˆe´ud¯ı˙’ nh y d¯˜ad¯uo.c tˆod¯o˙’ , th`ıta tˆoxanh tˆa´tca˙’ c´acd¯ı˙’ nh kˆe` v´oi y. . . . V`ıd¯ˆo` thi. G liˆenthˆong,nˆens´omhaymuˆo.nth`ımo.id¯ı˙’ nh cu˙’ an´od¯ˆ`eud¯uo. c tˆom`auhˆe´t, . . . v`amˆo.td¯ı˙’ nh x khˆongthˆe˙’ c`ung mˆo.tl´uc d¯uo. c tˆoxanh v`atˆod¯o˙’ ,v`ınhuvˆa.yth`ıx v`a a s˜e c`ung nˇa`m trˆenmˆo.t chu tr`ınhc´od¯ˆo. d`aile˙’ .Vˆa.yd¯ˆo` thi. G l`a2−sˇa´c. / . . . . . . Ch´u´yrˇa`ng t´ınhchˆa´td¯ˆo` thi. G khˆongc´ochu tr`ınhv´oid¯ˆo. d`aile˙’ tuong d¯uong v´oi . . . t´ınhchˆa´t G khˆongc´ochu tr`ınhso cˆa´pv´oid¯ˆo. d`aile˙’ . Thˆa.tvˆa.y gia˙’ su˙’ c´omˆo.t chu tr`ınh µ = {v0,v1, ,vp = v0} . c´od¯ˆo. d`ai p le˙’ .Mˆo˜i khi gˇa.p hai d¯ı˙’ nh vj v`a vk v´oi j<k<pv`a vj = vk, ta phˆanchia µ . . th`anhhai chu tr`ınhbˆo. phˆa.n µ1 = {vj, ,vk} v`a µ2 = {v0, ,vj,vk, ,v0};honn˜ua . mˆo.t trong hai chu tr`ınhc´od¯ˆo. d`aile˙’ (v`ınˆe´u khˆongnhu thˆe´ th`ı µ s˜ec´od¯ˆo. d`aichˇa˜n). Ta thˆa´yrˇa`ng nˆe´utiˆe´ptu.c phˆanchia chu tr`ınh µ theo c´ach d¯´ocho d¯ˆe´n khi c`onc´othˆe˙’ l`am . . . . d¯ u o.c, th`ımˆo˜ilˆa`nvˆa˜n c`ond¯uo. cmˆo.t chu tr`ınhc´od¯ˆo. d`aile˙’ ; v`ıcuˆo´ic`ung mo.i chu tr`ınh d¯` ˆe ul`aso. cˆa´p, nˆenxa˙’ y ra mˆauthuˆa˜n; v`ata c´od¯iˆ`eucˆa`nch´u.ng minh. D- .inh l´ysau d¯ˆaycho ta biˆe´tcˆa.n trˆencu˙’ asˇa´csˆo´. - . D.inh l´y 2.2.7. K´yhiˆe.u dmax l`abˆa. ccu. cd¯a. icu˙’ a c´acd¯ı˙’ nh trong G. Khi d¯´o γ(G) ≤ 1+dmax. . Ch´ung minh. B`aitˆa.p. / . Brooks [9] d¯˜ach´ung minh rˇa`ng nˆe´u G l`ad¯ˆo` thi. khˆongd¯ˆa`yd¯u˙’ ,c´odmax d¯ ı ˙’ nh th`ı γ(G) ≤ dmax. 61
2.2.1 C´ach t`ımsˇa´csˆo´ X´et d¯ˆo` thi. G =(V,Γ) c´o n d¯ ı ˙’ nh v`a m ca.nh; muˆo´n t`ımsˇa´csˆo´ cu˙’ an´otac´othˆe˙’ d`ung mˆo.t . . . . . . . . phuong ph´apthu. c nghiˆe.mrˆa´td¯on gia˙’ n, ´apdu.ng tru. ctiˆe´pd¯uo. c, nhung khˆongpha˙’ il´uc . . . n`aoc˜ung c´ohiˆe.u qua˙’ hoˇa.cc´othˆe˙’ d`ung phuong ph´apgia˙’ i t´ıch, n´ocho ta mˆo.tl`oi gia˙’ ihˆe. . . thˆo´ng, nhung n´oichung cˆa`n m´ayt´ınhd¯iˆe.ntu˙’ . . . . Phuong ph´apthu. c nghiˆe.m Bˇa`ng c´ach tˆom`aut`uy´yd`ung c´acm`au1, 2, ,p v`at`ımc´ach loa.idˆa`nmˆo.t m`aun`aod¯´o . . (go.i l`a“m`aut´oiha.n”) trong c´acm`auˆa´y. Muˆo´nvˆa.y,tax´et d¯ı˙’ nh v c´om`aut´oiha.nd¯´ov`a jk jk . . c´acth`anhphˆa`n liˆenthˆong C1 ,C2 , cu˙’ ad¯ˆo` thi. con sinh ra bo˙’ i hai m`aukhˆongt´oiha.n ˙’ . . jk jk j v`a k. Tac´othˆelˆa.pt´uc thay m`aucu˙’ ad¯ı˙’ nh v nˆe´u c´actˆa.pho. p C1 ∩Γ(v),C2 ∩Γ(v), khˆongpha˙’ i l`ahai m`au:lˆa´y riˆengr˜emˆo˜i th`anhphˆa`n Cjk m`av´o.i th`anhphˆa`n d¯´oth`ıc´ac d¯ ı ˙’ nh cu˙’ a Cjk ∩ Γ(v) c´om`au j, ho´anvi. trong c´acth`anhphˆa`n d¯´oc´acm`au j v`a k (khˆong thay d¯ˆo˙’i m`aucu˙’ a c´acd¯ı˙’ nh kh´ac),cuˆo´ic`ung tˆod¯ı˙’ nh v m`au j (l´uc n`ayd¯ı˙’ nh v khˆongkˆ`e v´o.id¯ı˙’ nh n`aoc´om`au j). Phu.o.ng ph´apgia˙’ it´ıch . . . . Kiˆe˙’m tra bˇa`ng c´ach gia˙’ i t´ıch xem d¯ˆo` thi. G c´othˆe˙’ d¯ u o. c tˆobˇa`ng p m`aud¯uo. c khˆong. . . . . . . . . Phuong ph´apd¯´onhu sau: V´oimˆo˜i c´ach tˆobˇa`ng p m`au,ta cho tuong ´ung v´oimˆo.thˆe. . . . thˆo´ng c´acsˆo´ xij,i=1, 2, ,n; j =1, 2, ,p, d¯ u o. c x´acd¯i.nh nhu sau: ( 1nˆe´ud¯ı˙’ nh i c´om`au j, xij = . . . . . 0 trong tru`ong ho. p nguo. cla.i. D- ˇa.t ( 1nˆe´uca.nh ej liˆenthuˆo.cd¯ı˙’ nh vi, rij = . . . . . 0 trong tru`ong ho. p nguo. cla.i. 62
. L´uc d¯´ob`aito´antro˙’ th`anht`ım c´acsˆo´ nguyˆen xij sao cho:  xij ≥ 0,  p Pq=1 xiq ≤ 1,i=1, 2, ,n, n ≤  Pk=1 rjkxkq 1,j=1, 2, ,m; q =1, 2, ,p. . . . Ta c´ohˆe. bˆa´td¯ˇa˙’ ng th´uc tuyˆe´n t´ınh. Dˆ˜e r`angthˆa´yrˇa`ng hˆe. d¯´oth´ıch ho. pv´oi c´ac . . . . . . phuong ph´apthˆongthu`ong cu˙’ a quy hoa.ch nguyˆen v`ado d¯´oc´othˆe˙’ d`ung phuong ph´ap . . . . cu˙’ a Gomory (du. a trˆenphuong ph´apd¯on h`ınhcu˙’ a Dantzig) d¯ˆe˙’ gia˙’ i. 2.3 Sˆo´ ˆo˙’ nd¯i.nh trong . . . . . . V´oid¯ˆo` thi. G =(V,Γ) cho tru´oc ta thu`ong quan tˆamd¯ˆe´ntˆa.p con cu˙’ a V c´onh˜ung t´ınh . . chˆa´t n`aod¯´o. Chˇa˙’ ng ha.n, t`ımmˆo.ttˆa.p con S ⊂ V c´osˆo´ phˆa`ntu˙’ l´on nhˆa´t sao cho d¯ˆo` . . thi. con sinh bo˙’ i S l`ad¯ˆa`yd¯u˙’ ? Hoˇa.c t`ımtˆa.p con c´acd¯ı˙’ nh cu˙’ ad¯ˆo` thi. G c´osˆo´ phˆa`ntu˙’ nhiˆe` u nhˆa´t sao cho hai d¯ı˙’ nh trong d¯´okhˆongkˆ`e nhau. Mˆo.t b`aito´ankh´acl`at`ımtˆa.p con . . S cu˙’ a V c´osˆo´ phˆa`ntu˙’ ´ıtnhˆa´t sao cho mo.id¯ı˙’ nh thuˆo.c V \ S kˆ`e v´oimˆo.td¯ı˙’ nh trong S. . . . . . C´acsˆo´ v`ac´actˆa.p con tuong ´ung l`oi gia˙’ i c´acb`aito´antrˆencho nh˜ung t´ınhchˆa´t . . quan tro.ng cu˙’ ad¯ˆo` thi. v`ac´onhiˆe` u´ung du. ng tru. ctiˆe´p trong b`aito´anlˆa.pli.ch, phˆant´ıch . . cluster, phˆanloa.isˆo´,xu˙’ l´ysong song trˆenm´ayt´ınh,vi. tr´ıthuˆa.nlo. i v`athay thˆe´ c´ac . th`anhphˆa`nd¯iˆe.ntu˙’ , v.v. . . . . . D- .inh ngh˜ıa2.3.1. X´et d¯ˆo` thi. vˆohu´ong G := (V,Γ); tˆa.pho. p S ⊂ V d¯ u o. cgo.il`atˆa.p . . ho. pˆo˙’nd¯i.nh trong nˆe´u hai d¯ı˙’ nh bˆa´tk`ycu˙’ a S d¯` ˆe u khˆongkˆe` nhau; n´oic´ach kh´ac,v´oi mo.icˇa.pd¯ı˙’ nh a, b ∈ S th`ı b/∈ Γ(a). K´yhiˆe.u S l`aho. c´actˆa.pˆo˙’nd¯i.nh trong cu˙’ ad¯ˆo` thi. G. Khi d¯´o 1. Tˆa.p trˆo´ng ∅ thuˆo.c S. 2. Nˆe´u S ∈Sv`a A ⊂ S th`ı A ∈S. N´oic´ach kh´ac,tˆa.p con cu˙’ amˆo.ttˆa.pˆo˙’nd¯i.nh trong c˜ung l`amˆo.ttˆa.pˆo˙’nd¯i.nh trong. 63
. Tˆa.pˆo˙’nd¯i.nh trong l`a cu. cd¯a. i nˆe´u thˆemmˆo.td¯ı˙’ nh bˆa´tk`y v`aon´oth`ıs˜e khˆongc`onˆo˙’n . . . d¯ i .nh trong n˜ua. D- a.iluo. ng α(G) := max{#S | S ∈S} . . d¯ u o.cgo.il`asˆo´ ˆo ˙’nd¯i.nh trong cu˙’ aG. V´ı du. 2.3.2. X´et d¯ˆo` thi. G trong H`ınh 2.3. Tˆa.p c´acd¯ı˙’ nh {v7,v8,v2} l `a ˆo ˙’nd¯i.nh trong . . . nhung khˆongcu. cd¯a.i; tˆa.p {v7,v8,v2,v5} l `a ˆo ˙’nd¯i.nh trong cu. cd¯a.i. C´actˆa.p {v1,v3,v7} . v`a {v4,v6} c˜ung l`atˆa.pˆo˙’nd¯i.nh trong cu. cd¯a.i v`ado d¯´o,n´oichung c´othˆe˙’ c´onhiˆ`eutˆa.p . . ˆo˙’nd¯i.nh trong cu. cd¯a.i. Ho. c´actˆa.pˆo˙’nd¯i.nh trong cu. cd¯a.icu˙’ ad¯ˆo` thi. n`ayl`a {v7,v8,v2,v5}, {v1,v3,v7}, {v4,v6}, {v3,v6}, {v1,v5,v7}, {v1,v4}, {v3,v7,v8}. Suy ra α(G)=4. v1 v2 v3 ••• . . . . . . . . . . . . . . . . . . • •. v6 . • v4 . . . v8 . . . . . . . . . . . • .• v7 v5 H`ınh 2.3: . V´ı du. 2.3.3. [Gauss] B`aito´ant´amcon hˆa.u. Trˆenb`anc`o c´othˆe˙’ bˆo´ tr´ıt´amcon hˆa.u, . . . sao cho khˆongc´ocon n`aoch´em d¯uo. c con n`aokhˆong? B`aito´annˆo˙’itiˆe´ng n`ayd¯uavˆe` . . . . t`ımmˆo.ttˆa.pho. pˆo˙’nd¯i.nh trong cu. cd¯a.icu˙’ ad¯ˆo` thi. vˆohu´ong c´o64 d¯ı˙’ nh (l`ac´acˆotrˆen . b`anc`o), trong d¯´o y ∈ Γ(x)nˆe´u c´acˆo x v`a y nˇa`m trˆenc`ung mˆo.t h`ang,mˆo.tcˆo.t hay mˆo.t . . . . . . . . d¯ u `ong ch´eo. Thu. ctˆe´, kh´okhˇanla.il´onhon l`akhi ngu`oi ta m´oi thoa.tnh`ın: l´uc d¯ˆa`u Gauss tu.o˙’.ng c´o76 l`o.i gia˙’ i, c`ont`o. b´aovˆ`e c`o. o˙’. Berlin“Schachzeitung” nˇam1854 chı˙’ m´o.i . . . . . . . d¯ u a ra 40 l`oi gia˙’ ithˆe´ c`o do c´acnh`aham c`o t`ımra. Su. thˆa.t th`ıc´o92 l`oi gia˙’ inhu12 so. d¯` ˆo du.´o.i d¯ˆay: (72631485) (61528374) (58417263) (35841726) (46152837) (57263148) (16837425) (57263184) (48157263) (51468273) (42751863) (35281746) 64
. . . . . . . . Mˆo˜isod¯` ˆo trˆentuong ´ung v´oimˆo.t ho´anvi.,v`at`u mˆo.tsod¯` ˆo ta suy ra t´aml`oi gia˙’ i kh´ac nhau: ba l`o.i gia˙’ ibˇa`ng c´ach quay 900, 1800 v`a2700; c´acl`o.i gia˙’ i kh´acsuy ra bˇa`ng c´ach . . . . . . d¯ ˆo´ix´ung mˆo˜isod¯` ˆo nhˆa.nd¯uo. c qua d¯u`ong ch´eo ch´ınh;ho´anvi. cuˆo´ic`ung (35281746) chı˙’ c´obˆo´nl`o.i gia˙’ iv`ıso. d¯` ˆo tu.o.ng ´u.ng s˜etr`ung v´o.ich´ınh n´osau khi quay 1800. . V´ı du. 2.3.4. B`e cu˙’ amˆo.td¯ˆo` thi. G l`atˆa.pho. p C ⊂ V sao cho a ∈ C, b ∈ C suy ra b ∈ Γ(a). . . . . . . . Nˆe´u V l`amˆo.ttˆa.pho. p ngu`o i, v`a b ∈ Γ(a)chı˙’ su. d¯` ˆo ng t`ınhgi˜ua a v`a b, th`ıthu`ong . . . yˆeu cˆa`ut`ımb`ecu. cd¯a.i, ngh˜ıa l`ahˆo.i c´osˆo´ ngu`oi tham gia nhiˆe` u nhˆa´t. X´etd¯ˆo` thi. 0 0 . G := (V,Γ ) x´acd¯i.nh nhu sau: b ∈ Γ(a0)nˆe´uv`achı˙’ nˆe´u b/∈ Γ(a). . . 0 B`aito´anquy vˆe` t`ımmˆo.ttˆa.pho. pˆo˙’nd¯i.nh trong cu. cd¯a.icu˙’ ad¯ˆo` thi. (V,Γ ). . . V´ı du. 2.3.5. B`aito´anvˆe` c´accˆog´ai l`ad¯ˆo´ituo. ng cu˙’ a nhiˆe` u cˆongtr`ınhto´anho.c, c´o . . . thˆe˙’ ph´atbiˆe˙’unhusau: mˆo.tk´yt´uc x´anuˆoidu˜ong 15 cˆog´ai,k´yhiˆe.ul`a a, b, c, d, e, f, g, h, i, j, k, l, m, n, o. . . . . H`angng`ayc´accˆod¯ida.ochoi th`anht`ung bˆo. ba, c´othˆe˙’ d¯ u a c´accˆod¯ichoi trong ba˙’ y . . ng`ayliˆ`en sao cho khˆongc´ohai cˆon`aoc`ung d¯itrong mˆo.tbˆo. ba qu´amˆo.tlˆa`nd¯uo.c khˆong? . . . . . V´oinh˜ung nhˆa.n x´et vˆe` d¯ ˆo´ix´ung, Cayley d¯˜at`ımra l`oi gia˙’ inhusau: . . . . . . . Chu˙’ Nhˆa.t Th´u Hai Th´u Ba Th´u Tu Th´u Nˇam Th´u S´au Th´u Ba˙’ y afk abe alm ado agn ahj aci bgl cno bcf bik bdj bmn bho chm df l deh cjl cek cdg dkm din ghk gio egm fmo fei eln ejo ijm jkn fhn hil klo fgj . . B`aito´anvˆe` c´accˆog´aic`ung loa.iv´oimˆo.t b`aito´anth´u hai c˜ung nˆo˙’itiˆe´ng go.il`a . . . . b`aito´anbˆo˙’ tro. : v´oi 15 cˆog´aic´othˆe˙’ lˆa`nluo. tlˆa.p35bˆo. ba kh´acnhau sao cho khˆongc´o 65