Bài giảng Đồ thị và các thuật toán

Nội dung text: Bài giảng Đồ thị và các thuật toán

1. Giáo trình Đồ thị và các thuật toán
2. Mu. c lu. c L`o.i n´oid¯ˆa` u 7 . . 1 D- a.i cuong 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 10 1.1.4 C´acd¯i.nh ngh˜ıach´ınh. . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Ma trˆa.n biˆe˙’u diˆe˜n d¯ˆo` thi. 13 1.2.1 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh . . . . . . . . . . . . . . . . . . . . . . 15 1.2.3 Ma trˆa.n kˆe` hay ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-d¯ı˙’nh . . . . . . . . . . . . . 17 1.2.4 C´acbiˆe˙’u diˆe˜n cu˙’a d¯ˆo` thi. 18 1.3 T´ınhliˆenthˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 Dˆaychuyˆe` n v`achu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . 23 . . 1.3.2 D- u`ong d¯iv`ama.ch 24 1.3.3 T´ınhliˆenthˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1
3. 1.3.4 Cˆa`u, k−liˆenthˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.3.5 D- `ˆo thi. liˆenthˆongma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.4 Pha.m vi v`aliˆenthˆongma.nh 33 1.4.1 Ma trˆa.n pha.mvi 33 1.4.2 T`ımc´acth`anhphˆa`n liˆenthˆongma.nh . . . . . . . . . . . . . . . . . . 36 1.4.3 Co. so˙’. 39 1.5 D- ˇa˙’ng cˆa´u cu˙’a c´acd¯ˆo` thi. 41 1.5.1 1−d¯ˇa˙’ng cˆa´u 42 1.5.2 2−d¯ˇa˙’ng cˆa´u 43 1.6 C´acd¯ˆo` thi. d¯ˇa.c biˆe.t 46 1.6.1 D- `ˆo thi. khˆongc´oma.ch 46 1.6.2 D- `ˆo thi. phˇa˙’ng 46 . 2 C´acsˆo´ co ba˙’n cu˙’a d¯ˆo` thi. 49 2.1 Chu sˆo´ 49 2.2 Sˇa´c sˆo´ 52 2.2.1 C´ach t`ımsˇa´c sˆo´ 54 2.3 Sˆo´ ˆo˙’n d¯i.nh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Sˆo´ ˆo˙’n d¯i.nh ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Phu˙’ 65 2.6 Nhˆancu˙’a d¯ˆo` thi. 69 2.6.1 C´acd¯i.nh l´yvˆe` tˆo`n ta.i v`aduy nhˆa´t 69 2.6.2 Tr`ocho.i Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2
4. 3 C´acb`aito´anvˆe` d¯u.`o.ng d¯i 75 3.1 D- u.`o.ng d¯igi˜u.a hai d¯ı˙’nh 75 3.1.1 D- u.`o.ng d¯igi˜u.a hai d¯ı˙’nh . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.1.2 D- `ˆo thi. liˆenthˆongma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2 D- u.`o.ng d¯ingˇa´n nhˆa´t gi˜u.a hai d¯ı˙’nh . . . . . . . . . . . . . . . . . . . . . . . 78 . . . . . 3.2.1 Tru`ong ho. p ma trˆa.n tro.ng luo. ng khˆongˆam . . . . . . . . . . . . . . 78 . . . . . 3.2.2 Tru`ong ho. p ma trˆa.n tro.ng luo. ng tu`y´y. . . . . . . . . . . . . . . . . 82 . . . 3.3 D- u`ong d¯ingˇa´n nhˆa´t gi˜ua tˆa´t ca˙’ c´accˇa.p d¯ı˙’nh . . . . . . . . . . . . . . . . . 87 . . . . . 3.3.1 Thuˆa.t to´anHedetniemi (tru`ong ho. p ma trˆa.n tro.ng luo. ng khˆongˆam) 88 . . . . . 3.3.2 Thuˆa.t to´anFloyd (tru`ong ho. p ma trˆa.n tro.ng luo. ng tu`y´y). . . . . . 93 3.4 Ph´athiˆe.n ma.ch c´od¯ˆo. d`aiˆam . . . . . . . . . . . . . . . . . . . . . . . . . . 96 . . . 3.4.1 Ma.ch tˆo´i uu trong d¯ˆo` thi. c´ohai tro.ng luo. ng . . . . . . . . . . . . . . 96 4 CAYˆ 99 4.1 Mo˙’. d¯ˆa`u 99 4.2 CˆayHuffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2.1 C´acbˆo. m˜a“tˆo´t” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2.2 M˜aHuffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 Cˆaybao tr`um. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.1 Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u rˆo.ng x´acd¯i.nh cˆaybao tr`um. . . . . 107 4.3.2 Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆaux´acd¯i.nh cˆaybao tr`um . . . . . 107 . 4.3.3 T`ımcˆaybao tr`umdu. a trˆenhai ma˙’ng tuyˆe´n t´ınh . . . . . . . . . . . 108 4.3.4 Thuˆa.t to´ant`ımtˆa´t ca˙’ c´accˆaybao tr`um . . . . . . . . . . . . . . . . 112 . . 4.3.5 Hˆe. co so˙’ cu˙’a c´acchu tr`ınhd¯ˆo.c lˆa.p . . . . . . . . . . . . . . . . . . . 112 3
5. 4.4 Cˆaybao tr`umtˆo´i thiˆe˙’u 114 4.4.1 Thuˆa.t to´anKruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.4.2 Thuˆa.t to´anPrim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.4.3 Thuˆa.t to´anDijkstra-Kevin-Whitney . . . . . . . . . . . . . . . . . . 121 4.5 B`aito´anSteiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5 B`aito´anEuler v`ab`aito´anHamilton 127 5.1 B`aito´anEuler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.1.1 Thuˆa.t to´ant`ımdˆaychuyˆe` n Euler . . . . . . . . . . . . . . . . . . . . 129 5.2 B`aito´anngu.`o.i d¯u.a thu. Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . 131 5.3 B`aito´anHamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.3.1 C´acd¯iˆe` u kiˆe.n cˆa`n d¯ˆe˙’ tˆo`n ta.i chu tr`ınhHamilton . . . . . . . . . . . . 138 . 5.3.2 C´acd¯iˆe` u kiˆe.n d¯u˙’ vˆe` su. tˆo`n ta.i chu tr`ınhHamilton . . . . . . . . . . 139 . 5.3.3 C´acd¯iˆe` u kiˆe.n d¯u˙’ vˆe` su. tˆo`n ta.i ma.ch Hamilton . . . . . . . . . . . . . 142 6 D- `ˆo thi. phˇa˙’ng 149 6.1 D- .inh ngh˜ıav`ac´acv´ıdu. 149 6.2 C´acbiˆe˙’u diˆe˜n kh´acnhau cu˙’a mˆo.t d¯ˆo` thi. phˇa˙’ng . . . . . . . . . . . . . . . . 151 6.3 C´act´ınhchˆa´t cu˙’a d¯ˆo` thi. phˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.4 Ph´athiˆe.n t´ınhphˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 6.4.1 Kiˆe˙’m tra t´ınhphˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.5 D- ˆo´i ngˆa˜u h`ınhho.c 167 . 6.6 D- ˆo´i ngˆa˜u tˆo˙’ ho. p 170 7 Ma.ng vˆa.n ta˙’i 173 4
6. 7.1 Mo˙’. d¯ˆa`u 173 7.2 B`aito´anluˆo`ng l´o.n nhˆa´t 174 . 7.2.1 Thuˆa.t to´ang´annh˜and¯ˆe˙’ t`ımluˆo`ng l´on nhˆa´t . . . . . . . . . . . . . . 180 7.2.2 D- `ˆo thi. d¯iˆe` u chı˙’nh luˆo`ng . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2.3 Phˆant´ıch luˆo`ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3 C´acca˙’i biˆend¯o.n gia˙’n cu˙’a b`aito´anluˆo`ng l´o.n nhˆa´t . . . . . . . . . . . . . . . 183 7.3.1 C´acd¯ˆo` thi. c´onhiˆe` u nguˆo`n v`anhiˆe` u d¯´ıch . . . . . . . . . . . . . . . . 183 . 7.3.2 C´acd¯ˆo` thi. v´oi r`angbuˆo.c ta.i c´accung v`ad¯ı˙’nh . . . . . . . . . . . . . 184 . . 7.3.3 C´acd¯ˆo` thi. c´ocˆa.n trˆenv`acˆa.n du´oi vˆe` luˆo`ng . . . . . . . . . . . . . . 185 7.4 Luˆo`ng v´o.i chi ph´ınho˙’ nhˆa´t 186 7.4.1 Thuˆa.t to´anKlein, Busacker, Gowen . . . . . . . . . . . . . . . . . . . 186 7.5 Cˇa.p gh´ep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7.5.1 C´acb`aito´anvˆe` cˇa.p gh´ep . . . . . . . . . . . . . . . . . . . . . . . . 189 . 7.5.2 Cˇa.p gh´epl´on nhˆa´t trong d¯ˆo` thi. hai phˆa`n . . . . . . . . . . . . . . . . 192 7.5.3 Cˇa.p gh´epho`anha˙’o trong d¯ˆo` thi. hai phˆa`n . . . . . . . . . . . . . . . 193 . A Thu viˆe.n Graph.h 197 T`ailiˆe.u tham kha˙’o 209 5
7. L`o.i n´oid¯ˆa` u . . . . . Trong thu. c tˆe´ d¯ˆe˙’ miˆeuta˙’ mˆo.t sˆo´ t`ınhhuˆo´ng ngu`oi ta thu`ong biˆe˙’u thi. bˇa`ng mˆo.t h`ınha˙’nh . gˆo`m c´acd¯iˆe˙’m (c´acd¯ı˙’nh)-biˆe˙’u diˆe˜n c´acthu. c thˆe˙’-v`av˜ec´acd¯oa.n thˇa˙’ng nˆo´i cˇa.p c´acd¯ı˙’nh biˆe˙’u . . . . . diˆe˜n mˆo´i quan hˆe. gi˜ua ch´ung.Nh˜ung h`ınhnhu thˆe´ thu`ong go.i l`ac´ac d¯ˆo` thi Mu. c d¯´ıch cu˙’a . . . . gi´aotr`ınhn`aycung cˆa´p nh˜ung kiˆe´n th´uc co ba˙’n d¯ˆe˙’ nghiˆenc´uu c´acd¯ˆo` thi C´acd¯ˆo` thi. xuˆa´t . . . hiˆe.n trong nhiˆe` u l˜ınhvu. c v´oi c´actˆengo.i kh´acnhau: “cˆa´u tr´uc”trong cˆongtr`ınhxˆaydu. ng, . . . . “ma.ch” trong d¯iˆe.n tu˙’ , “luo. c d¯ˆo` quan hˆe.”, “cˆa´u tr´uctruyˆe` n thˆong”,“cˆa´u tr´uctˆo˙’ ch´uc” . trong x˜ahˆo.i v`akinh tˆe´, “cˆa´u tr´ucphˆ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ˆenc´uu . xung quanh l´ythuyˆe´t d¯ˆ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˙’y su. ph´attriˆe˙’n d¯´ol`axuˆa´t hiˆe.n c´acm´ayt´ınhl´on c´othˆe˙’ thu. c hiˆe.n nhiˆe` u ph´epto´anv´oi . . tˆo´c d¯ˆo. rˆa´t nhanh. Viˆe.c biˆe˙’u diˆe˜n tru. c tiˆe´p v`achi tiˆe´t c´achˆe. thˆo´ng thu. c tˆe´, chˇa˙’ng ha.n c´ac . . . . . ma.ng truyˆe` n thˆong,d¯˜ad¯ua d¯ˆe´n nh˜ung d¯ˆo` thi. c´ok´ıch thu´oc l´on v`aviˆe.c phˆant´ıch th`anh . cˆonghˆe. thˆo´ng phu. thuˆo.c rˆa´t nhiˆe` u v`aoc´acthuˆa.t to´an“tˆo´t” c˜ungnhu kha˙’ nˇangcu˙’a m´ay t´ınh. Theo d¯´o,gi´aotr`ınhn`ays˜etˆa.p trung v`aoviˆe.c ph´attriˆe˙’n v`atr`ınhb`ayc´acthuˆa.t to´an d¯ˆe˙’ phˆant´ıch c´acd¯ˆo` thi . . C´acphuong ph´apphˆant´ıch v`athiˆe´t kˆe´ c´acthuˆa.t to´antrong gi´aotr`ınhcho ph´epsinh . . . . viˆenc´othˆe˙’ viˆe´t dˆe˜ d`angc´acchuong tr`ınhminh ho.a. Gi´aotr`ınhd¯uo. c biˆensoa.n cho c´acd¯ˆo´i . . tuo. ng l`asinh viˆenTo´an-Tinv`aTin ho.c. . . Gi´aotr`ınhsu˙’ du. ng ngˆonng˜u C d¯ˆ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ˆencˆa`n c´omˆo.t sˆo´ kiˆe´n th´uc vˆe` ngˆonng˜u C. Ngo`ai . . . . ra, hˆa`u hˆe´t c´acchuong tr`ınhthao t´actrˆencˆa´u tr´ucd˜u liˆe.u nhu danh s´ach liˆenkˆe´t, nˆend¯`oi . ho˙’i sinh viˆenpha˙’i c´onh˜ung k˜ynˇanglˆa.p tr`ınhtˆo´t. . . . . . Gi´aotr`ınhbao gˆo`m ba˙’y chuong v`amˆo.t phˆa`n phu. lu. c v´oi nh˜ung nˆo.i dung ch´ınhnhu sau: . . . . • Chuong th´u nhˆa´t tr`ınhb`aynh˜ung kh´ainiˆe.m cˇanba˙’n vˆe` d¯ˆo` thi . . . . . • Chuong 2 tr`ınhb`aynh˜ung sˆo´ co ba˙’n cu˙’a d¯ˆo` thi Y´ ngh˜ıathu. c tiˆe˜n cu˙’a c´acsˆo´ n`ay. 7
8. • Chu.o.ng 3 t`ımhiˆe˙’u b`aito´ant`ımd¯u.`o.ng d¯ingˇa´n nhˆa´t. . . . . • Chuong 4 d¯ˆe` cˆa.p d¯ˆe´n kh´ainiˆe.m vˆe` cˆay. U´ ng du. ng cu˙’a cˆayHuffman trong n´end˜u . liˆe.u. Ngo`aira xˆaydu. ng c´acthuˆa.t to´ant`ımcˆaybao tr`umnho˙’ nhˆa´t. . . . . • B`aito´anEuler v`ab`aito´anHamilton v`anh˜ung mo˙’ rˆo.ng cu˙’a ch´ungs˜ed¯uo. c n´oid¯ˆe´n trong Chu.o.ng 5. . . . • Chuong 6 nghiˆenc´uu c´act´ınhchˆa´t phˇa˙’ng cu˙’a d¯ˆo` thi.; v`acuˆo´i c`ung . . • Chuong 7 t`ımhiˆe˙’u c´acb`aito´antrˆenma.ng vˆa.n ta˙’i. . . Ngo`aira, phˆa`n phu. lu. c tr`ınhb`ayc´accˆa´u tr´ucd˜u liˆe.u v`anh˜ung thu˙’ tu. c cˆa`n thiˆe´t d¯ˆe˙’ . . . . . d¯on 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. c biˆensoa.n lˆa`n d¯ˆa`u tiˆennˆenkhˆongtr´anhkho˙’i kh´anhiˆe` u thiˆe´u s´ot.T´ac . . gia˙’ mong c´onh˜ung d¯´ongg´opt`u ba.n d¯o.c. . . . . . . . . Tˆoixin ca˙’m on nh˜ung gi´upd¯˜o d¯˜anhˆa.n d¯uo. c t`u nhiˆe` u ngu`oi m`akhˆongthˆe˙’ liˆe.t kˆe hˆe´t, d¯ˇa.c biˆe.t l`ac´acba.n sinh viˆen,trong qu´atr`ınhbiˆensoa.n gi´aotr`ınhn`ay. D- `aLa.t, ng`ay5 th´ang3 nˇam2002 . PHA. M Tiˆe´n Son 8
9. Chu.o.ng 1 . . D- a.i cuong vˆe` d¯ˆo` thi. 1.1 D- .inh ngh˜ıav`ac´ackh´ainiˆe.m . . 1.1.1 D- `ˆo thi. c´ohu´ong . . . D- `ˆo thi. c´ohu´ong G = (V, E) gˆo`m mˆo.t tˆa.p V c´acphˆa`n tu˙’ go.i l`a d¯ı˙’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´oi mˆo.t cˇa.p c´acd¯ı˙’nh d¯uo. c sˇa´p th´u tu. . Nˆe´u . . . . . . . c´od¯´ungmˆo.t cung e tuong ´ung c´acd¯ı˙’nh d¯uo. c sˇa´p th´u tu. (a, b), ta s˜eviˆe´t e := (a, b). . . . Ch´ungta s˜egia˙’ su˙’ c´acd¯ı˙’nh d¯uo. c d¯´anhsˆo´ l`a v1, v2, . . . , vn hay gia˙’n tiˆe.n, 1, 2, . . . , n, trong d¯´o n = #V l`asˆo´ c´acd¯ı˙’nh cu˙’a d¯ˆo` thi . . . . . . . Nˆe´u e l`amˆo.t cung tuong ´ung cˇa.p c´acd¯ı˙’nh d¯uo. c sˇa´p th´u tu. vi v`a vj th`ıd¯ı˙’nh vi go.i l`a . . gˆo´c v`ad¯ı˙’nh vj go.i l`a ngo. n; cung e go.i l`a liˆenthuˆo. c hai d¯ı˙’nh vi v`a vj. Ch´ungta s˜ethu`ong . . . . k´yhiˆe.u m = #E−sˆo´ ca.nh cu˙’a d¯ˆo` thi. G. C´acca.nh 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. c biˆe˙’u diˆe˜n bo˙’ i c´acd¯iˆe˙’m, v`a e = (vi, vj) d¯uo. c biˆe˙’u . diˆe˜n bo˙’ i mˆo.t cung nˆo´i c´acd¯iˆe˙’m vi v`a vj. . Mˆo.t cung c´ogˆo´c tr`ungv´oi ngo.n go.i l`a khuyˆen. . . Nˆe´u c´onhiˆe` u hon mˆo.t cung v´oi gˆo´c ta.i vi v`ango.n ta.i vj th`ı G go.i l`a d¯ad¯ˆo` thi. v`ac´ac . . . . . . cung tuong ´ung go.i l`a song song. D- on d¯ˆo` thi. c´ohu´ong l`ad¯ˆo` thi. khˆongkhuyˆentrong d¯´ohai d¯ı˙’nh bˆa´t k`y vi v`a vj c´onhiˆe` u nhˆa´t mˆo.t cung (vi, vj). Chˇa˙’ng ha.n, d¯ˆo` thi. trong H`ınh1.1 c´o . . . cung e8 l`akhuyˆen;c´accung e4 v`a e9 l`asong song do c`ungtuong ´ung cˇa.p d¯ı˙’nh v3 v`a v4. 9
10. e4 v e v 2 . 3 3 . •• . • v4 . . . . . . . . . . e . . . 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . e e . e 1 . 2 6 . 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e5 . • • v v 5 1 . . . . e8 . . H`ınh1.1: V´ıdu. cu˙’a 2−d¯ˆo` thi. c´ohu´ong. 1.1.2 D- `ˆo thi. v`a´anhxa. d¯atri. . V´oi mˆo˜i x ∈ V, k´yhiˆe.u Γ(x) := {y ∈ V | (x, y) ∈ E}. Khi d¯´ota c´omˆo.t ´anhxa. d¯atri. V −1 . . Γ: V → 2 , x 7→ Γ(x). K´yhiˆe.u Γ l`a´anhxa. (d¯atri.) nguo. c cu˙’a Γ. . . . . Nˆe´u G l`ad¯on d¯ˆo` thi., th`ıd¯ˆo` thi. n`ayho`anto`and¯uo. c x´acd¯i.nh bo˙’ i tˆa.p V v`a´anhxa. d¯a . V tri. Γ t`u V v`ao2 . V`ıvˆa.y, d¯ˆo` thi. n`ayc`onc´othˆe˙’ k´yhiˆe.u l`a G = (V, Γ). . . . Nˆe´u xo´acung e9 trong H`ınh1.1 ta nhˆa.n d¯uo. c d¯on d¯ˆo` thi. v`ado d¯´oc´othˆe˙’ biˆe˙’u diˆe˜n . . . . bo˙’ i ´anhxa. d¯atri. Γ. Trong tru`ong ho. p n`ayta c´o Γ(v1) = {v2}, Γ(v2) = {v1, v3}, Γ(v3) = {v4, v5}, Γ(v4) = {v5}, Γ(v5) = {v1, v5}. . . 1.1.3 D- `ˆo thi. vˆohu´ong . Khi nghiˆenc´uu mˆo.t sˆo´ t´ınhchˆa´t cu˙’a c´acd¯ˆo` thi., ta thˆa´y rˇa`ng ch´ungkhˆongphu. thuˆo.c v`ao . . . . . hu´ong cu˙’a c´accung, t´uc l`akhˆongcˆa`n phˆanbiˆe.t su. kh´acnhau gi˜ua c´acd¯iˆe˙’m bˇa´t d¯ˆa`u v`a . . kˆe´t th´uc.D- iˆe` u n`ayd¯on gia˙’n l`amˆo˜i khi c´o´ıtnhˆa´t mˆo.t cung gi˜ua hai d¯ı˙’nh ta khˆongquan . . tˆamd¯ˆe´n th´u tu. cu˙’a ch´ung. . . . . . . . . V´oi mˆo˜i cung, t´uc l`amˆo˜i cˇ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. Tuong d¯uong, ta n´oirˇa`ng ca.nh l`amˆo.t cung m`ahu´ong d¯˜abi. bo˙’ . . . quˆen. Vˆe` h`ınhho.c, ca.nh (vi, vj) d¯uo. c biˆe˙’u diˆe˜n bo˙’ i c´acd¯oa.n thˇa˙’ng (hoˇa.c cong) v`akhˆong . . . c´om˜uitˆenliˆenthuˆo.c hai d¯iˆe˙’m tuong ´ung hai d¯ı˙’nh vi v`a vj. 10
11. . . . . Nghiˆenc´uu c´act´ınhchˆa´t vˆohu´ong cu˙’a d¯ˆo` thi. G = (V, E) d¯ua vˆe` kha˙’o s´attˆa.p E l`a . . . . tˆa.p c´ac ca. nh, t´uc l`a,mˆo.t tˆa.p h˜uu ha.n c´acphˆa`n tu˙’ m`amˆo˜i phˆa`n tu˙’ l`amˆo.t cˇa.p hai d¯ı˙’nh phˆanbiˆe.t hay d¯ˆo`ng nhˆa´t cu˙’a V. . . . D- a d¯ˆo` thi. vˆohu´ong l`ad¯ˆo` thi. m`ac´othˆe˙’ c´onhiˆe` u hon mˆo.t ca.nh liˆenthuˆo.c hai d¯ı˙’nh. . D- `ˆo thi. go.i l`a d¯on nˆe´u n´okhˆongc´okhuyˆenv`ahai d¯ı˙’nh bˆa´t k`yc´onhiˆe` u nhˆa´t mˆo.t ca.nh liˆenthuˆo.c ch´ung. e4 v2 e3 v3 . v •• . • 4 . . . . . . . . e . . . 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . . e e . e 1 . . 2 6 . 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e5 . • • v .v5 1 . . . . . . e8 . . . . . H`ınh1.2: D- `ˆo thi. vˆohu´ong tuong ´ung d¯ˆo` thi. trong H`ınh1.1. 1.1.4 C´acd¯i.nh ngh˜ıach´ınh Hai cung, hoˇa.c hai ca.nh go.i l`a kˆe` nhau nˆe´u ch´ungc´o´ıtnhˆa´t mˆo.t d¯ı˙’nh chung. Chˇa˙’ng ha.n, hai ca.nh e1 v`a e3 trong H`ınh1.2 l`akˆe` nhau. Hai d¯ı˙’nh vi v`a vj go.i l`a kˆe` nhau nˆe´u tˆo`n ta.i ca.nh hoˇa.c cung ek liˆenthuˆo.c ch´ung.V´ıdu. trong H`ınh1.2 hai d¯ı˙’nh v2 v`a v3 l`akˆe` nhau (liˆen . . thuˆo.c bo˙’ i ca.nh e3), nhung d¯ı˙’nh v2 v`a v5 khˆongkˆe` nhau. . Bˆa.c v`anu˙’ a bˆa.c + + . Bˆa. c ngo`ai cu˙’a d¯ı˙’nh v ∈ V, k´yhiˆe.u dG(v) (hay d (v) nˆe´u khˆongso. nhˆa`m lˆa˜n) l`asˆo´ c´accung − − . c´od¯ı˙’nh v l`agˆo´c. Bˆa. c trong cu˙’a d¯ı˙’nh v ∈ V, k´yhiˆe.u dG(v) (hay d (v) nˆe´u khˆongso. nhˆa`m lˆ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`ınh1.1 c´o d (v2) = 2, d (v2) = 1. 11
12. 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˙’a d¯ˆo` thi. G, t´uc l`a Xn Xn + − d (vi) = d (vi) = m. i=1 i=1 . . . Nˆe´u G l`ad¯ˆo` thi. vˆohu´ong, bˆa. c cu˙’a d¯ı˙’nh v ∈ V, k´yhiˆe.u dG(v) (hay d(v) nˆe´u khˆongso. . . . nhˆa`m lˆa˜n) l`asˆo´ c´acca.nh liˆenthuˆo.c d¯ı˙’nh v v´oi khuyˆend¯uo. c d¯ˆe´m hai lˆa`n. V´ıdu. d¯ˆo` thi. vˆo . . hu´ong trong H`ınh1.2 c´o d(v2) = 3, d(v5) = 5. C´accung (ca.nh) liˆenthuˆo.c tˆa.p A ⊂ V. C´acd¯ˆo´i chu tr`ınh . + Gia˙’ su˙’ A ⊂ V. K´yhiˆe.u ω (A) l`atˆa.p tˆa´t ca˙’ 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.p tˆa´t ca˙’ 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.c ca.nh c´oda.ng ω(A) go.i l`a d¯ˆo´i chu tr`ınh cu˙’a d¯ˆ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.c ca.nh) e ∈ E c´otuong ´ung mˆo.t sˆo´ thu. c w(e) go.i . . l`atro.ng luo. ng cu˙’a cung e. . D- `ˆo thi. d¯ˆo´i x´ung . . . D- `ˆo thi. c´ohu´ong go.i l`a d¯ˆo´i x´ung nˆe´u c´obao nhiˆeucung da.ng (vi, vj) th`ıc˜ungc´obˆa´y nhiˆeu cung da.ng (vj, vi). . D- `ˆo thi. pha˙’n d¯ˆo´i x´ung . . . D- `ˆo thi. c´ohu´ong go.i l`a pha˙’n d¯ˆo´i x´ung nˆe´u c´ocung da.ng (vi, vj) th`ıkhˆongc´ocung da.ng (vj, vi). 12
13. D- `ˆo thi. d¯ˆa` y d¯u˙’ . . D- `ˆo thi. vˆohu´ong go.i l`a d¯ˆa`y d¯u˙’ nˆe´u hai d¯ı˙’nh bˆa´t k`y vi v`a vj tˆo`n ta.i mˆo.t ca.nh da.ng (vi, vj). . . . . . D- on d¯ˆo` thi. vˆohu´ong d¯ˆa`y d¯u˙’ n d¯ı˙’nh d¯uo. c k´yhiˆe.u l`a Kn. D- `ˆo thi. con . . . . Gia˙’ su˙’ A ⊂ V. D- `ˆo thi. con d¯uo. c sinh bo˙’ i tˆa.p A l`ad¯ˆo` thi. GA := (A, EA) trong d¯´oc´acd¯ı˙’nh l`a . c´acphˆa`n tu˙’ cu˙’a tˆa.p A v`ac´accung trong EA l`ac´accung cu˙’a G m`ahai d¯ı˙’nh n´oliˆenthuˆo.c thuˆo.c tˆa.p A. . . Nˆe´u G l`ad¯ˆo` thi. biˆe˙’u diˆe˜n ba˙’n d¯ˆo` giao thˆongcu˙’a nu´oc Viˆe.t Nam th`ıd¯ˆo` thi. biˆe˙’u diˆe˜n ba˙’n d¯ˆo` giao thˆongcu˙’a th`anhphˆo´ D- `aLa.t l`amˆo.t d¯ˆo` thi. con. D- `ˆo thi. bˆo. phˆa.n . . X´etd¯ˆo` thi. G = (V, E) v`a U ⊂ E. D- `ˆo thi. bˆo. phˆa. n sinh bo˙’ i tˆa.p U l`ad¯ˆo` thi. v´oi tˆa.p d¯ı˙’nh V v`ac´accung thuˆo.c U (c´accung cu˙’a E \ U bi. xo´akho˙’i G). D- `ˆo thi. con bˆo. phˆa.n . X´etd¯ˆo` thi. G = (V, E) v`a A ⊂ V, U ⊂ E. D- `ˆo thi. con bˆo. phˆa. n sinh bo˙’ i tˆa.p A v`a U l`ad¯ˆo` thi. . bˆo. phˆa.n cu˙’a GA sinh bo˙’ i U. 1.2 Ma trˆa.n biˆe˙’u diˆe˜n d¯ˆo` thi. 1.2.1 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung Ma trˆa. n liˆenthuˆo. c d¯ı˙’nh-cung cu˙’a d¯ˆ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`n tu˙’ 0, 1 v`a −1, trong d¯´omˆo˜i cˆo.t biˆe˙’u diˆe˜n mˆo.t cung cu˙’a G v`amˆo˜i . h`angbiˆe˙’u diˆe˜n mˆo.t d¯ı˙’nh cu˙’a G. Nˆe´u ek = (vi, vj) ∈ E th`ıtˆa´t ca˙’ c´acphˆa`n tu˙’ cu˙’a cˆo.t k bˇa`ng . khˆongngoa.i tr`u aik = 1, ajk = −1. 13
14. V´ıdu. 1.2.1 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi. trong H`ınh1.3 l`a e1 e2 e3 e4 e5   a +1 +1 0 0 0   b  −1 0 +1 +1 0   . c  0 −1 −1 0 +1  d 0 0 0 −1 −1 e a . 1 b •• . . . . . . . e4 . . . . . . . e . 3 . . . . . . . . e2 . . . . . •• d e5 c H`ınh1.3: . Nhˇa´c la.i rˇa`ng, ma trˆa.n vuˆonggo.i l`a unimodular nˆe´u d¯i.nh th´uc cu˙’a n´obˇa`ng 1 hoˇa.c −1. Ma trˆa.n A cˆa´p m × n go.i l`a total unimodular nˆe´u tˆa´t ca˙’ c´acma trˆa.n vuˆongcon khˆong suy biˆe´n cu˙’a A l`aunimodular. Mˆe.nh d¯ˆe` 1.2.2 Ma trˆa. n liˆenthuˆo. c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi. G = (V, E) l`atotal unimodular. . . Ch´ung minh. Ch´u´yrˇa`ng ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi. G = (V, E) ch´ua d¯´ung . . hai phˆa`n tu˙’ kh´ackhˆongtrˆenmˆo˜i cˆo.t, mˆo.t bˇa`ng 1 v`amˆo.t bˇa`ng −1. Do d¯´ota c´othˆe˙’ ch´ung . minh theo quy na.p nhu sau: Hiˆe˙’n nhiˆen,tˆa´t ca˙’ c´acma trˆa.n vuˆongcon khˆongsuy biˆe´n cˆa´p 1 . cu˙’a A l`amodular; gia˙’ su˙’ khˇa˙’ng d¯i.nh d¯´ungcho mo.i ma trˆa.n con khˆongsuy biˆe´n cˆa´p (k − 1). 0 0 . . X´etma trˆa.n vuˆongcon A cˆa´p k cu˙’a A. Nˆe´u mˆo˜i cˆo.t cu˙’a A ch´ua d¯´unghai phˆa`n tu˙’ kh´ackhˆongth`ıdet(A0) = 0 (thˆa.t vˆa.y, tˆo˙’ng tˆa´t ca˙’ c´ach`angcu˙’a A0 l`avector khˆong,do d¯´oc´ac 0 . h`angl`ad¯ˆo.c lˆa.p tuyˆe´n t´ınh). Nˆe´u tˆo`n ta.i mˆo.t cˆo.t cu˙’a A khˆongc´ophˆa`n tu˙’ kh´ackhˆongth`ı 0 0 . det(A ) = 0. Cuˆo´i c`ung,nˆe´u tˆo`n ta.i cˆo.t j cu˙’a A sao cho c´od¯´ungmˆo.t phˆa`n tu˙’ kh´ackhˆong 0 00 00 aij (bˇa`ng 1, hay −1) th`ıdet(A ) = ± det(A ), trong d¯´o A l`ama trˆa.n vuˆongcˆa´p (k − 1) . . . 0 0 nhˆa.n d¯uo. c t`u A bˇa`ng c´ach xo´ah`ang i v`acˆo.t j. Theo gia˙’ thiˆe´t quy na.p, det(A ) bˇa`ng 1, −1 . . . hay 0 v`ado d¯´omˆe.nh d¯ˆe` d¯uo. c ch´ung minh. / 14
15. 1.2.2 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh . . X´etd¯ˆo` thi. vˆohu´ong G = (V, E). Ma trˆa. n liˆenthuˆo. c d¯ı˙’nh-ca. nh cu˙’a d¯ˆo` thi. G l`ama trˆa.n . . A = (aij), i = 1, 2, . . . , n, j = 1, 2, . . . , m, v´oi c´acphˆa`n tu˙’ 0 v`a1, trong d¯´omˆo˜i cˆo.t biˆe˙’u diˆe˜n mˆo.t ca.nh cu˙’a G v`amˆo˜i h`angbiˆe˙’u diˆe˜n mˆo.t d¯ı˙’nh cu˙’a G; ngo`aira, nˆe´u ca.nh ek liˆenthuˆo.c . . hai d¯ı˙’nh vi v`a vj th`ıtˆa´t ca˙’ c´acphˆa`n tu˙’ cu˙’a cˆo.t k bˇa`ng khˆongngoa.i tr`u aik = 1, ajk = 1. V´ıdu. 1.2.3 Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh cu˙’a d¯ˆo` thi. trong H`ınh1.4 l`a e1 e2 e3 e4 e5   a 1 1 0 0 0   b  1 0 1 1 0    c  0 1 1 0 1  d 0 0 0 1 1 a e1 b •• . . . . . . . e4 . . . . . . . . . . e . 3 . . . . . . . e . 2 . . . . . •• d e5 c H`ınh1.4: . Tr´aiv´oi ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung, n´oichung ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh khˆong total unimodular. Chˇa˙’ng ha.n, trong v´ıdu. trˆen,ma trˆa.n con   1 1 0    1 0 1  0 1 1 . c´od¯i.nh th´uc bˇa`ng −2. . . D- `ˆo thi. vˆohu´ong G = (V, E) go.i l`a hai 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´i v´oi mˆo˜i ca.nh (vi, vj) ∈ E th`ıhoˇa.c vi ∈ V1, vj ∈ V2 hoˇa.c vj ∈ V1, vi ∈ V2. 15
16. a b •• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ••• c d e H`ınh1.5: D- `ˆo thi. hai phˆa`n K2,3. V´ıdu. 1.2.4 Dˆe˜ kiˆe˙’m tra d¯ˆo` thi. K2,3 trong H`ınh1.5 l`ahai phˆa`n. . . Mˆe.nh d¯ˆe` 1.2.5 Ma trˆa. n liˆenthuˆo. c d¯ı˙’nh-ca. nh cu˙’a d¯ˆo` thi. vˆohu´ong G = (V, E) l`atotal unimodular nˆe´u v`achı˙’ nˆe´u G l`ad¯ˆo` thi. hai phˆa`n. . . Ch´ung minh. (1) Nˆe´u d¯ˆo` thi. l`ahai phˆa`n, th`ıch´ungta c´othˆe˙’ ch´ung minh theo quy na.p rˇa`ng . mo.i ma trˆa.n vuˆongcon B cu˙’a ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh c´od¯i.nh th´uc det(B) = 0, 1 hoˇa.c . . . −1. D- iˆe` u n`ayd¯´ungv´oi c´acma trˆa.n vuˆongcon cˆa´p 1; gia˙’ su˙’ khˇa˙’ng d¯i.nh d¯´ungv´oi c´acma trˆa.n vuˆongcon cˆa´p (k − 1). X´etma trˆa.n vuˆongcon B cˆa´p k. j . . Nˆe´u mˆo˜i cˆo.t B cu˙’a B ch´ua d¯´unghai phˆa`n tu˙’ bˇa`ng 1 th`ı X X Bi = Bi, i∈I1 i∈I2 . . . trong d¯´o I1 v`a I2 l`ac´actˆa.p chı˙’ sˆo´ tuong ´ung hai phˆanhoa.ch cu˙’a tˆa.p c´acd¯ı˙’nh V v`a Bi l`a vector h`angcu˙’a B. C´acvector h`angphu. thuˆo.c tuyˆe´n t´ınh,nˆendet(B) = 0. . . . Nˆe´u, nguo. c la.i, tˆo`n ta.i cˆo.t c´od¯´ungmˆo.t phˆa`n tu˙’ bˇa`ng 1, chˇa˙’ng ha.n bij = 1, k´yhiˆe.u C . . . l`ama trˆa.n nhˆa.n d¯uo. c t`u B bˇa`ng c´ach xo´ah`ang i v`acˆo.t j. Th`ı det(B) = ± det(C) (= 0, 1 hoˇa.c − 1 theo quy na.p). . (2) Mˇa.t kh´ac,dˆe˜ d`angch´ung minh rˇa`ng ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh cu˙’a d¯ˆo` thi. l`amˆ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`n nˆe´u v`achı˙’ nˆe´u G khˆongch´ua chu tr`ınhc´od¯ˆo. d`aile˙’. . . . Ch´ung minh. D- iˆe` u kiˆe.n cˆa`n. Do V d¯uo. c phˆanhoa.ch th`anh V1 v`a V2 : V = V2 ∪ V2,V1 ∩ V2 = ∅. 16
17. Gia˙’ thiˆe´t tˆo`n ta.i mˆ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.t d¯ı˙’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˙’ i vˆa.y vi1 ∈ V2. Diˆeu n`aymˆauthuˆan v´oi V1 ∩ V2 = ∅. . D- iˆe` u kiˆe.n d¯u˙’. Khˆongmˆa´t t´ınhtˆo˙’ng qu´atgia˙’ thiˆe´t d¯ˆo` thi. G liˆenthˆong.Gia˙’ su˙’ khˆongtˆo`n ta.i chu tr`ınhc´od¯ˆo. d`aile˙’. Cho.n d¯ı˙’nh bˆa´t k`y,chˇa˙’ng ha.n vi v`ag´annh˜ancho n´ol`a“ + ”. Sau d¯´olˇa.p la.i c´acph´ep to´ansau: . . . . . Cho.n d¯ı˙’nh d¯˜ad¯uo. c g´annh˜an vj v`ag´annh˜annguo. c v´oi nh˜ancu˙’a vj cho tˆa´t ca˙’ c´ac . d¯ı˙’nh kˆe` v´oi d¯ı˙’nh vj. . . . Tiˆe´p tu. c qu´atr`ınhn`aycho d¯ˆe´n khi xa˙’y ra mˆo.t trong hai tru`ong ho. p: . . (a) Tˆa´t ca˙’ c´acd¯ı˙’nh d¯˜ad¯uo. c g´annh˜anv`ahai d¯ı˙’nh bˆa´t k`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ˆon ta.i d¯ınh, chˇang ha.n vjk , d¯uo. c g´anhai nh˜ankh´acnhau. . . . . . Trong Tru`ong ho. p (a), d¯ˇa.t V1 l`atˆa.p tˆa´t ca˙’ c´acd¯ı˙’nh d¯uo. c g´annh˜an“+” v`a V2 l`atˆa.p tˆa´t . . . ca˙’ c´acd¯ı˙’nh d¯uo. c g´annh˜an“−”. Do tˆa´t ca˙’ c´acca.nh liˆenthuˆo.c gi˜ua c´accˇa.p d¯ı˙’nh c´onh˜an kh´acnhau nˆend¯ˆo` thi. G l`ahai phˆa`n. . . . ˙’ . . ` Trong Tru`ong ho. p (b), d¯ınh vjk d¯uo. c g´annh˜an“+” do.c theo mˆo.t dˆaychuyˆen µ1 n`ao . . . . d¯´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´ucta.i . . . ˙’ . . ` . vjk . Tuong tu. , d¯ınh vjk d¯uo. c g´annh˜an“−” do.c theo mˆo.t dˆaychuyˆen µ2 n`aod¯´o,v´oi c´ac ˙’ . . ´ . ´ . d¯ınh d¯uo. c g´annh˜an“+” v`a“−” xen k˜enhau xuˆat ph´att`u vi v`akˆet th´ucta.i vjk . Nhung . ´ . ˙’ ´ ˙’ . . nhu thˆe chu tr`ınhd¯ido.c theo µ1 t`u d¯ınh vi d¯ˆen d¯ınh vjk sau d¯´od¯inguo. c la.i do.c theo µ2 . . . vˆe` la.i vi c´od¯ˆo. d`aile˙’.D- iˆe` u n`aymˆauthuˆa˜n v´oi gia˙’ thiˆe´t, v`ado d¯´okhˆongthˆe˙’ xa˙’y ra Tru`ong . . . . ho. p (b). D- .inh l´yd¯uo. c ch´ung minh. / 1.2.3 Ma trˆa.n kˆe` hay ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-d¯ı˙’nh . Gia˙’ su˙’ G = (V, E) l`ad¯ˆo` thi. sao cho c´onhiˆe` u nhˆa´t mˆo.t cung liˆenthuˆo.c hai d¯ı˙’nh bˆa´t k`y vi v`a vj. Ma trˆa. n kˆe` hay ma trˆa. n liˆenthuˆo. c d¯ı˙’nh-d¯ı˙’nh l`ama trˆa.n vuˆong A = (aij) cˆa´p n × n 17
18. . . v´oi c´acphˆa`n tu˙’ 0 hoˇa.c 1: ( 1 nˆe´u (vi, vj) ∈ E, aij := . . 0 nˆe´u nguo. c la.i. . . . . . . . . Trong tru`ong ho. p d¯ˆo` thi. vˆohu´ong, ma trˆa.n kˆe` cu˙’a d¯on d¯ˆo` thi. c˜ungc´othˆe˙’ d¯uo. c d¯i.nh . . . . . ngh˜ıabˇa`ng c´ach xem mˆo˜i ca.nh (vi, vj) tuong ´ung hai cung (vi, vj) v`a(vj, vi). Trong tru`ong . . ho. p n`ay, ma trˆa.n kˆe` l`ad¯ˆo´i x´ung. 1.2.4 C´acbiˆe˙’u diˆe˜n cu˙’a d¯ˆo` thi. . . D- ˆe˙’ mˆota˙’ mˆo.t d¯ˆo` thi., ta c´othˆe˙’ su˙’ du. ng mˆo.t sˆo´ c´ach biˆe˙’u diˆe˜n kh´acnhau. V´oi quan d¯iˆe˙’m . . . . lˆa.p tr`ınh,n´oichung c´acbiˆe˙’u diˆe˜n n`aykhˆongtuong d¯uong theo kh´ıaca.nh hiˆe.u qua˙’ cu˙’a thuˆa.t to´an. . . C´ohai c´ach biˆe˙’u diˆe˜n ch´ınh: Th´u nhˆa´t, su˙’ du. ng ma trˆa.n kˆ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´t cu˙’a n´o. . Su˙’ du. ng ma trˆa.n kˆe` . . Ch´ungta biˆe´t rˇa`ng c´acma trˆa.n kˆe` cho ph´epmiˆeuta˙’ hoˇa.c c´ac1-d¯ˆo` thi. d¯i.nh hu´ong, hoˇa.c . . . . . . c´acd¯on d¯ˆo` thi. vˆohu´ong. V´oi c´ach biˆe˙’u diˆe˜n d¯ˆo` thi. qua ma trˆa.n kˆe` , ta thˆa´y sˆo´ luo. ng thˆong . . 2 . . . . tin, gˆo`m c´acbit 0 v`a1, cˆa`n luu tr˜u l`a n . C´acbit c´othˆe˙’ d¯uo. c kˆe´t ho. p trong c´act`u. K´y . . . hiˆe.u w l`ad¯ˆo. d`aicu˙’a t`u (t´uc l`asˆo´ c´acbit trong mˆo.t t`u m´ayt´ınh).Khi d¯´omˆo˜i h`angcu˙’a ma . . . . 1 . . . trˆa.n kˆe` c´othˆe˙’ d¯uo. c viˆe´t nhu mˆ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.n kˆe` l`a ndn/we. . . . . . . Ma trˆa.n kˆe` cu˙’a d¯ˆo` thi. vˆohu´ong l`ad¯ˆo´i x´ung, nˆenta chı˙’ cˆa`n luu tr˜u nu˙’ a tam gi´actrˆen . . . . cu˙’a n´o,v`ado d¯´ochı˙’ cˆa`n n(n − 1)/2 bit. Tuy nhiˆen,v´oi c´ach luu tr˜u n`ay, s˜etˇangd¯ˆo. ph´uc . ta.p v`ath`oi gian t´ınhto´antrong mˆo.t sˆo´ b`aito´an. . . . . 2 . . . 1 Trong tru`ong ho. p c´acma trˆa.n thua (m ¿ n v´oi d¯ˆo` thi. c´ohu´ong; m ¿ n(n + 1) d¯ˆo´i . . . 2 v´oi d¯ˆo` thi. vˆohu´ong) c´ach biˆe˜u diˆe˜n n`ayl`al˜angph´ı.Do d¯´ota s˜et`ımc´ach biˆe˙’u diˆe˜n chı˙’ c´ac phˆa`n tu˙’. kh´ackhˆong. . . . V`ımu. c d¯´ıch n`ayta s˜esu˙’ du. ng mˆo.t ma˙’ng danh s´ach kˆe` cho d¯ˆo` thi. c´ohu´ong. D- `ˆo thi. c´o . . . . . hu´ong d¯uo. c biˆe˙’u diˆe˜n bo˙’ i mˆo.t ma˙’ng c´accon tro˙’ V out[1],V out[2], ,V out[n], trong d¯´o . . . . . . . mˆo˜i con tro˙’ tuong ´ung v´oi mˆo.t d¯ı˙’nh trong d¯ˆo` thi. c´ohu´ong. Mˆo˜i phˆa`n tu˙’ cu˙’a ma˙’ng V out[i] . . . . . . . chı˙’ d¯ˆe´n mˆo.t n´utd¯ˆa`u luu tr˜u mu. c d˜u liˆe.u cu˙’a n´uttuong ´ung d¯ı˙’nh vi v`ach´ua mˆo.t con tro˙’ 1 . K´yhiˆe.u dxe l`asˆo´ nguyˆennho˙’ nhˆa´t khˆongb´ehon x. 18
19. . . . . . . chı˙’ d¯ˆe´n mˆo.t danh s´ach liˆenkˆe´t cu˙’a c´acd¯ı˙’nh kˆe` (d¯ı˙’nh d¯uo. c nˆo´i v´oi vi theo hu´ong t`u vi ra). Mˆo˜i n´utkˆe` c´ohai tru.`o.ng: . . . . 1. Tru`ong sˆo´ nguyˆen: luu tr˜u sˆo´ hiˆe.u cu˙’a d¯ı˙’nh kˆe` ; v`a 2. Tru.`o.ng liˆenkˆe´t chı˙’ d¯ˆe´n n´utkˆe´ tiˆe´p trong danh s´ach kˆe` n`ay. v1 v2 •• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v6 • . • . . . . . . . . . v3 . . . . . . . . . . . . . . . . . . . . . . . . . . .•• v5 v4 H`ınh1.6: . . . . C´ach biˆe˙’u diˆe˜n ma˙’ng danh s´ach kˆe` V out[] cu˙’a d¯ˆo` thi. c´ohu´ong trong H`ınh1.6 d¯uo. c . . . . . . . . . . cho tuong ´ung trong H`ınh1.7 (gia˙’ su˙’ c´acmu. c d˜u liˆe.u tuong ´ung c´acd¯ı˙’nh theo th´u tu. l`a A, B, C, D, E, F ). N´utd¯ˆ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`ınh1.7: Danh s´ach kˆe` V out[] tuong ´ung d¯ˆo` thi. trong H`ınh1.6. . Thay v`ıcon tro˙’ chı˙’ d¯ˆe´n mˆ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¯id¯ˆe´n vi v`ado d¯´oc´othˆe˙’ luu tr˜u d¯ˆo` thi. thˆongqua ma˙’ng c´acdanh s´ach 19
20. . . kˆe` V in[i]. H`ınh1.8 minh ho.a ma˙’ng c´acdanh s´ach kˆe` V in[] cu˙’a d¯ˆo` thi. c´ohu´ong trong H`ınh 1.6. . . . . D- ˆe˙’ ´yrˇa`ng, c´acsˆo´ trong n´utkˆe` cu˙’a V out[] (tuong ´ung, V in[]) l`anh˜ung chı˙’ sˆo´ cˆo.t . . . . (tuong ´ung, h`ang)trong ma trˆa.n kˆe` cu˙’a d¯ˆo` thi. m`ao˙’ d¯´osˆo´ 1 xuˆa´t hiˆe.n. Ngo`aira, trong . . . . . tru`ong ho. p d¯ˆo` thi. vˆohu´ong, hai danh s´ach kˆe` n`ayl`atr`ungnhau. . . . Khi d¯ˆo` thi. c´o tro. ng sˆo´, t´uc l`anˆe´u mˆo˜i cung hoˇa.c ca.nh e ∈ E c´omˆo.t tro.ng luo. ng w(e), . . . ta chı˙’ cˆa`n mo˙’ rˆo.ng cˆa´u tr´uccu˙’a mˆo˜i n´uttrong danh s´ach kˆe` bˇa`ng c´ach thˆemmˆo.t tru`ong . . . . luu tr˜u tro.ng luo. ng cu˙’a cung. . . . . C´ach biˆe˙’u diˆe˜n bˇa`ng danh s´ach kˆe` cu˙’a d¯ˆo` thi. c´ohu´ong c´othˆe˙’ d¯uo. c c`aid¯ˇa.t trong ngˆon . . . . ng˜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.t d¯ˆo` thi., ta c´othˆe˙’ su˙’ du. ng c´acthu˙’ tu. c MakeV out() v`aMakeV in() tu.o.ng ´u.ng. N´utd¯ˆ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`ınh1.8: Danh s´ach kˆe` V in[] tuong ´ung d¯ˆo` thi. trong H`ınh1.6. . Su˙’ du. ng c´acma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung hoˇa.c d¯ı˙’nh-ca.nh Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung hoˇa.c d¯ı˙’nh-ca.nh cho ph´epch´ungta mˆota˙’ d¯ˆa`y d¯u˙’ cˆa´u tr´uccu˙’a . mˆo.t d¯ad¯ˆo` thi. khˆongc´okhuyˆen. Tuy nhiˆen,do chı˙’ c´ohai phˆa`n tu˙’ kh´ackhˆongtrong mˆo˜i . . . cˆo.t, nˆenc´othˆe˙’ biˆe˙’u diˆe˜n thˆongtin o˙’ da.ng th´ıch ho. p hon. . Ch´ungta d¯i.nh ngh˜ıahai ma˙’ng tuyˆe´n t´ınh α[] v`a β[] chiˆe` u m trong d¯´ov´oi mˆo˜i cung hoˇa.c ca.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ˆen 20
21. v1 • . . . . . . . . . e 5 . . . . . . . . . . . . . . . . . . . e e e 1 . 2 . 3 . . . . . . . e4 . . . . . . . . . . . . . . . . . . e6 •• v2 . e8 v 3 . e7 H`ınh1.9: . . . . . thuˆo.c. Trong tru`ong ho. p c´ohu´ong, ch´ungta quyˆe´t d¯i.nh α[k] l`ad¯ı˙’nh gˆo´c v`a β[k] l`ad¯ı˙’nh ngo.n cu˙’a cung ek. . . Ch´u´yrˇa`ng, tr´aiv´oi ma trˆa.n kˆe` , c´ach biˆe˙’u diˆe˜n n`ayc˜ungc´othˆe˙’ d¯ˇa.c trung cho c´acd¯a d¯ˆo` thi. c´okhuyˆen. . . . . Chˇa˙’ng ha.n, d¯ad¯ˆo` thi. cu˙’a H`ınh1.9 trong d¯´oc´accung d¯uo. c d¯´anhsˆo´, ta nhˆa.n d¯uo. 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. p d¯ˆo` thi. c´otro.ng sˆo´, ta chı˙’ cˆa`n thˆemmˆo.t ma˙’ng w[] k´ıch thu´oc m luu . . . . . . . tr˜u tro.ng luo. ng cu˙’a mˆo˜i ca.nh hoˇa.c cung v´oi tuong ´ung mˆo.t-mˆo.t c´acma˙’ng α[] v`a β[]. . . . . Vˆe` c´ach kh´acbiˆe˙’u diˆe˜n hiˆe.u qua˙’ hon cu˙’a d¯ˆo` thi. vˆohu´ong su˙’ du. ng danh s´ach c´acca.nh xem [43]. . Mˆo´i liˆenhˆe. gi˜ua c´acbiˆe˙’u diˆe˜n . . . Dˆe˜ d`angthˆa´y rˇa`ng tˆo`n ta.i c´acthuˆa.t to´and¯ath´uc d¯ˆe˙’ chuyˆe˙’n d¯ˆo˙’i gi˜ua c´ackiˆe˙’u d˜u liˆe.u trˆen d¯ˆo` thi H`ınh1.10 minh ho.a c´ackha˙’ nˇangc´othˆe˙’ c´o. . . . . . D- ˆe˙’ chuyˆe˙’n d¯ˆo˙’i gi˜ua c´ackiˆe˙’u d˜u liˆe.u, cˆa`n c´acchuong tr`ınhthu. c hiˆe.n d¯iˆe` u n`ay(b`ai . . tˆa.p). C´acbiˆe˙’u diˆe˜n n`ayc´othˆe˙’ ca˙’i biˆencho ph`uho. p v´oi yˆeucˆa`u. Chˇa˙’ng ha.n, d¯ˆo` thi. c´o 21
22. . . Ma trˆa.n kˆe` d¯uo. c kˆe´t theo h`ang ↑| ↑| O(n2) O(m) ↓| ↓| . . . . Ma trˆa.n kˆe` da.ng tu`ong minh Ma trˆa.n kˆe` d¯uo. c kˆe´t theo cˆo.t ↑| ↑| O(mn) O(m) ↓| ↓| Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung hoˇa.c ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh hoˇa.c ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh . . da.ng tu`ong minh da.ng kˆe´t theo h`ang ↑| ↑| O(mn) O(m) ↓| ↓| Ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-cung hoˇa.c ma trˆa.n liˆenthuˆo.c d¯ı˙’nh-ca.nh da.ng kˆe´t theo cˆo.t . . H`ınh1.10: Mˆo´i liˆenhˆe. v`ad¯ˆo. ph´uc ta.p t´ınhto´ankhi chuyˆe˙’n d¯ˆo˙’i gi˜ua c´acbiˆe˙’u diˆe˜n kh´ac nhau trong d¯ˆo` thi . . . . . tro.ng sˆo´ c´othˆe˙’ d¯uo. c biˆe˙’u diˆe˜n bo˙’ i mˆo.t ma trˆa. n tro. ng luo. ng (c`ongo.i l`a ma trˆa. n chi ph´ı . . . hay khoa˙’ng c´ach) cˆa´p n × n trong d¯´ophˆa`n tu˙’ (i, j) bˇa`ng tro.ng luo. ng cu˙’a ca.nh hay cung (vi, vj). Tuy nhiˆen,cˆa`n ch´u´yrˇa`ng, t´ınhhiˆe.u qua˙’ cu˙’a nhiˆe` u vˆa´n d¯ˆe` phu. thuˆo.c v`aobiˆe˙’u diˆe˜n . . . cu˙’a d¯ˆo` thi Do d¯´o,viˆe.c cho.n lu. a c´accˆa´u tr´ucd˜u liˆe.u mˆo.t c´ach th´ıch ho. p l`aquan tro.ng. 22
23. 1.3 T´ınhliˆenthˆong 1.3.1 Dˆaychuyˆe` n v`achu tr`ınh . . . . Gia˙’ su˙’ v0, vk l`ac´acd¯ı˙’nh cu˙’a d¯ˆo` thi. vˆohu´ong 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´t d¯ˆa`u t`u v0 v`akˆe´t th´ucta.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˙’n tiˆe.n, ta thu`ong viˆe´t µ := {e1, e2, . . . , ek}. . . . . . . . Dˆaychuyˆe` n d¯uo. c go.i l`a d¯on gia˙’n (tuong ´ung, so cˆa´p) nˆe´u n´okhˆongd¯ihai lˆa`n qua . . . c`ungmˆo.t ca.nh (tuong ´ung, d¯ı˙’nh). . Chu tr`ınh l`amˆo.t dˆaychuyˆe` n trong d¯´od¯ı˙’nh d¯ˆa`u tr`ungv´oi d¯ı˙’nh cuˆo´i. Chu tr`ınhqua . . mˆo˜i ca.nh d¯´ungmˆo.t lˆa`n go.i l`a d¯on 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.t lˆa`n tr`u d¯ı˙’nh d¯ˆa`u tiˆenhai lˆa`n (mˆo.t lˆa`n l´ucxuˆa´t ph´atv`amˆo.t l´uctro˙’ vˆe` ). D- `ˆo thi. trong H`ınh1.11 c´o (a, e1, b, e2, c, e3, d, e4, b) . . l`adˆaychuyˆe` n t`u d¯ı˙’nh a d¯ˆe´n d¯ı˙’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). e1 b e2 . a ••• c . . . . e4 e3 . . . . . . • . . . . d e5 . e6 . . . . . . . . . . . . . . f ••• . g e7 e e8 H`ınh1.11: . . . . Trong tru`ong ho. p d¯ˆo` thi. khˆongc´o ca. nh song song (t´uc l`ahai d¯ı˙’nh c´onhiˆe` u nhˆa´t mˆo.t . . . ca.nh liˆenthuˆo.c ch´ung),d¯ˆe˙’ d¯on gia˙’n dˆaychuyˆe` n µ d¯uo. c viˆe´t la.i µ = {v0, v1, v2, . . . , vk}. 23
24. . . 1.3.2 D- u`ong d¯iv`ama.ch . . . . . . Gia˙’ su˙’ v0, vk l`ac´acd¯ı˙’nh cu˙’a d¯ˆo` thi. c´ohu´ong G := (V, E). D- u`ong 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´t d¯ˆa`u t`u v0 v`akˆe´t th´ucta.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˙’n tiˆe.n, ta c´othˆe˙’ k´y . . hiˆe.u d¯u`ong d¯i µ l`a {e1, e2, . . . , ek}. Do d¯´otrong H`ınh1.12 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`ong d¯il`a d¯on gia˙’n nˆe´u khˆongch´ua cung n`aoqu´amˆo.t lˆ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`ong d¯il`a so cˆa´p nˆe´u khˆongd¯iqua d¯ı˙’nh n`aoqu´amˆo.t lˆa`n. Khi d¯´od¯u`ong d¯i µ2 l`a . . . . . . . . . so cˆa´p nhung c´acd¯u`ong 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˙’n nhung nguo. c la.i khˆongnhˆa´t thiˆe´t d¯´ung.Chˇa˙’ng ha.n, ch´u´yrˇa`ng d¯u`ong d¯i µ1 l`ad¯on . . . . . . . . . . gia˙’n nhung khˆongso cˆa´p, d¯u`ong d¯i µ2 v`ua d¯on gia˙’n v`av`ua so cˆa´p, d¯u`ong d¯i µ3 khˆong d¯o.n gia˙’n c˜ungkhˆongso. cˆa´p. . . . . Ch´u´yrˇa`ng, kh´ainiˆe.m dˆaychuyˆe` n l`aba˙’n sao khˆongc´ohu´ong cu˙’a d¯u`ong d¯iv`a´ap . . du. ng cho c´acd¯ˆo` thi. m`akhˆongd¯ˆe˙’ ´yd¯ˆe´n hu´ong cu˙’a c´accung. . . . . . . . D- u`ong d¯ic˜ungc´othˆe˙’ d¯uo. c biˆe˙’u diˆe˜n bo˙’ i d˜ayc´acd¯ı˙’nh m`ach´ungd¯iqua trong tru`ong . . . . ho. p khˆongc´o cung song song (t´uc hai cung c´oc`unggˆo´c v`ac`ungngo.n). Do d¯´o,d¯u`ong d¯i . µ1 c´othˆe˙’ biˆe˙’u diˆe˜n bo˙’ i d˜ayd¯ı˙’nh {v2, v5, v4, v3, v5, v6}. . . . Ma. ch l`amˆo.t d¯u`ong d¯i {e1, e2, . . . , ek} trong d¯´od¯ı˙’nh gˆo´c cu˙’a cung e1 tr`ungv´oi d¯ı˙’nh . . ngo.n cu˙’a cung ek. Do d¯´od¯u`ong d¯i {e5, e9, e10, e6} trong H`ınh1.12 l`ama.ch. 1.3.3 T´ınhliˆenthˆong . . . D- `ˆo thi. vˆohu´ong go.i l`a liˆenthˆong nˆe´u tˆa´t ca˙’ c´accˇa.p d¯ı˙’nh vi v`a vj tˆo`n ta.i dˆaychuyˆe` n t`u vi d¯ˆe´n vj. Quan hˆe. viRvj nˆe´u v`achı˙’ nˆe´u vi = vj hoˇa.c tˆo`n ta.i mˆo.t dˆaychuyˆe` n nˆo´i hai d¯ı˙’nh vi . . . . . v`a vj l`a quan hˆe. tuong d¯uong (pha˙’n xa., d¯ˆo´i x´ung v`abˇa´c cˆa`u). 24
25. v2 • . . . . . . . e . 10 e . 1 . . . . . . . . . . . . . . v1 •. . • v3 . e . . . 3 . . . . . . . . . . . . . . . . . . . . . . e2 . . e7 e9 . . . . . . . . . . . . . . . . . . . . . . v6 • e6 . • v4 . . e8 . . . . . . . . e . e 4 . 5 . . . . . . . • v5 H`ınh1.12: . . . . . . . . . . L´op tuong 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.i l`a sˆo´ th`anhphˆa`n liˆenthˆong cu˙’a d¯ˆo` thi Theo d¯i.nh ngh˜ıa,d¯ˆo` thi. liˆenthˆongnˆe´u v`achı˙’ nˆe´u sˆo´ th`anhphˆa`n liˆenthˆongbˇa`ng mˆo.t. C´ac . d¯ˆ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ˆong cu˙’a d¯ˆo` thi Mˆo˜i th`anhphˆa`n liˆenthˆongl`amˆo.t d¯ˆo` thi. liˆenthˆong. H`ınh1.13 minh ho.a d¯ˆo` thi. c´oba th`anhphˆa`n liˆenthˆong. v1 v5 v3 . . . .• •. .• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •• ••. • v2 v4 v7 v8 v6 H`ınh1.13: D- `ˆo thi. c´oba th`anhphˆa`n liˆenthˆong. . . X´acd¯i.nh sˆo´ th`anhphˆa`n liˆenthˆongcu˙’a d¯ˆo` thi. l`amˆo.t trong nh˜ung b`aito´anco ba˙’n cu˙’a . . l´ythuyˆe´t d¯ˆo` thi. v`ac´onhiˆe` u ´ung du. ng trong thu. c tiˆe˜n; chˇa˙’ng ha.n, x´acd¯i.nh t´ınhliˆenthˆong cu˙’a ma.ch d¯iˆe.n, ma.ng d¯iˆe.n thoa.i, v.v. . Ch´ungta s˜etr`ınhb`aymˆo.t sˆo´ thuˆa.t to´anc´oth`oi gian O(m) gia˙’i b`aito´ann`ayv`ın´o 25
26. . cho ph´ept`ıml`oi gia˙’i cu˙’a mˆo.t sˆo´ b`aito´ankh´ac. . . . Bˇa´t d¯ˆa`u v´oi d¯ı˙’nh n`aod¯´ocu˙’a d¯ˆo` thi., ch´ungta liˆe.t kˆec´acd¯ı˙’nh theo th´u tu. cu˙’a thuˆa.t . . . to´an t`ımkiˆe´m theo chiˆe` u sˆau, t´uc l`ach´ungta d¯i,d¯ˆa`u tiˆen,xa nhˆa´t c´othˆe˙’ d¯uo. 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¯ˆaynhˆa´t m`ach´ungta . d¯˜abo˙’ qua, v`atiˆe´p tu. 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´t gˇa.p s˜e ta.o th`anhth`anhphˆa`n liˆenthˆongd¯ˆa`u tiˆen. . . . . Nˆe´u tˆa´t ca˙’ c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. d¯uo. c duyˆe.t th`ıd¯ˆo` thi. liˆenthˆong;nguo. c la.i, ch´ungta . . . . . . . . . kho˙’ i d¯ˆa`u la.i thu˙’ tu. c trˆenv´oi mˆo.t d¯ı˙’nh m´oi chua d¯uo. c viˆe´ng thˇam;do d¯´ota xˆaydu. ng d¯uo. c th`anhphˆa`n liˆenthˆongth´u. hai, v`avˆanvˆan. . . . Thuˆa.t to´andu´oi d¯ˆaytr`ınhb`aygiai d¯oa.n d¯ˆa`u tiˆen,t´uc l`at`ımth`anhphˆa`n liˆenthˆong . . ch´ua mˆo.t d¯ı˙’nh d¯˜acho-nˆe´u th`anhphˆa`n n`aych´ua tˆa´t ca˙’ c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. th`ıd¯ˆo` thi. liˆen thˆong. K´yhiˆe.u num(i) l`asˆo´ hiˆe.u cu˙’a d¯ı˙’nh vi trong qu´atr`ınht`ımkiˆe´m. Nˆe´u ta bˇa´t d¯ˆ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´oc d¯ı˙’nh vi trong cˆayc´ogˆo´c . . . . . . (xem Chuong 4) d¯uo. c xˆaydu. ng trong qu´atr`ınhthu. c hiˆe.n thuˆa.t to´an. . . ˙’ . - + + X´etd¯ˆo` thi. d¯uo. c biˆeu diˆe˜n bo˙’ i ´anhxa. d¯atri. Γ. Dˇa.t di l`asˆo´ c´acd¯ı˙’nh kˆe` d¯ı˙’nh vi : di := . . #Γ(vi). V´oi mˆ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. c hiˆe.n t`ımkiˆe´m trˆend¯ˆo` thi., ch´ungta cˆa`n mˆo˜i giai d¯oa.n cu˙’a thuˆa.t to´anchı˙’ sˆo´ . . . . n(i) cu˙’a d¯ı˙’nh d¯uo. c viˆe´ng thˇamcuˆo´i c`ungt`u d¯ı˙’nh vi. Do d¯´ota bˇa´t d¯ˆa`u v´oi n(i) = 0. . . . Du´oi d¯ˆayl`athuˆa.t to´an(da.ng khˆongd¯ˆe. qui) cu˙’a Tr´emauxd¯ua ra nˇa`m 1882 v`asau d¯´o . . d¯uo. c Tarjan ca˙’i tiˆe´n [53]. . Thuˆa.t to´anTr´emaux-Tarjan t`ımth`anhphˆa` n liˆenthˆongch´ua d¯ı˙’nh s. . - + . 1. [Kho˙’ i ta.o] Dˇa.t P (i) = 0, di := #Γ(vi) v`a n(i) = 0 v´oi mo.i d¯ı˙’nh vi, i = 1, 2, . . . , n; k = 0, num(s) = 1,P (s) = s (tu`y´y,kh´ackhˆong), i = s. . . . 2. [Bu´oc lˇa.p] Trong khi (n(i) 6= d(i)) hoˇa.c (i 6= s) thu. c hiˆe.n . . • Nˆe´u n(i) = d(i) d¯ˇa.t i = P (i) (lˆa`n nguo. c); . . • nguo. c la.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´t th´ucthuˆa.t to´an,nˆe´u k = n th`ıd¯ˆo` thi. liˆenthˆong;nguo. c la.i th`anhphˆa`n liˆenthˆongch´ua . d¯ı˙’nh s gˆo`m k d¯ı˙’nh m`anum(i) nhˆa.n c´acgi´atri. t`u 1 d¯ˆe´n k. 26
27. . . . . V´ıdu. 1.3.1 X´etd¯ˆo` thi. trong H`ınh1.14. C´acd¯ı˙’nh s˜ed¯uo. c viˆe´ng thˇamtheo th´u tu. 1, 4, 2, 3 v`a5. Qu´atr`ınht`ımkiˆe´m c´othˆe˙’ biˆe˙’u diˆe˜n th`anhcˆayc´ogˆo´c (d¯ı˙’nh gˆo´c l`a v1) trong H`ınh v5 •. v 4 v v 1 ••• 2 .• v3 H`ınh1.14: 1.15. v5 •. 5 v 4 v v 1 ••• 2 . 1 2 3 . . . 4 .• v3 H`ınh1.15: Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆau 1. Thˇamd¯ı˙’nh xuˆa´t ph´at s. 2. V´o.i mˆo˜i d¯ı˙’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 chua d¯uo. c thˇam,´apdu. ng thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆauv´oi w nhu l`a d¯ı˙’nh xuˆa´t ph´at. Trong c´ach t`ımkiˆe´m theo chiˆe` u sˆau,ta d¯itheo d¯u.`o.ng t`u. d¯ı˙’nh xuˆa´t ph´atcho d¯ˆe´n khi . . d¯a.t d¯ˆe´n mˆo.t d¯ı˙’nh c´otˆa´t ca˙’ c´acd¯ı˙’nh kˆe` n´od¯˜ad¯uo. c viˆe´ng thˇam.Sau d¯´ota quay la.i d¯ı˙’nh 27
28. . . . . . . . . . cuˆo´i c`ungv`ua d¯uo. c thˇamdo.c theo d¯u`ong n`aysao cho c´acd¯ı˙’nh kˆe` v´oi n´o(c´ohu´ong t`u . . . . . . . . n´od¯ira trong tru`ong ho. p d¯ˆo` thi. c´ohu´ong) c´othˆe˙’ thˇamd¯uo. c. D- ˆe˙’ c´othˆe˙’ quay tro˙’ la.i, ta . . . . . . luu tr˜u c´acd¯ı˙’nh do.c theo d¯u`ong n`aytrong mˆo.t ngˇanxˆe´p. Nˆe´u thu˙’ tu. c d¯uo. c viˆe´t da.ng d¯ˆe. . . . . . . . . quy th`ıngˇanxˆe´p n`ayd¯uo. c ba˙’o tr`ımˆo.t c´ach tu. d¯ˆo.ng; trong tru`ong ho. p nguo. c la.i, cˆa`n mˆo.t . . ma˙’ng d¯´anhdˆa´u c´acd¯ı˙’nh d¯˜ad¯uo. c viˆe´ng thˇam. Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u rˆo.ng . . Trong thuˆa.t to´ann`ay, ch´ungta thˇamc´acd¯ı˙’nh theo t`ung m´uc mˆo.t, v`akhi thˇammˆo.t d¯ı˙’nh . . . . . . o˙’ m´uc n`aod¯´o,ta pha˙’i luu tr˜u n´od¯ˆe˙’ c´othˆe˙’ tro˙’ la.i khi d¯ihˆe´t mˆo.t m´uc, v`ıvˆa.y c´othˆe˙’ thˇam . . . c´acd¯ı˙’nh kˆe` cu˙’a n´o.Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u rˆo.ng du´oi d¯ˆayd`ungmˆo.t h`angd¯o. i theo c´ach n`ay. 1. Thˇamd¯ı˙’nh xuˆa´t ph´at. . . . 2. Kho˙’ i d¯ˆo.ng mˆo.t h`angd¯o. i chı˙’ ch´ua d¯ı˙’nh xuˆa´t ph´at. . . . 3. Trong khi h`angd¯o. i khˆongrˆo˜ng l`amc´acbu´oc sau: . . Lˆa´y mˆo.t d¯ı˙’nh v t`u h`angd¯o. i. V´o.i tˆa´t ca˙’ c´acd¯ı˙’nh w kˆe` v´o.i v, l`amc´acbu.´o.c sau: . . . Nˆe´u (w chua d¯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ˆe` u rˆo.ng v`at`ımkiˆe´m theo chiˆe` u sˆaul`arˆa´t co ba˙’n cho . nhiˆe` u thuˆa.t to´ankh´acd¯ˆe˙’ xu˙’ l´yd¯ˆo` thi V´ıdu. , d¯ˆe˙’ duyˆe.t mˆo.t d¯ˆo` thi., ta c´othˆe˙’ ´apdu. ng nhiˆe` u . lˆa`n mˆo.t trong c´acc´ach n´oitrˆen,cho.n c´acd¯ı˙’nh xuˆa´t ph´atm´oi nˆe´u cˆa`n thiˆe´t, cho d¯ˆe´n khi . . tˆa´t ca˙’ c´acd¯ı˙’nh d¯uo. c thˇam. 1.3.4 Cˆa` u, k−liˆenthˆong . D- iˆe˙’m kh´op cu˙’a d¯ˆo` thi. l`amˆo.t d¯ı˙’nh m`axo´an´os˜etˇangsˆo´ th`anhphˆa`n liˆenthˆong; cˆa`u l`aca.nh . . . . . . m`axo´an´oc˜ungc´oa˙’nh huo˙’ ng tuong tu. .D- `ˆo thi. trong H`ınh1.14 c´omˆo.t d¯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.2 Trong mˆo.t d¯ˆo` thi. khˆongc´ochu tr`ınh,c´acd¯ı˙’nh khˆongpha˙’i l`ad¯ı˙’nh treo, t´uc . . . d¯ı˙’nh c´obˆa.c ≥ 2, l`ad¯iˆe˙’m kh´op. Nguo. c la.i, d¯ˆo` thi. c´ochu tr`ınhHamilton (xem Phˆa`n 5.3) khˆongc´od¯iˆe˙’m kh´o.p. 28
29. . . . . . . V´ıdu. 1.3.3 [Ma. ng thˆongtin] Gia˙’ su˙’ V l`atˆa.p ho. p nh˜ung ngu`oi thuˆo.c mˆo.t tˆo˙’ ch´uc n`ao . . . . . . d¯´o;ta d¯ˇa.t (a, b) ∈ E nˆe´u ngu`oi a v`a b c´othˆe˙’ b´aotin v´oi nhau. Nh˜ung ngu`oi liˆenla.c l`a . . . . . . . nh˜ung d¯iˆe˙’m kh´op. Nh˜ung ngu`oi d¯´ol`anh˜ung mˇa´t x´ıch quan tro.ng, v`ımˆa´t ho. s˜eph´av˜o . . t´ınhthˆo´ng nhˆa´t v`asu. liˆenkˆe´t cu˙’a tˆo˙’ ch´uc. . . D- .inh l´y 1.3.4 Gia˙’ su˙’ G = (V, E) l`ad¯ˆo` thi. liˆenthˆong.Khi d¯´od¯ı˙’nh v ∈ V l`ad¯iˆe˙’m kh´op . nˆe´u v`achı˙’ nˆe´u tˆo`n ta. i hai d¯ı˙’nh a v`a b sao cho mo. i dˆaychuyˆe` n nˆo´i a v´oi b d¯ˆe` u d¯iqua v. . . . Ch´ung minh. D- iˆe` u kiˆe.n cˆa`n. Nˆe´u d¯ˆo` thi. con sinh bo˙’ i tˆa.p ho. p V \{v} khˆongliˆenthˆongth`ı . . n´och´ua ´ıtnhˆa´t hai th`anhphˆa`n C v`a C; gia˙’ su˙’ a l`amˆo.t d¯ı˙’nh n`aod¯´ocu˙’a C v`a b l`amˆo.t . d¯ı˙’nh n`aod¯´ocu˙’a C. Trong d¯ˆo` thi. liˆenthˆongban d¯ˆa`u G mo.i dˆaychuyˆe` n bˆa´t k`ynˆo´i a v´oi b d¯ˆe` u pha˙’i d¯iqua v. . D- iˆe` u kiˆe.n d¯u˙’. Nˆe´u mˆo.t dˆaychuyˆe` n bˆa´t k`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˙’ i vˆa.y d¯ı˙’nh v l`ad¯iˆe˙’m kh´op. / Ta c´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ˆongt´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ˆenthˆongcu. c d¯a.i cu˙’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ˆenthˆong cu˙’a G. . . D- ˆe˙’ t`ımc´acd¯iˆe˙’m kh´op v`ac´acth`anhphˆa`n 2−liˆenthˆongta c´othˆe˙’ su˙’ du. ng thuˆa.t to´an t`ımkiˆe´m theo chiˆe` u sˆau. . . . . V´oi mˆo˜i d¯ı˙’nh vi, x´ettˆa.p D(i) c´acd¯ı˙’nh d¯´ung liˆe` n tru´oc d¯ı˙’nh vi trong cˆay T x´acd¯i.nh . . bo˙’ i thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆau.Khi d¯´o,v´oi mo.i d¯ı˙’nh vj ∈ D(i) ta c´o l(j) = min (num(k)) k∈Γ(vj ) . . . . l`asˆo´ nho˙’ nhˆa´t d¯uo. c g´ancho d¯ı˙’nh kˆe` v´oi d¯ı˙’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. c tiˆe˙’u cu˙’a num(i) v`asˆo´ nho˙’ nhˆa´t d¯uo. c g´ancho c´ac . . . d¯ı˙’nh m`ac´othˆe˙’ d¯ˆe´n d¯uo. c bˇa`ng d¯´ungmˆo.t ca.nh t`u mˆo.t trong c´ac hˆa. u duˆe. cu˙’a vi trong cˆay T. . . Do d¯´o,trong V´ıdu. 1.3.1 (H`ınh1.15), d¯ı˙’nh v2 c´od¯´ungmˆo.t d¯ı˙’nh tru´oc liˆe` n kˆe` l`ad¯ı˙’nh v4, v`ado d¯´oinf(2) = num(4) = 2. . . . Ch´u´yrˇa`ng inf(i) ≤ num(i) v`ıkho˙’ i d¯ˆa`u t`u tiˆe` n bˆo´i cu˙’a vi n´oc´othˆe˙’ tro˙’ vˆe` vi. 29
30. . . . Hon n˜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´op cu˙’a d¯ˆo` . thi Ngo`aira, c´acd¯ı˙’nh bˇa´t gˇa.p khi duyˆe.t tro˙’ la.i d¯ı˙’nh vi ta.o th`anhmˆo.t th`anhphˆa`n 2−liˆen thˆong. . . . . . Thuˆa.t to´andu´oi d¯ˆaytr`ınhb`ayphuong ph´apx´acd¯i.nh c´acd¯iˆe˙’m kh´op cu˙’a d¯ˆo` thi. liˆen thˆongxuˆa´t ph´att`u. d¯ı˙’nh s. . . Thuˆa.t to´anTarjan t`ımd¯iˆe˙’m kh´op cu˙’a d¯ˆo` thi. liˆenthˆongxuˆa´t ph´att`u d¯ı˙’nh s . - + . 1. [Kho˙’ i ta.o] Dˇa.t P (i) = 0, di := #Γ(vi), n(i) = 0 v`ainf(i) = ∞ v´oi mo.i d¯ı˙’nh vi, i = 1, 2, . . . , n; k = 0, num(s) = 1,P (s) = s, i = s. . . . 2. [Bu´oc lˇa.p] Trong khi (n(i) 6= d(i)) hoˇa.c (i 6= s) thu. c hiˆ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ˆen thˆong). . . . • Nguo. c la.i, t´uc l`a n(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. c la.i nˆe´u P (j) 6= 0 g´aninf(i) = min(inf(i), num(j)). . . . . Dˆe˜ d`angkiˆe˙’m tra v´oi v´ıdu. tru´oc, d¯ı˙’nh v4 l`ad¯iˆe˙’m kh´op. Ch´u´yrˇa`ng c´othˆe˙’ x´acd¯i.nh . . . th`anhphˆa`n 2−liˆenthˆongbˇa`ng c´ach su˙’ a d¯ˆo˙’i Bu´oc 2 trong Thuˆa.t to´anTarjan. Mˆe.nh d¯ˆe` sau l`ahiˆe˙’n nhiˆen: . Mˆe.nh d¯ˆe` 1.3.5 C´acthuˆa. t to´anTr´emaux-Tarjan v`aTarjan c´oth`oi gian O(m). Thiˆe´t diˆe.n A ⊂ V cu˙’a d¯ˆo` thi. liˆenthˆong G l`atˆa.p con A c´acd¯ı˙’nh sao cho d¯ˆo` thi. con . . . GV \A nhˆa.n d¯uo. c t`u G bˇa`ng c´ach xo´ac´acd¯ı˙’nh trong A (v`ac´acca.nh liˆenthuˆo.c n´o)khˆong liˆenthˆong. D- `ˆo thi. go.i l`a k−liˆenthˆong nˆe´u v`achı˙’ nˆe´u n´oliˆenthˆong,c´osˆo´ d¯ı˙’nh n ≥ k +1, v`akhˆong . . . . ch´ua mˆo.t thiˆe´t diˆe.n c´olu. c luo. ng (k − 1). 30
31. . C´acd¯ˆo` thi. con k−liˆenthˆongcu. c d¯a.i cu˙’a G ta.o th`anhmˆo.t phˆanhoa.ch cu˙’a G v`ago.i l`ac´ac th`anhphˆa`n k−liˆenthˆong. . . . C´acth`anhphˆa`n 3−liˆenthˆongcu˙’a d¯ˆo` thi. c´othˆe˙’ nhˆa.n d¯uo. c trong th`oi gian O(m) bˇa`ng . . . thuˆa.t to´antuong tu. cu˙’a Tarjan. D- a d¯ˆo` thi. liˆenthˆong G go.i l`a k−ca. nh liˆenthˆong nˆe´u n´ovˆa˜n c`onliˆenthˆongkhi xo´ad¯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´ua cˆa`u. . . Bˇa`ng c´ach su˙’ a d¯ˆo˙’i la.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´ett´ınh2−ca.nh liˆenthˆongc´onhiˆe` u ´ung du. ng trong thu. c tˆe´: ma.ng d¯iˆe.n, d¯iˆe.n thoa.i, v.v., pha˙’i 2−ca.nh liˆenthˆong! 1.3.5 D- `ˆo thi. liˆenthˆongma.nh . . . . D- `ˆo thi. c´ohu´ong go.i l`a liˆenthˆongma. nh nˆe´u tˆa´t ca˙’ c´accˇa.p d¯ı˙’nh vi v`a vj tˆo`n ta.i d¯u`ong d¯i . t`u vi d¯ˆe´n vj. . . . X´etquan hˆe. viRvj nˆe´u v`achı˙’ nˆe´u hoˇa.c vi = vj hoˇa.c tˆo`n ta.i d¯u`ong d¯it`u d¯ı˙’nh vi d¯ˆe´n . . . . . . . d¯ı˙’nh vj v`ad¯u`ong d¯it`u d¯ı˙’nh vj d¯ˆe´n d¯ı˙’nh vi. Dˆe˜ thˆa´y d¯ˆayl`a quan hˆe. tuong d¯uong (pha˙’n . xa., d¯ˆo´i x´ung v`abˇa´c cˆa`u). . . . . . . . . . . L´op tuong 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.i l`a sˆo´ th`anhphˆa`n liˆenthˆongma. nh cu˙’a d¯ˆ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´u v`achı˙’ nˆe´u sˆo´ th`anh phˆ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´ua d¯ı˙’nh vl d¯uo. c cho bo˙’ i C = Γˆ ∩ Γˆ−1, l vl vl . . . . . v`at`u d¯´osuy ra mˆo.t thuˆa.t to´anrˆa´t d¯on gia˙’n th`oi gian d¯ath´uc O(m) du. a trˆenthuˆa.t to´an . t`ımkiˆe´m theo chiˆe` u sˆaum`ac´othˆe˙’ su˙’ du. ng n´od¯ˆe˙’ t`ım Cl. Do d¯´ot´ınhliˆenthˆongma.nh dˆe˜ d`angkiˆe˙’m tra. Chı˙’ cˆa`n x´etkhi n`ao Cl ≡ V. (H˜aygia˙’i b`aito´ann`aybˇa`ng ma trˆa.n). . Nˆe´u mˇa.t kh´ac,ch´ungta muˆo´n t`ımtˆa´t ca˙’ c´acth`anhphˆa`n liˆenthˆongma.nh, ta s˜esu˙’ du. ng Thuˆa.t to´anTarjan. 31
32. . . . . Thˆa.t vˆa.y ta s˜ech´ung minh rˇa`ng, thuˆa. t to´anTarjan ´apdu. ng v´oi c´acd¯ˆo` thi. c´ohu´ong, cho ph´ept`ımc´acth`anhphˆa`n liˆenthˆongma.nh. . . . Ch´ungta kho˙’ i d¯ˆa`u v´oi thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆau,nhu trong c´acthuˆa.t to´an . . t`ımkiˆe´m theo chiˆe` u sˆauv`aTarjan. V´oi mˆo˜i d¯ı˙’nh vi x´etmˆo.t chı˙’ sˆo´ m´oi l`asˆo´ nho˙’ nhˆa´t cu˙’a . chı˙’ 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. u duˆe. cu˙’a vi trong cˆaygia pha˙’. . . . Chı˙’ sˆo´ m´oi n`ayd¯uo. c k´yhiˆe.u l`ainf(i). Nhˆa.n x´etrˇa`ng ch´ungta 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.t d¯ı˙’nh m`axa˙’y ra d¯ˇa˙’ng th´uc inf(i) = num(i) s˜ephˆan . . . hoa.ch d¯ˆo` thi. th`anh´ıtnhˆa´t hai th`anhphˆa`n liˆenthˆongma.nh, v`amˆo.t trong ch´ungtuong ´ung . . . . . tˆa.p c´acd¯ı˙’nh m`ad¯˜ad¯uo. c viˆe´ng thˇamtru´oc khi t´oi d¯ı˙’nh vi. D- `ˆo thi. trong H`ınh1.16 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`ınh1.16: . . Ch´ungta su˙’ du. ng thuˆa.t ng˜u d¯ˆo` thi. thu go. n d¯ˆe˙’ biˆe˙’u diˆe˜n d¯ˆo` thi. G qua quan hˆe. liˆen thˆ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`n ta.i cung gi˜ua hai d¯ı˙’nh Ci v`a Cj nˆe´u v`achı˙’ nˆe´u tˆo`n ta.i ´ıtnhˆa´t mˆo.t cung gi˜ua mˆo.t d¯ı˙’nh cu˙’a Ci v`a Cj trong G. Hiˆe˙’n nhiˆend¯ˆo` thi. Gr khˆongc´oma.ch. H`ınh1.17 l`ad¯ˆo` thi. thu . . . go.n cu˙’a d¯ˆo` thi. c´ohu´ong trong H`ınh1.16. Nghiˆenc´uu c´acth`anhphˆa`n liˆenthˆongma.nh v`a . . . t`ımd¯ˆo` thi. thu go.n l`anh˜ung b`aito´anthu. c tiˆ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´u tr´uccu˙’a mˆo.t hˆe. thˆo´ng (xem [30]). Phˆa`n tiˆe´p theo ch´ung ta s˜ed¯ˆe˙’ cˆa.p thˆemvˆe` vˆa´n d¯ˆe` n`ay. 32
33. C6 • •• C1 C8 H`ınh1.17: 1.4 Pha.m vi v`aliˆenthˆongma.nh . . Ta biˆe´t rˇa`ng hˆe. thˆo´ng truyˆe` n thˆongcu˙’a mˆo.t tˆo˙’ ch´uc c´othˆe˙’ xem nhu mˆo.t d¯ˆo` thi. trong d¯´o . . . . . . . . mˆo˜i ngu`oi tuong ´ung mˆo.t d¯ı˙’nh v`ac´ackˆenhtruyˆe` n thˆongtuong ´ung c´accung. Cˆauho˙’i . . . . d¯ˇa.t ra l`atrong hˆe. thˆo´ng n`ay, thˆongtin t`u vi c´othˆe˙’ d¯ˆe´n d¯uo. c vj khˆong?T´uc l`ac´otˆo`n ta.i . . . . . d¯u`ong d¯it`u vi d¯ˆe´n vj? Nˆe´u d¯u`ong d¯id¯´otˆo`n ta.i ta n´oi vj thuˆo.c pha. m vi cu˙’a vi. Ch´ungta . . . . c˜ungquan tˆamd¯ˆe´n c´od¯u`ong d¯it`u vi d¯ˆe´n vj v´oi sˆo´ cung ha.n chˆe´ khˆong? Mu. c d¯´ıch cu˙’a . phˆa`n n`ayl`atha˙’o luˆa.n mˆo.t v`aikh´ainiˆe.m co ba˙’n liˆenquan d¯ˆe´n c´act´ınhchˆa´t pha.m vi v`a . . . liˆenthˆongma.nh cu˙’a c´acd¯ˆo` thi. v`agi´oi thiˆe.u mˆo.t sˆo´ thuˆa.t to´anco so˙’ . . . Theo thuˆa.t ng˜u cu˙’a d¯ˆo` thi. biˆe˜u diˆe˜n cho mˆo.t tˆo˙’ ch´uc, phˆa`n n`aykha˙’o s´atmˆo.t sˆo´ cˆau ho˙’i: . . . . . . . 1. Sˆo´ ngu`oi ´ıtnhˆa´t m`amˆo˜i ngu`oi trong tˆo˙’ ch´uc c´othˆe˙’ liˆenla.c d¯uo. c bˇa`ng bao nhiˆeu? . . . . . 2. Sˆo´ ngu`oi nhiˆe` u nhˆa´t c´othˆe˙’ liˆenla.c d¯uo. c v´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.m vi . Ma trˆa. n pha. m vi R = (rij) d¯i.nh ngh˜ıanhu sau: ( . . . 1 nˆe´u tˆo`n ta.i d¯u`ong d¯it`u d¯ı˙’nh vi d¯ˆe´n d¯ı˙’nh vj, rij := . . 0 nˆe´u nguo. c la.i. . . . Tˆa.p R(vi) c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. G c´othˆe˙’ d¯ˆe´n d¯uo. c t`u d¯ı˙’nh vi gˆo`m c´acd¯ı˙’nh vj sao cho . . . . phˆa`n tu˙’ rij bˇa`ng 1. Theo d¯i.nh ngh˜ıa,tˆa´t ca˙’ c´acphˆa`n tu˙’ trˆend¯u`ong ch´eocu˙’a ma trˆa.n pha.m vi bˇa`ng 1. 33
34. . . . . . Do Γ(vi) l`atˆa.p c´acd¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c t`u vi theo mˆo.t d¯u`ong d¯ic´od¯ˆo. d`ai1 nˆen 2 . . . . . . tˆa.p Γ(Γ(vi)) = Γ (vi) gˆo`m nh˜ung d¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c t`u vi theo mˆo.t d¯u`ong d¯ic´od¯ˆo. d`ai . . . p . . . . . . 2. Tuong tu. ,Γ (vi) l`atˆa.p nh˜ung d¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c t`u vi theo mˆo.t d¯u`ong d¯ic´od¯ˆo. d`ai . . . p. Do vˆa.y, tˆa.p c´acd¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c t`u vi l`a 1 2 R(vi) = {vi} ∪ Γ (vi) ∪ Γ (vi) ∪ · · · . . . . . . . . . . . Nhung do d¯ˆo` thi. d¯uo. c x´etl`ah˜uu ha.n v`amo.i d¯u`ong d¯id¯ˆe` u ch´ua mˆo.t d¯u`ong d¯icon so cˆa´p trong d¯´o,nˆentˆo`n ta.i p sao cho 1 2 p R(vi) = {vi} ∪ Γ (vi) ∪ Γ (vi) ∪ · · · ∪ Γ (vi). (1.1) . . . . . . Suy ra tˆa.p pha.m vi R(vi) c´othˆe˙’ nhˆa.n d¯uo. c t`u Phuong tr`ınh(1.1) bˇa`ng c´ach thu. c hiˆe.n c´ac . . . . ph´epto´anho. p t`u tr´aisang pha˙’i cho d¯ˆe´n khi tˆa.p hiˆe.n h`anhkhˆongtˇangk´ıch thu´oc trong lˆa`n . lˇa.p kˆe´ tiˆe´p. Sˆo´ c´acph´epto´anho. p phu. thuˆo.c v`aod¯ˆo` thi., mˇa.c d`uhiˆe˙’n nhiˆenrˇa`ng p ≤ n − 1, trong d¯´o n l`asˆo´ d¯ı˙’nh cu˙’a d¯ˆo` thi . . . . . Vˆa.y ma trˆa.n pha.m vi c´othˆe˙’ d¯uo. c xˆaydu. ng nhu sau. T`ımtˆa.p R(vi) v´oi mˆo˜i d¯ı˙’nh vi . . theo trˆen.D- ˇa.t rij = 1 nˆe´u vj ∈ R(vi), v`a rij = 0 nˆe´u nguo. c la.i. . . . Ma trˆa. n d¯a. t d¯uo. c Q = (qij) d¯i.nh ngh˜ıanhu sau: ( . . . 1 nˆe´u tˆo`n ta.i d¯u`ong d¯it`u d¯ı˙’nh vj d¯ˆe´n d¯ı˙’nh vi, qij := . . 0 nˆe´u nguo. c la.i. . . . . . . Tˆa.p Q(vi) cu˙’a d¯ˆo` thi. G l`atˆa.p c´acd¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c d¯ı˙’nh vi. Tuong tu. nhu trˆen ta c˜ungc´o −1 −2 −p Q(vi) = {vi} ∪ Γ (vi) ∪ Γ (vi) ∪ · · · ∪ Γ (vi), (1.2) −2 −1 −1 trong d¯´oΓ (vi) = Γ (Γ (vi)), . t T`u d¯i.nh ngh˜ıa,hiˆe˙’n nhiˆenc´o Q = R . V´ıdu. 1.4.1 X´etd¯ˆo` thi. G trong H`ınh1.18. Ma trˆa.n kˆe` cu˙’a G l`a v v v v v v v  1 2 3 4 5 6 7  v1 0 1 0 0 1 0 0     v2  0 1 0 1 0 0 0    v3  0 0 0 1 0 0 0    A = v  0 0 0 0 1 0 0 . 4     v5  0 0 0 0 1 0 0    v6  0 0 1 0 0 0 1  v7 0 0 0 1 0 1 0 34
35. v1 • . . . . . . v 2 .•. v6 •. . . . . . . . . . . . . . . . . . . . v • • 3 v 7 • • v 5 . . v . . 4 . . H`ınh1.18: . . . . 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}. 35
36. Do d¯´oma trˆa.n pha.m vi c´oda.ng v v v v v v v  1 2 3 4 5 6 7  v1 1 1 0 1 1 0 0     v2  0 1 0 1 1 0 0    v3  0 0 1 1 1 0 0    R = v  0 0 0 1 1 0 0 . 4     v5  0 0 0 0 1 0 0    v6  0 0 1 1 1 1 1  v7 0 0 1 1 1 1 1 . Cˆa`n ch´u´yrˇa`ng, do R v`a Q l`ac´acma trˆa.n Boole, mˆo˜i h`angcu˙’a ch´ungc´othˆe˙’ luu da.ng . . . mˆo.t hoˇa.c hon mˆo.t t`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´t mˆo.t d¯u`ong d¯it`u vi d¯ˆe´n vj qua d¯ı˙’nh vk. C´acd¯ı˙’nh n`aygo.i l`a cˆo´t yˆe´u. Tˆa´t ca˙’ c´acd¯ı˙’nh vk ∈/ R(vi) ∩ Q(vj) go.i l`a khˆong . . . . . . . cˆo´t yˆe´u hay du th`ua do bo˙’ ch´ungd¯ikhˆonga˙’nh huo˙’ ng d¯ˆe´n c´acd¯u`ong d¯it`u vi d¯ˆe´n vj. . . C´acma trˆa.n R v`a Q d¯i.nh ngh˜ıatrˆenl`atuyˆe.t d¯ˆo´i theo ngh˜ıasˆo´ c´accung trˆend¯u`ong . . . . d¯it`u vi d¯ˆe´n vj khˆongbi. ha.n chˆe´. Mˇa.t kh´acta c˜ungc´othˆe˙’ d¯i.nh ngh˜ıatuong tu. c´acma . . . . . . . . . trˆa.n n`ayv´oi sˆo´ cung trˆend¯u`ong d¯ikhˆongvuo. t qu´amˆo.t sˆo´ cho tru´oc. V´oi mo˙’ rˆo.ng n`ayta . . . . c˜ungc´othˆe˙’ t´ınhd¯uo. c c´acma trˆa.n ha.n chˆe´ theo luo. c d¯ˆo` trˆen. . . D- `ˆo thi. d¯uo. c go.i l`a bˇa´c cˆa`u nˆe´u tˆo`n ta.i c´accung (vi, vj) v`a(vj, vk) th`ıc˜ungtˆo`n ta.i cung 0 0 (vi, vk). Bao d¯´ongbˇa´c cˆa`u cu˙’a d¯ˆo` thi. G = (V, E) l`ad¯ˆo` thi. Gtc = (V, E ∪ E ) trong d¯´o E l`a . . . c´accung d¯uo. c thˆemv`ao´ıtnhˆa´t d¯ˆe˙’ d¯ˆo` thi. Gtc c´ot´ınhbˇa´c cˆa`u. Dˆe˜ d`angch´ung minh rˇa`ng ma trˆa.n kˆe` cu˙’a d¯ˆo` thi. Gtc ch´ınhl`ama trˆa.n pha.m vi R v`abˇa`ng A + A2 + ··· + Ap, (p ≤ n − 1), trong d¯´o A l`ama trˆa.n kˆe` cu˙’a G. (Ta.i sao?) 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˜ıatrong phˆa`n tru´oc tru´oc l`ad¯ˆo` thi. con liˆenthˆong . . . ma.nh l´on nhˆa´t trong G. V`ıv´oi d¯ˆo` thi. liˆenthˆongma.nh, v´oi mo.i cˇa.p d¯ı˙’nh vi, vj, luˆonluˆon . . . . . tˆo`n ta.i mˆo.t d¯u`ong d¯it`u d¯ı˙’nh vi d¯ˆe´n d¯ı˙’nh vj v`anguo. c la.i, nˆentˆo`n ta.i duy nhˆa´t mˆo.t th`anh . . . phˆa`n liˆenthˆongma.nh ch´ua mˆo.t d¯ı˙’nh cho tru´oc v`a vi s˜exuˆa´t hiˆe.n trong tˆa.p c´acd¯ı˙’nh cu˙’a mˆ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?). 36
37. . . . . . . Nˆe´u d¯ı˙’nh vi d¯uo. c coi v`ua l`axuˆa´t ph´atv`ua l`akˆe´t th´ucth`ıtˆa.p c´acd¯ı˙’nh cˆo´t yˆe´u tuong . . . . ´ung v´oi hai d¯ı˙’nh tr`ungnhau n`ay(t´uc l`atˆa.p c´acd¯ı˙’nh thuˆo.c ma.ch n`aod¯´och´ua vi) x´acd¯i.nh . . . . bo˙’ i R(vi) ∩ Q(vi). V`ıtˆa´t ca˙’ c´acd¯ı˙’nh cˆo´t yˆe´u n`ayc´othˆe˙’ d¯ˆe´n t`u vi v`anguo. c la.i nˆench´ung . . . . . . c˜ungc´othˆe˙’ d¯ˆe´n d¯uo. c c´acd¯ı˙’nh kh´actrong tˆa.p n`ayv`anguo. c la.i. Hon n˜ua, dˆe˜ thˆa´y rˇ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´t tuong ´ung . v´oi d¯ı˙’nh vi. Nˆe´u ta loa.i c´acd¯ı˙’nh n`aykho˙’i d¯ˆo` thi. G = (V, Γ) th`ıc´othˆe˙’ ´apdu. ng t`ımth`anhphˆa`n . . 0 . liˆenthˆongma.nh trˆend¯ˆo` thi. con nhˆa.n d¯uo. c G v´oi tˆa.p d¯ı˙’nh V \ (R(vi) ∩ Q(vi)). Qu´atr`ınh . . n`aylˇa.p la.i cho d¯ˆe´n khi tˆa´t ca˙’ c´acth`anhphˆa`n liˆenthˆongma.nh d¯uo. c t`ım.Kˆe´t th´ucta c´od¯ˆo` . . thi. G d¯uo. c phˆanhoa. ch th`anhc´acth`anhphˆa`n liˆenthˆongma.nh. V´ıdu. 1.4.2 X´etd¯ˆo` thi. trong H`ınh1.19. Ch´ungta h˜ayt`ımth`anhphˆa`n liˆenthˆongma.nh . ch´ua d¯ı˙’nh v1. v1 v6 v10 v11 •. •. •. •. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • v13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • •. • . . . . . . v2 v5 . v8 . v12 . . . . . . . . . . . . . . . . . . . . . . . . . v •• . • 9 . . v v . 3 7 . . . . . . . . . . . . .• v4 H`ınh1.19: D- `ˆo thi. G. 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´ua d¯ı˙’nh v1 l`ad¯ˆo` thi. con hR(v1) ∩ Q(v1)i = h{v1, v2, v5, v6}i. 37
38. . . . . . Tuong tu. , th`anhphˆa`n liˆenthˆongma.nh ch´ua d¯ı˙’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´ua d¯ı˙’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¯uo. c cho trong H`ınh1.20. ∗ ∗ v1 = {v1, v2, v5, v6} v2 = {v8, v10} • •. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∗ . . • v4 = {v11, v12, v13} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • ∗ ∗ v5 = {v3} v3 = {v4, v7, v9} H`ınh1.20: D- `ˆo thi. thu go.n Gr. . . C´acph´epto´and¯uo. c miˆeuta˙’ trˆend¯ˆe˙’ t`ımc´acth`anhphˆa`n liˆenthˆongma.nh cu˙’a mˆo.t d¯ˆo` . . . . . thi. c˜ungc´othˆe˙’ su˙’ du. ng tru. c tiˆe´p d¯ˆo´i v´oi c´acma trˆa.n R v`a Q d¯i.nh ngh˜ıaphˆa`n tru´oc. Do . . . d¯´onˆe´u ta k´yhiˆe.u R ⊗ Q c´ongh˜ıal`ama trˆa.n nhˆa.n d¯uo. c t`u R v`a Q bˇa`ng c´ach nhˆanc´ac . . . . . . . . phˆa`n tu˙’ tuong ´ung th`ıphˆa`n tu˙’ (R ⊗ Q)ij = rijqij bˇa`ng 1 nˆe´u tˆo`n ta.i d¯u`ong d¯it`u vi d¯ˆe´n vj . . . . . . . v`anguo. c la.i, v`abˇa`ng 0 trong tru`ong ho. p nguo. c la.i. Do d¯´ohai d¯ı˙’nh thuˆo.c c`ungmˆo.t th`anh . . . phˆa`n liˆenthˆongma.nh nˆe´u v`achı˙’ nˆe´u c´ach`ang(hoˇa.c cˆo.t) tuong ´ung bˇa`ng nhau. C´acd¯ı˙’nh . . . . . . m`ah`angtuong ´ung ch´ua mˆo.t phˆa`n tu˙’ 1 o˙’ cˆo.t vj ta.o th`anhtˆa.p d¯ı˙’nh cu˙’a th`anhphˆa`n liˆen . thˆongma.nh ch´ua vi. Hiˆe˙’n nhiˆenrˇa`ng c´othˆe˙’ biˆe´n d¯ˆ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.n thu d¯uo. c c´oda.ng khˆo´i ch´eo;mˆo˜i ma trˆa.n con ch´eo . . . . . tuong ´ung v´oi mˆo.t th`anhphˆa`n liˆenthˆongma.nh cu˙’a G v`ac´oc´acphˆa`n tu˙’ bˇa`ng 1, c´acphˆa`n 38
39. . . . . tu˙’ kh´acbˇa`ng 0. V´oi v´ıdu. trˆen,ma trˆa.n R ⊗ Q d¯uo. c sˇa´p x´e6pla.i c´oda.ng v1 v2 v5 v6 v8 v10 v4 v7 v9 v11 v12 v13 v3   v1 1 1 1 1   v  1 1 1 1  2     v5  1 1 1 1    v6  1 1 1 1      v8  1 1    v10  1 1    R ⊗ Q = v  1 1 1 . 4     v7  1 1 1    v  1 1 1  9     v11  1 1 1    v12  1 1 1    v13  1 1 1  v3 1 1.4.3 Co. so˙’. . . Tˆa.p B c´acd¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c mo.i d¯ı˙’nh cu˙’a d¯ˆo` thi. v`anho˙’ nhˆa´t theo ngh˜ıakhˆongc´otˆa.p . . . . con thu. c su. n`aocu˙’a n´oc´ot´ınhchˆa´t n`aygo.i l`a co so˙’ . Do d¯´onˆe´u ta viˆe´t R(B) l`atˆa.p pha.m vi cu˙’a B-t´u.c l`a R(B) = ∪vi∈BR(vi) th`ı B l`aco. so˙’. nˆe´u v`achı˙’ nˆe´u 1. B(V ) = V ; v`a . 2. v´oi mo.i tˆa.p con S ⊂ B th`ı R(S) 6= V. . . . . . . . D- iˆe` u kiˆe.n th´u hai tuong d¯uong v´oi d¯iˆe` u kiˆe.n vj ∈/ R(vi) v´oi hai d¯ı˙’nh phˆanbiˆe.t vi, vj ∈ B; . . . . t´uc l`amˆo.t d¯ı˙’nh thuˆo.c B khˆongthˆe˙’ d¯ˆe´n d¯uo. c t`u mˆo.t d¯ı˙’nh kh´actrong B. D- iˆe` u n`ayc´othˆ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ˆend¯iˆe` u kiˆe.n R(S) 6= V v´oi mo.i . . . . . . S ⊂ B tuong d¯uong v´oi R(B\{vj}) 6= V v´oi mo.i vj ∈ B. N´oic´ach kh´ac, R(vj) 6⊂ R(B\{vj}). . . . Nhung d¯iˆe` u kiˆe.n n`aythoa˙’ m˜annˆe´u v`achı˙’ nˆe´u vj ∈/ R(B \{vj}), t´uc l`a vj ∈/ R(vi) v´oi mo.i vi, vj ∈ B. . . Vˆa.y, co so˙’ l`amˆo.t tˆa.p B c´acd¯ı˙’nh thoa˙’ m˜anhai d¯iˆe` u kiˆe.n sau: 39
40. . . . 1. tˆa´t ca˙’ c´acd¯ı˙’nh cu˙’a G c´othˆe˙’ d¯ˆe´n d¯uo. c t`u d¯ı˙’nh n`aod¯´ocu˙’a B; v`a . . . 2. khˆongd¯ı˙’nh n`aotrong B c´othˆe˙’ d¯ˆe´n d¯uo. c t`u mˆo.t d¯ı˙’nh thuˆo.c B. . T`u hai d¯iˆe` u kiˆe.n n`ayta suy ra . . Mˆe.nh d¯ˆe` 1.4.3 (i) Khˆongtˆo`n ta. i hai d¯ı˙’nh trong co so˙’ B sao cho ch´ungthuˆo. c c`ungmˆo. t th`anhphˆa`n liˆenthˆongma. nh cu˙’a G. . . (b) D- `ˆo thi. khˆongma. ch c´oduy nhˆa´t mˆo. t co so˙’ gˆo`m tˆa. p c´acd¯ı˙’nh c´obˆa. c trong bˇa`ng khˆong. . . . Ch´ung minh. Suy tru. c tiˆe´p t`u d¯i.nh ngh˜ıa. / . Theo Mˆe.nh d¯ˆe` trˆenv`ado d¯ˆo` thi. thu go.n Gr cu˙’a d¯ˆo` thi. G khˆongc´oma.nh nˆentˆ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.p co so˙’ cu˙’a G c´othˆe˙’ 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.p d¯ı˙’nh Sj trong co ˙’. ˙’ . so Br cua Gr, th`ı B l`atˆa.p da.ng {vi1 , vi2 , . . . , vik } v´oi vij ∈ Sj, j = 1, 2, . . . , k. . . . V´ıdu. 1.4.4 V´oi d¯ˆo` thi. trong H`ınh1.19, d¯ˆo` thi. thu go.n trong H`ınh1.20. Co so˙’ cu˙’a d¯ˆo` ∗ ∗ ∗ ∗ thi. n`ayl`a {v4, v5} do v4 v`a v5 l`ahai d¯ı˙’nh duy nhˆa´t cu˙’a G c´obˆa.c trong bˇa`ng khˆong.Suy ra . . c´actˆa.p co so˙’ cu˙’a G l`a {v3, v11}, {v3, v12} v`a {v3, v13.} . . . . . D- ˆo´i ngˆa˜u v´oi kh´ainiˆe.m co so˙’ c´othˆe˙’ d¯i.nh ngh˜ıatheo thuˆa.t ng˜u cu˙’a c´actˆa.p ho. p Q(vi) nhu. sau. . . D- ˆo´i co so˙’ l`atˆa.p B¯ c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. G = (V, Γ) thoa˙’ m˜an [ ¯ Q(B) = Q(vi) = V, vi∈B ∀S ⊂ B,¯ Q(S) 6= V. . . . . T´uc l`a B¯ l`atˆa.p nho˙’ nhˆa´t c´acd¯ı˙’nh c´othˆe˙’ d¯ˆe´n d¯uo. c t`u c´acd¯ı˙’nh kh´ac.C´act´ınhchˆa´t cu˙’a B¯ . . . . . . . . . . tuong tu. v´oi cu˙’a B trong d¯´oc´ackh´ainiˆe.m vˆe` hu´ong d¯uo. c thay bˇa`ng ba˙’n sao nguo. c la.i. . . Do vˆa.y, d¯ˆo´i co so˙’ cu˙’a d¯ˆ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.n d¯uo. c d¯ˆo´i co so˙’ cu˙’a G tuong tu. nhu d¯˜athu. c hiˆe.n o˙’ trˆen. . ∗ Trong v´ıdu. cu˙’a d¯ˆo` thi. G trong H`ınh1.19, d¯ˆo` thi. thu go.n Gr chı˙’ ch´ua mˆo.t d¯ı˙’nh v3 . . ∗ . . . c´obˆa.c ngo`aibˇa`ng khˆong. Do d¯´od¯ˆo´i co so˙’ cu˙’a Gr l`a {v3} v`abo˙’ i vˆa.y d¯ˆo´i co so˙’ cu˙’a G l`a {v4}, {v7} v`a {v9}. 40
41. . Ap´ du. ng trong cˆa´u tr´uctˆo˙’ ch´uc . . . . Nˆe´u d¯ˆo` thi. biˆe˙’u diˆe˜n cˆa´u tr´uca˙’nh huo˙’ ng cu˙’a mˆo.t tˆo˙’ ch´uc th`ıc´acphˆa`n tu˙’ cu˙’a mˆo.t th`anh . . . . . phˆa`n liˆenthˆongma.nh cu˙’a G c´oa˙’nh huo˙’ ng v`ach´uc nˇangngang nhau. Mˆo.t co so˙’ cu˙’a G c´o . . . . thˆe˙’ hiˆe˙’u l`amˆo.t “liˆenminh” c´osˆo´ ngu`oi ´ıtnhˆa´t nhung l˜anhd¯a.o mo.i c´anhˆantrong tˆo˙’ ch´uc. . 0 . . Trˆentˆa.p c´acd¯ı˙’nh biˆe˙’u diˆe˜n c´acth`anhviˆencu˙’a c`ungtˆo˙’ ch´uc, ta x´etd¯ˆo` thi. G d¯uo. c . xˆaydu. ng d¯ˆe˙’ biˆe˙’u diˆe˜n c´ackˆenhtruyˆe` n thˆongsao cho tˆo`n ta.i cung (vi, vj) nˆe´u vi c´othˆe˙’ giao . 0 . . . tiˆe´p v´oi vj. D- `ˆo thi. G d˜ınhiˆenc´oliˆenquan v´oi G. Sˆo´ ngu`oi ´ıtnhˆa´t m`abiˆe´t hoˇa.c c´othˆe˙’ . . . . 0 nhˆa.n tˆa´t ca˙’ c´acsu. kiˆe.n vˆe` tˆo˙’ ch´uc ta.o th`anhmˆo.t d¯ˆo´i co so˙’ cu˙’a G . Ta c´othˆe˙’ n´oirˇa`ng mˆo.t . . . . liˆenminh hiˆe.u qua˙’ d¯ˆe˙’ l˜anhd¯a.o tˆo˙’ ch´uc l`atˆa.p H nh˜ung ngu`oi thoa˙’ m˜an: H = B(G) ∪ B¯(G0), 0 . . . . 0 . . . trong d¯´o B(G) v`a B¯(G ) l`amˆo.t trong c´acco so˙’ v`ac´acd¯ˆo´i co so˙’ cu˙’a G v`a G tuong ´ung . . d¯uo. c cho.n sao cho #H nho˙’ nhˆa´t. . . . Kˆe´ tiˆe´p x´et co 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` u kiˆe.n th´u hai ngh˜ıal`achı˙’ nh˜ung ngu`oi bˆentrong Bp m´oi c´othˆe˙’ c´oa˙’nh huo˙’ ng d¯ˆe´n . . . . . . ngu`oi kh´acc˜ungtrong Bp v`ac´othˆe˙’ thay bˇa`ng d¯iˆe` u kiˆentuong d¯uong: R(V \ Bp) ∩ Bp = ∅. D- iˆe` u kiˆe.n n`aychı˙’ ra rˇa`ng nˆe´u mˆo.t d¯ı˙’nh trong th`anhphˆa`n liˆenthˆongma.nh cu˙’a G thuˆo.c Bp . th`ımo.i d¯ı˙’nh kh´actrong c`ungth`anhphˆa`n liˆenthˆongma.nh n`ayc˜ungthuˆo.c Bp. Do tˆa.p co . . . . so˙’ cu˙’a Gr l`atˆa.p c´acd¯ı˙’nh c´obˆa.c trong bˇa`ng khˆongnˆentˆa.p co so˙’ l˜uyth`ua cu˙’a G ch´ınhl`a [ Bp = Si. ∗ Si∈B . . . Chˇa˙’ng ha.n d¯ˆo` thi. trong H`ınh1.19 c´oco so˙’ l˜uyth`ua l`a {v3, v11, v12, v13}. Cˆa`n ch´u´y . . . . . . rˇa`ng, nˆe´u d¯ˆo` thi. n`aytuong ´ung mˆo.t tˆo˙’ ch´uc th`ı v3 c´othˆe˙’ xem l`angu`oi l˜anhd¯a.o cao nhˆa´t ∗ ∗ ∗ cu˙’a c´acnh´om v1, v2 v`a v3. 1.5 D- ˇa˙’ng cˆa´u cu˙’a c´acd¯ˆo` thi. . . Ta d¯˜abiˆe´t rˇa`ng c`ungmˆo.t d¯ˆo` thi. c´othˆe˙’ d¯uo. c biˆe˙’u diˆe˜n bˇa`ng nhiˆe` u h`ınhv˜ekh´acnhau. Viˆe.c . . . . . . . nhˆa.n biˆe´t d¯uo. c trong tru`ong ho. p n`aohai h`ınhv˜ebiˆe˙’u diˆe˜n c`ungmˆo.t d¯ˆo` thi., trong tru`ong . . ho. p n`aobiˆe˙’u diˆe˜n hai d¯ˆo` thi. kh´acnhau, l`amˆo.t vˆa´n d¯ˆe` khˆongd¯on gia˙’n. 41
42. . . R˜or`angl`ahai h`ınhcho tru´oc biˆe˙’u diˆe˜n c`ungmˆo.t d¯ˆo` thi. chı˙’ khi c´acd¯iˆe` u kiˆe.n sau d¯ˆay . . d¯uo. c thoa˙’ m˜an: 1. Sˆo´ d¯ı˙’nh bˇa`ng nhau; 2. Sˆo´ ca.nh bˇa`ng nhau; 3. Sˆo´ d¯ı˙’nh c`ungbˆa.c bˇa`ng nhau. . D- ´ol`anh˜ung d¯iˆe` u kiˆe.n cˆa`n: hai h`ınhkhˆongthoa˙’ m˜anmˆo.t trong c´acd¯iˆe` u kiˆe.n d¯´oth`ı . khˆongbiˆe˙’u diˆe˜n c`ungmˆo.t d¯ˆo` thi Nhung ch´ungc˜ungkhˆongpha˙’i l`ad¯iˆe` u kiˆe.n d¯u˙’ (h˜aycho v´ıdu. ). Hiˆe˙’n nhiˆenrˇa`ng D- .inh l´y 1.5.1 D- iˆe` u kiˆe. n cˆa`n v`ad¯u˙’ d¯ˆe˙’ hai h`ınhbiˆe˙’u diˆe˜n c`ungmˆo. t d¯ˆo` thi. l`atˆo`n ta. i mˆo. t . . . . . . tuong ´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`ınhn`ayd¯uo. c . . . . . . . . nˆo´i bo˙’ i mˆo. t ca. nh th`ıhai d¯ı˙’nh tuong ´ung cu˙’a h`ınhkia c˜ungd¯uo. c nˆo´i v´oi nhau bo˙’ i mˆo. t . . ca. nh v`anguo. c la. i. . Viˆe.c t`ımmˆo.t tiˆeuchuˆa˙’n d¯on gia˙’n v`ahiˆe.u qua˙’ d¯ˆe˙’ ph´athiˆe.n t´ınhd¯ˇa˙’ng cˆa´u cu˙’a c´acd¯ˆo` . . . . thi. vˆa˜n l`ab`aito´anmo˙’ cu˙’a l´ythuyˆe´t d¯ˆo` thi. v`ad¯angc`ond¯uo. c tiˆe´p tu. c nghiˆenc´uu. 1.5.1 1−d¯ˇa˙’ng cˆa´u . . D- `ˆo thi. c´oc´acd¯iˆe˙’m kh´op gˆo`m ´ıtnhˆa´t hai d¯ˆo` thi. con khˆongc´od¯iˆe˙’m kh´op. Mˆo˜i d¯ˆo` thi. con . . liˆenthˆongl´on nhˆa´t khˆongc´od¯iˆe˙’m kh´op go.i l`a khˆo´i. D- `ˆo thi. trong H`ınh1.21 c´onˇamkhˆ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´op chı˙’ c´omˆo.t khˆo´i. •. • • . . . . . . . . . . . a c . . b . . . . . . •. •. • • . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . • • . . . . . . . . . . •. H`ınh1.21: 42
43. So s´anhd¯ˆo` thi. khˆongliˆenthˆongtrong H`ınh1.22 v`ad¯ˆo` thi. trong H`ınh1.21. Hiˆe˙’n nhiˆen . hai d¯ˆo` thi. n`aykhˆongd¯ˇa˙’ng cˆa´u (ch´ungc´osˆo´ d¯ı˙’nh kh´acnhau); nhung ch´ungc´omˆo´i liˆenhˆe. . l`ac´ackhˆo´i trong H`ınh1.21 d¯ˇa˙’ng cˆa´u v´oi c´acth`anhphˆa`n cu˙’a d¯ˆo` thi. trong H`ınh1.22. C´ac . d¯ˆo` thi. n`aygo.i l`a 1-d¯ˇa˙’ng cˆa´u. Ch´ınhx´achon: - . D.inh ngh˜ıa1.5.2 Hai d¯ˆo` thi. G1 v`a G2 go.i l`a1−d¯ˇa˙’ng cˆa´u nˆe´u ch´ungtro˙’ th`anhd¯ˇa˙’ng cˆa´u . v´oi nhau sau khi ´apdu. ng mˆo.t sˆo´ lˆa`n ph´epto´ansau: . Ph´epto´an1. “T´ach” mˆo.t d¯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.p r`o.i nhau. y • •. •. . . . . . . . . . . a . . 1 b1 . . . . . . . . . • • •. •• • • . . . . . a . c c . 3 . b2 1 2 . . . . . . . . . . . . • a2 •. • • . . . x . . . . . . . . . . . . . . . . . . . . •. H`ınh1.22: . . 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´u nˆe´u v`achı˙’ nˆe´u ch´ungd¯ˇa˙’ng cˆa´u. D- iˆe` u g`ıs˜exa˙’y ra khi ta nˆo´i hai th`anhphˆa`n cu˙’a H`ınh1.22 bˇa`ng c´ach “d´an”hai d¯ı˙’nh . . (chˇa˙’ng ha.n x v`a y)? Ch´ungta nhˆa.n d¯uo. c d¯ˆo` thi. trong H`ınh1.23. . Hiˆe˙’n nhiˆenc´acd¯ˆo` thi. trong H`ınh1.23 l`a1−d¯ˇa˙’ng cˆa´u v´oi d¯ˆo` thi. trong H`ınh1.22. V`ı . c´ackhˆo´i cu˙’a d¯ˆo` thi. trong H`ınh1.23 d¯ˇa˙’ng cˆa´u v´oi c´ackhˆo´i cu˙’a d¯ˆo` thi. trong H`ınh1.21, nˆen hai d¯ˆo` thi. n`ayl`a1−d¯ˇa˙’ng cˆa´u. Do d¯´oba d¯ˆo` thi. trong c´acH`ınh1.21, 1.22 v`a1.23 l`ad¯ˆoimˆo.t 1−d¯ˇa˙’ng cˆa´u. 1.5.2 2−d¯ˇa˙’ng cˆa´u Trong phˆa`n trˆench´ungta d¯˜atˆo˙’ng qu´atho´akh´ainiˆe.m d¯ˇa˙’ng cˆa´u bˇa`ng kh´ainiˆe.m 1−d¯ˇa˙’ng . . . . cˆa´u. C´acd¯ˆo` thi. d¯ˇa˙’ng cˆa´u th`ı1−d¯ˇa˙’ng cˆa´u nhung nguo. c la.i khˆongd¯´ung.Su. tˆo˙’ng qu´atho´a . . . rˆa´t h˜uu ´ıch trong viˆe.c nghiˆenc´uu c´acd¯ˆo` thi. c´od¯iˆe˙’m kh´op. 43
44. • •. . . . . . . . . . . a . . 1 . . . . . . . . • •• • • . . . c c . b2 1 2 . . . . . . . xy a . • 2 •. • . . . . . . . . . b . 1 . . . . • •. . . . . . a . . 3 . . . . . . . . . . . . . . • •. H`ınh1.23: . . Ch´ungta 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´ethai d¯ı˙’nh x v`a y m`axo´ach´ung(v`ac´acca.nh liˆenthuˆo.c ch´ung)th`ıd¯ˆo` thi. mˆa´t t´ınhliˆenthˆong.N´oic´ach kh´ac, G gˆo`m mˆo.t d¯ˆo` thi. con g1 v`aphˆa`n b`u . . cu˙’a n´o¯g1 sao cho g1 v`a¯g1 c´od¯´unghai d¯ı˙’nh chung: x v`a y. Gia˙’ su˙’ rˇa`ng ch´ungta thu. c hiˆ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. c t`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.cg ¯1. Bˆaygi`o nˆo´i hai d¯ˆo` thi. g1 v`a¯g1 bˇa`ng c´ach ho. p nhˆa´t d¯ı˙’nh x1 v´oi d¯ı˙’nh y2 v`a . . . d¯ı˙’nh x2 v´oi d¯ı˙’nh y1. (Hiˆe˙’n nhiˆenc´acca.nh m`aliˆenthuˆo.c v´oi x hoˇa.c y trong G d¯ic`ungv´oi . . . . . . . g1 hoˇa.cg ¯1, khˆonga˙’nh huo˙’ ng d¯ˆe´n d¯ˆo` thi. thu d¯uo. c o˙’ bu´oc cuˆo´i). . Hai d¯ˆo` thi. go.i l`a2−d¯ˇa˙’ng cˆa´u nˆe´u ch´ungtro˙’ th`anhd¯ˇa˙’ng cˆa´u sau Ph´epto´an1 hoˇa.c . Ph´epto´an2, hoˇa.c ca˙’ hai ph´epto´ansau mˆo.t sˆo´ lˆa`n thu. c hiˆe.n. H`ınh1.24 chı˙’ ra hai d¯ˆo` thi. trong H`ınh1.24(a) v`a(d) l`a2−d¯ˇa˙’ng cˆa´u. Ch´u´yrˇa`ng trong H`ınh1.24(a), bˆa.c cu˙’a d¯ı˙’nh x bˇa`ng bˆo´n, c`ontrong H`ınh1.24(d) khˆongc´od¯ı˙’nh n`aobˆa.c bˆo´n. . . . . . T`u d¯i.nh ngh˜ıa,suy ra 1−d¯ˇa˙’ng cˆa´u l`a2−d¯ˇa˙’ng cˆa´u, nhung nguo. c la.i chua chˇa´c d¯´ung. . . Tuy nhiˆen,v´oi c´acd¯ˆo` thi. k−liˆenthˆongv´oi k ≥ 3 th`ıba kh´ainiˆe.m d¯ˇa˙’ng cˆa´u, 1−d¯ˇa˙’ng cˆa´u . v`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´u ch´ungthoa˙’ d¯iˆe` u kiˆe.n sau: Tˆo`n . . . . . . . . ta.i tuong ´ung mˆo.t-mˆo.t gi˜ua c´acca.nh cu˙’a G1 v`a G2 v`amˆo.t tuong ´ung gi˜ua c´acchu tr`ınh . . . cu˙’a G1 v`a G2 sao cho mˆo.t chu tr`ınhtrong G1 d¯uo. c ta.o bo˙’ i c´acca.nh cu˙’a G1 c´omˆo.t chu . . . . . . . . . . . . tr`ınhtuong ´ung trong G2 d¯uo. c ta.o bo˙’ i c´acca.nh tuong ´ung trong G2, v`anguo. c la.i. T`u 44
45. x x1 x2 .•• . .• •• . . . . . . . . . . . . . . . . . . . . . • . • . . . . . . . . . . . . . g¯1 . . . . . . . . . g . . 1 . . . . . . . . . . . . . . . •• • •• y y1 y2 (a) (b) x1 x2 .•. •• . .•• . . . . . . . . . . . . . . . . . . . . . g1 . . . . . . . . . . . . . g¯1 . . . . . . . . . . . • . • . . . . . . . . . . . . . . . • •• •• y1 y2 (c) (d) H`ınh1.24: . . . d¯i.nh ngh˜ıasuy ra c´acd¯ˆo` thi. d¯ˇa˙’ng cˆa´u c´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.c mˆo.t khˆo´i n`aod¯´o,nˆenmˆo˜i chu . . . . tr`ınhtrong G vˆa˜n tuong ´ung c´acca.nh cu˙’a n´okhi thu. c hiˆe.n Ph´epto´an1 trˆen G. Do d¯´o,c´ac . . . d¯ˆo` thi. 1−d¯ˇa˙’ng cˆa´u c´ot´ınhchˆa´t tuong ´ung chu tr`ınh. . . . . . Tuong tu. , x´etchu tr`ınh µ trong d¯ˆo` thi. G sau khi thu. c hiˆe.n Ph´epto´an2 trˆen G. V´oi . . . chu tr`ınh µ, ta c´oba tru`ong ho. p xa˙’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˙’i ch´u.a ca˙’ 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. p 3, µ vˆa˜n gˆo`m c´acca.nh c˜u,ngoa.i tr`u dˆaychuyˆe` n gi˜ua c´acd¯ı˙’nh x v`a y trong g1 (thuˆo.c . . chu tr`ınh µ) bi. “d¯a˙’o nguo. c la.i”. Do d¯´o,mˆo˜i chu tr`ınhsau Ph´epto´an2 vˆa˜n gˆo`m ch´ınh . . . . nh˜ung ca.nh c˜u.Suy ra c´acd¯ˆo` thi. 2−d¯ˇa˙’ng cˆa´u c˜ungc´ot´ınhchˆa´t tuong ´ung chu tr`ınh. 45
46. . . . D- .inh l´y 1.5.3 Hai d¯ˆo` thi. l`a 2−d¯ˇa˙’ng cˆa´u nˆe´u v`achı˙’ nˆe´u ch´ungc´otuong ´ung chu tr`ınh. . . . . Ch´ung minh. D- iˆe` u kiˆend¯u˙’ suy t`u c´acl´yluˆa.n trˆen.Ch´ung minh d¯iˆe` u kiˆe.n cˆa`n kh´ohon v`a c´othˆe˙’ xem [55]. / . . . . Nhu s˜ethˆa´y sau, c´ackh´ainiˆe.m 2−d¯ˇa˙’ng cˆa´u v`atuong ´ung chu tr`ınhd¯´ongvai tr`oquan . tro.ng khi nghiˆenc´uu d¯ˆo´i ngˆa˜u cu˙’a c´acd¯ˆo` thi. phˇa˙’ng. 1.6 C´acd¯ˆo` thi. d¯ˇa.c biˆe.t . . . . Phˆa`n n`aygi´oi thiˆe.u mˆo.t sˆo´ d¯ˆo` thi. d¯ˇa.c biˆe.t thu`ong gˇa.p trong c´acmˆoh`ınhthu. c tˆe´. C´acd¯ˆo` . . thi. n`ayd¯uo. c quan tˆamnhiˆe` u v`ı: . • T`u ph´atbiˆe˙’u mˆo.t sˆo´ b`aito´an; . • T`u c´act´ınhchˆa´t d¯ˇa.c biˆe.t cu˙’a ch´ung; • Phu. c vu. cho mˆo.t sˆo´ thuˆa.t to´an. 1.6.1 D- `ˆo thi. khˆongc´oma.ch . . . . . D- ˆayl`ad¯ˆo` thi. thu`ong gˇa.p nhˆa´t khi biˆe˙’u diˆe˜n c´acquan hˆe. th´u tu. bˆo. phˆa.n trˆenc´acphˆa`n tu˙’ : . . . v´oi mˆo.t quan hˆe. th´u tu. ≤ trˆentˆa.p V, x´etd¯ˆo` thi. G = (V, E) trong d¯´o (vi, vj) ∈ E ⇔ i ≤ j. C´acb`aito´anluˆo`ng trˆenma.ng vˆa.n ta˙’i x´etc´acd¯ˆo` thi. n`ay(c˜ungxem 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´ong G go.i l`a phˇa˙’ng nˆe´u c´othˆe˙’ biˆe˙’u diˆe˜n trˆenmˆo.t mˇa.t phˇa˙’ng R v´oi c´acd¯ı˙’nh . . . 2 . . . . . . tuong ´ung c´acd¯iˆe˙’m phˆanbiˆe.t trˆen R v`ac´acd¯u`ong cong khˆongtu. cˇa´t tuong ´ung c´acca.nh . . . sao cho hai d¯u`ong cong bˆa´t k`ykhˆongcˇa´t nhau ngoa.i tr`u ta.i c´acd¯ı˙’nh chung. . D- `ˆo thi. trong H`ınh1.25(a) l`aphˇa˙’ng v`ıch´ungta c´othˆe˙’ v˜ela.i nhu trong H`ınh1.25(b). . . . . . C´acd¯ˆo` thi. phˇa˙’ng s˜ed¯uo. c nghiˆenc´uu trong Chuong 6. 46
47. a a • • e ••. e ••. b b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •• •• d c d c (a) (b) . . H`ınh1.25: D- `ˆo thi. (a) d¯uo. c biˆe˙’u diˆe˜n la.i trong h`ınh(b) l`aphˇa˙’ng. 47
48. Chu.o.ng 2 . C´acsˆo´ co ba˙’n cu˙’a d¯ˆo` thi. 2.1 Chu sˆo´ . . . . Kh´ainiˆe.m m`ach´ungta s˜ed¯ˆe` cˆa.p o˙’ d¯ˆay khˆongphu. thuˆo. c v`aosu. d¯i.nh hu´ong: ta s˜en´oivˆe` . . . ca. nh ch´u khˆongpha˙’i cung. D- ˆe˙’ tˆo˙’ng qu´atx´etd¯ad¯ˆo` thi. vˆohu´ong G := (V, E) c´o n 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`a chu sˆo´ cu˙’a d¯ˆo` thi. G. . . . 0 . . . D- .inh l´y 2.1.1 Cho d¯ad¯ˆo` thi. vˆohu´ong G = (V, E). Gia˙’ su˙’ G l`ad¯ˆo` thi. nhˆa. n d¯uo. c t`u G . . bˇa`ng c´achnˆo´i hai d¯ı˙’nh a v`a b cu˙’a G bo˙’ i mˆo. t ca. nh m´oi; nˆe´u a v`a b tr`ungnhau hoˇa. c c´othˆe˙’ . . nˆo´i v´oi nhau bo˙’ i mˆo. t dˆaychuyˆe` n cu˙’a G th`ı ρ(G0) = ρ(G), ν(G0) = ν(G) + 1; . . . . . trong tru`ong ho. p nguo. c la. i ρ(G0) = ρ(G) + 1, ν(G0) = ν(G). . . 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 + 1 ca.nh v`agia˙’ 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` n nˆo´i a v´oi b. Khi d¯´oph´epbiˆe´n d¯ˆo˙’i G th`anh G khˆongthay d¯ˆo˙’i sˆo´ th`anhphˆa`n liˆenthˆong,t´u.c l`a p = p0. Do d¯´o ρ(G0) = n0 − p0 = n − p = ρ(G), ν(G0) = m0 − ρ(G0) = ν(G) + 1. 49
49. . . 0 Nguo. c la.i, nˆe´u a 6= b v`akhˆongtˆo`n ta.i dˆaychuyˆe` n nˆo´i a v`a b, th`ıdo c´ach x´acd¯i.nh G 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.2 ρ(G) ≥ 0 v`a ν(G) ≥ 0. . . Ch´ung minh. Thˆa.t vˆa.y, xuˆa´t ph´att`u d¯ˆo` thi. th`anhlˆa.p bˇa`ng c´acd¯ı˙’nh cu˙’a d¯ad¯ˆo` thi. vˆo . . . . 0 . . hu´ong G, d¯ı˙’nh no. cˆolˆa.p v´oi d¯ı˙’nh kia, ta xˆaydu. ng G dˆa`n dˆa`n t`ung ca.nh mˆo.t; kho˙’ i d¯ˆa`u ta c´o ρ = 0, ν = 0; mˆo˜i khi thˆemmˆo.t ca.nh, th`ıhoˇa.c ρ tˇangv`al´ucd¯´o ν khˆongd¯ˆo˙’i, hoˇa.c ν tˇang . . 0 v`al´ucd¯´o ρ khˆongd¯ˆo˙’i. Nhu vˆa.y, trong qu´atr`ınhxˆaydu. ng d¯ˆo` thi. G , c´acsˆo´ ρ v`a ν chı˙’ c´o thˆe˙’ tˇang. / . . D- ˆe˙’ c´othˆe˙’ vˆa.n du. ng nh˜ung kˆe´t qua˙’ phong ph´ucu˙’a d¯a.i sˆo´ vector trong viˆe.c nghiˆenc´uu, . . . . . . . . ngu`oi ta thu`ong d¯ˇa.t tuong ´ung mˆo˜i chu tr`ınhtrong G v´oi mˆo.t vector theo c´ach sau d¯ˆay. . . . . Mˆo˜i ca.nh cu˙’a d¯ad¯ˆo` thi. G d¯ˆe` u d¯uo. c d¯i.nh hu´ong mˆo.t c´ach t`uy´y;nˆe´u chu tr`ınh µ d¯i . . . . . . qua ca.nh ek, rk lˆa`n thuˆa.n hu´ong v`a sk lˆa`n nguo. c hu´ong th`ıta d¯ˇa.t ck := rk − sk (nˆe´u ek l`a . . mˆo.t khuyˆenth`ıta luˆonqui u´oc sk = 0). Vector m chiˆe` u (c1, c2, . . . , cm) . . . . go.i l`a vector chu tr`ınh tuong ´ung v´oi µ v`ak´yhiˆe.u l`a ~µ (hay l`a µ nˆe´u khˆongthˆe˙’ gˆayra nhˆa`m lˆa˜n). 0 00 . . . C´acchu tr`ınh µ, µ , µ , go.i l`a d¯ˆo. c lˆ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´acca.nh. . D- .inh l´y 2.1.3 Chu sˆo´ ν(G) cu˙’a G = (V, E) bˇa`ng sˆo´ cu. c d¯a. i c´acchu tr`ınhd¯ˆo. c lˆa. p. . . . . Ch´ung minh. Tiˆe´n h`anhnhu trong Hˆe. qua˙’ 2.1.2: d¯ˆa`u tiˆenta lˆa´y d¯ˆo` thi. vˆohu´ong khˆong . . 0 . c´oca.nh v´oi tˆ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.1, chu sˆo´ s˜etˇangmˆo.t d¯on vi. nˆe´u ca.nh thˆemv`aolˆa.p ra c´acchu . . . . . . tr`ınhm´oi, chu sˆo´ khˆongthay d¯ˆo˙’i trong tru`ong ho. p nguo. c la.i. . . . . . Gia˙’ su˙’ , tru´oc khi thˆemca.nh ek ta d¯˜ac´omˆo.t co so˙’ 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´t hiˆe.n thˆemc´acchu tr`ınhso cˆa´p m´oi γ1, γ2, , n`aod¯´o.Hiˆe˙’n nhiˆen γ1 khˆongthˆe˙’ biˆe˙’u diˆe˜n tuyˆe´n t´ınhqua hˆe. c´acchu tr`ınh µj (v`ıc´acvector 50
50. . . . . . . . tuong ´ung c´acchu tr`ınh µj c´oth`anhphˆa`n th´u k bˇa`ng khˆong,trong khi vector tuong ´ung . chu tr`ınh γ1 c´oth`anhphˆa`n th´u k kh´ackhˆong).Mˇa.t kh´acc´acvector γ2, γ3, c´othˆe˙’ biˆe˙’u . . diˆe˜n tuyˆe´n t´ınhqua γ1, µ1, µ2, µ3, T´omla.i mˆo˜i khi chu sˆo´ tˇangmˆo.t d¯on vi. th`ısˆo´ cu. c . . . . d¯a.i c´acchu tr`ınhd¯ˆo.c lˆa.p tuyˆe´n t´ınhc˜ungtˇanglˆenmˆo.t d¯on vi D- .inh l´yd¯uo. c ch´ung minh. / T`u. kˆe´t qua˙’ n`ay, dˆe˜ d`angsuy ra: . . Hˆe. qua˙’ 2.1.4 (a) D- a d¯ˆo` thi. vˆohu´ong G khˆongc´ochu tr`ınhnˆe´u v`achı˙’ nˆe´u ν(G) = 0. . . (b) D- a d¯ˆo` thi. vˆohu´ong G c´od¯´ungmˆo. t chu tr`ınhnˆe´u v`achı˙’ nˆe´u ν(G) = 1. . . . D- .inh l´y 2.1.5 Trong d¯ˆo` thi. c´ohu´ong liˆenthˆongma. nh, chu sˆo´ bˇa`ng sˆo´ cu. c d¯a. i c´acma. ch d¯ˆo. c lˆa. p tuyˆe´n t´ınh. . . . . Ch´ung minh. Thˆa.t vˆa.y, x´etd¯ˆo` thi. vˆohu´ong lˆa.p bo˙’ i c´accung kh´acnhau cu˙’a G (mˆo˜i cung . . . . tuong ´ung mˆo.t cˇa.p ca.nh) v`amˆo.t chu tr`ınhso cˆa´p µ; ta phˆanhoa.ch tˆa.p c´acd¯ı˙’nh trˆenchu . 0 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,tˆa.p S c´acd¯ı˙’nh 00 . 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 n´o.V`ısˆo´ c´accung . 0 00 . 0 0 0 . 0 d¯ira bˇa`ng sˆo´ c´accung d¯it´oi nˆen#S = #S ; gia˙’ su˙’ v1, v2, . . . , vk l`ac´acphˆa`n tu˙’ cu˙’a S v`a 00 00 00 . 00 v1 , v2 , . . . , vk l`ac´acphˆa`n tu˙’ cu˙’a S . Trˆenchu tr`ınh µ, c´acphˆa`n tu˙’. cu˙’a S0 v`acu˙’a S00 xen k˜enhau v`ata gia˙’ su˙’. rˇa`ng sau d¯ı˙’nh 0 00 . . vi th`ıd¯ı˙’nh d¯ˆa`u tiˆenbˇa´t gˇa.p (khˆongthuˆo.c S) l`a vi ; cuˆo´i c`ung,nˆe´u µ0 l`amˆo.t d¯u`ong d¯igˇa.p . . . . . d¯ı˙’nh x tru´oc d¯ı˙’nh y th`ıta k´yhiˆe.u µ0[x, y] l`ad¯u`ong d¯ibˆo. phˆa.n cu˙’a µ0 t`u x d¯ˆe´n y. V`ıd¯ˆo` 0 00 ˙’ . thi. liˆenthˆongma.nh nˆentˆo`n ta.i ma.ch µ1 d¯iqua vi+1 v`a vi v`ad`ungc´accung cu˙’a µ d¯ˆe d¯it`u 0 00 ˙’ . ˙’ vi+1 d¯ˆe´n vi . Chu tr`ınh µ l`amˆo.t tˆ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.y mo.i chu tr`ınhso cˆa´p d¯ˆe` u l`atˆo˙’ ho. p tuyˆe´n t´ınhcu˙’a c´acma.ch, d¯ˆo´i v´oi c´acchu tr`ınh . . bˆa´t k`yd¯iˆe` u d¯´oc˜ungd¯´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.t co so˙’ cu˙’a khˆonggian vector con sinh bo˙’ i c´acchu . . . tr`ınh,v`atheo D- .inh l´y2.1.3 th`ıco so˙’ n`ayc´osˆo´ chiˆe` u l`a ν(G). Vˆa.y sˆo´ cu. c d¯a.i c´acma.ch d¯ˆo.c lˆa.p tuyˆe´n t´ınhbˇa`ng ν(G)./ 51
51. 2.2 Sˇa´c sˆo´ . . . . Gia˙’ su˙’ rˇa`ng ch´ungta c´omˆo.t d¯ˆo` thi. vˆohu´ong 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´n d¯ˆe` d¯ˇa.t ra la.i khˆongmang t´ınhthu. c tiˆ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. c tˆo,ch´ungta c´othˆe˙’ . . nh´omch´ungv`aoc´actˆa.p kh´acnhau-mˆo.t tˆa.p gˆo`m c´acd¯ı˙’nh d¯uo. c tˆom`aud¯o˙’, mˆo.t tˆa.p c´ac . . d¯ı˙’nh d¯uo. c tˆom`auxanh, vˆanvˆan.D- ˆaych´ınhl`ab`aito´anphˆanhoa.ch. B`aito´antˆom`auv`a . . . phˆanhoa.ch d˜ınhiˆenc´othˆe˙’ x´ettrˆenc´acca.nh cu˙’a d¯ˆo` thi Trong tru`ong ho. p d¯ˆo` thi. phˇa˙’ng thˆa.m ch´ıc´othˆe˙’ quan tˆamd¯ˆe´n viˆe.c tˆom`auc´acdiˆe.n. . . Trong phˆa`n n`ayta chı˙’ x´etc´acd¯ˆo` thi. vˆohu´ong liˆenthˆong. . . D- .inh ngh˜ıa2.2.1 Cho tru´oc mˆo.t sˆ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`ungmˆo.t m`au. . Sˆo´ p nho˙’ nhˆa´t, m`ad¯ˆo´i v´oi sˆo´ d¯´o G l`a p−sˇa´c go.i l`a sˇa´c sˆo´ cu˙’a d¯ˆo` thi. G v`ak´yhiˆe.u l`a γ(G). V´ıdu. 2.2.2 H`ınh2.1 minh ho.a ba c´ach tˆom`aukh´acnhau cu˙’a d¯ˆ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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . g•• . y g•• . y r•• . r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • p r b (a) (b) (c) H`ınh2.1: . V´ıdu. 2.2.3 Ba˙’n d¯ˆo` d¯i.a l´y. Ta v˜etrˆenmˇa.t phˇa˙’ng mˆo.t ba˙’n d¯ˆo`. Go.i V l`atˆa.p ho. p c´ac . . . . . . nu´oc, d¯ˇa.t (i, j) ∈ E nˆe´u c´acnu´oc i v`a j c´obiˆengi´oi chung. D- `ˆo thi. G = (V, E) d¯ˆo´i x´ung v`ac´ot´ınhchˆa´t rˆa´t d¯ˇa.c biˆe.t l`a:c´othˆe˙’ v˜en´olˆenmˇa.t phˇa˙’ng m`akhˆongc´ohai ca.nh n`aocˇ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´c . . sˆo´ cu˙’a mo.i d¯ˆo` thi. phˇa˙’ng d¯ˆe` u nho˙’ hon hoˇa.c bˇa`ng bˆo´n (D- .inh l´y6.4.7). Nhu vˆa.y bˇa`ng bˆo´n . . m`auc˜ungd¯u˙’ d¯ˆe˙’ tˆom`auba˙’n d¯ˆo` phˇa˙’ng sao cho hai nu´oc kˆe` nhau khˆongc`ungmˆo.t m`au. 52
52. . T`u d¯i.nh ngh˜ıadˆe˜ d`angsuy ra 1. Mˆo.t d¯ˆo` thi. chı˙’ c´oc´acd¯ı˙’nh cˆolˆa.p l`a1−sˇa´c. 2. Mˆo.t d¯ˆo` thi. c´omˆo.t hoˇa.c hai ca.nh (khˆongpha˙’i l`amˆo.t khuyˆen)c´osˇa´c sˆo´ ´ıtnhˆa´t bˇa`ng hai. 3. D- `ˆo thi. d¯ˆa`y d¯u˙’ n d¯ı˙’nh Kn l`a n−sˇa´c. . . 4. D- `ˆo thi. l`amˆo.t chu tr`ınhd¯on gia˙’n v´oi n d¯ı˙’nh, n > 3, l`a2−sˇa´c nˆe´u n chˇa˜n v`a3−sˇa´c nˆe´u n le˙’. 5. Hiˆe˙’n nhiˆen,mo.i d¯ˆo` thi. 2−sˇa´c l`ahai phˆa`n do ch´ungta c´othˆe˙’ phˆanhoa.ch tˆa.p c´acd¯ı˙’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`n l`a . . . . . . 2−sˇa´c, v´oi mˆo.t tru`ong ho. p ngoa.i lˆe. tˆa`m thu`ong: d¯ˆo` thi. c´o´ıtnhˆa´t hai d¯ı˙’nh cˆolˆa.p v`a . khˆongc´oca.nh l`ahai phˆa`n nhung l`a1−sˇa´c. . D- .inh ngh˜ıa2.2.4 Ta go.i sˇa´c l´op cu˙’a d¯ˆ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 khˆongc`ungmˆo.t m`au; . . . 2. D- iˆe` u n`aykhˆongthˆe˙’ l`amd¯uo. c v´oi (q − 1) m`au. . 0 0 0 Nhˆa.n x´etrˇa`ng sˇa´c l´op cu˙’a d¯ˆo` thi. G = (V, E) ch´ınhl`asˇa´c sˆo´ cu˙’a d¯ˆo` thi. G = (V ,E ) . . . 0 . . . 0 0 0 0 d¯uo. c x´acd¯i.nh nhu sau: mˆo˜i d¯ı˙’nh cu˙’a G tuong ´ung mˆo.t ca.nh cu˙’a G; ca.nh e = (v1, v2) ∈ E . . . . 0 0 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´c l´op d¯ua vˆe` b`aito´ansˇa´c sˆo´. Du´oi d¯ˆayl`amˆo.t v`aikˆe´t qua˙’ co ba˙’n vˆe` sˇa´c sˆo´. . . D- .inh l´y 2.2.5 [K¨onig] D- `ˆo thi. vˆohu´ong G l`a 2−sˇa´c nˆe´u v`achı˙’ nˆe´u n´okhˆongc´ochu tr`ınh c´od¯ˆo. d`aile˙’. . . Ch´ung minh D- iˆe` u kiˆe.n cˆa`n. Nˆe´u d¯ˆ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˙’a mˆo.t chu tr`ınhloa.i nhu vˆa.y khˆongthˆe˙’ tˆobˇa`ng hai m`au theo nhu. quy tˇa´c d¯˜achı˙’ ra o˙’. trˆen. . . D- iˆe` u kiˆe.n d¯u˙’. Gia˙’ su˙’ d¯ˆo` thi. G khˆongc´ochu tr`ınhc´od¯ˆo. d`aile˙’, ta ch´ung minh n´ol`a2−sˇa´c. Khˆonggia˙’m tˆ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: 53
53. • tˆom`auxanh cho mˆo.t d¯ı˙’nh a n`aod¯´o; . . . • nˆe´u mˆo.t d¯ı˙’nh x n`aod¯´od¯˜ad¯uo. c tˆoxanh, th`ıta tˆod¯o˙’ tˆa´t ca˙’ c´acd¯ı˙’nh kˆe` v´oi n´o;nˆe´u . . . d¯ı˙’nh y d¯˜ad¯uo. c tˆod¯o˙’, th`ıta tˆoxanh tˆa´t ca˙’ c´acd¯ı˙’nh kˆe` v´oi y. . . . V`ıd¯ˆo` thi. G liˆenthˆong,nˆens´om hay muˆo.n th`ımo.i d¯ı˙’nh cu˙’a n´od¯ˆe` u d¯uo. c tˆom`auhˆe´t, v`a . . . mˆo.t d¯ı˙’nh x khˆongthˆe˙’ c`ungmˆo.t l´ucd¯uo. c tˆoxanh v`atˆod¯o˙’, v`ınhu vˆa.y th`ı x v`a a s˜ec`ung nˇa`m trˆenmˆo.t chu tr`ınhc´od¯ˆo. d`aile˙’. Vˆa.y d¯ˆo` thi. G l`a2−sˇa´c. / . . . . . . Ch´u´yrˇa`ng t´ınhchˆa´t d¯ˆo` thi. G khˆongc´ochu tr`ınhv´oi d¯ˆo. d`aile˙’ tuong d¯uong v´oi t´ınh . . . chˆa´t G khˆongc´ochu tr`ınhso cˆa´p v´oi d¯ˆo. d`aile˙’. Thˆa.t vˆ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 < p v`a vj = vk, ta phˆanchia µ th`anh . . hai chu tr`ınhbˆo. phˆa.n µ1 = {vj, . . . , vk} v`a µ2 = {v0, . . . , vj, vk, . . . , v0}; hon n˜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´y rˇa`ng nˆe´u . . tiˆe´p tu. c phˆanchia chu tr`ınh µ theo c´ach d¯´ocho d¯ˆe´n khi c`onc´othˆe˙’ l`amd¯uo. c, th`ımˆo˜i lˆa`n . . . vˆa˜n c`ond¯uo. c mˆo.t chu tr`ınhc´od¯ˆo. d`aile˙’; v`ıcuˆo´i c`ungmo.i chu tr`ınhd¯ˆe` u l`aso cˆa´p, nˆenxa˙’y ra mˆauthuˆa˜n; v`ata c´od¯iˆe` u cˆa`n ch´u.ng minh. D- .inh l´ysau d¯ˆaycho ta biˆe´t cˆa.n trˆencu˙’a sˇa´c sˆo´. - . D.inh l´y 2.2.6 K´yhiˆe. u dmax l`abˆa. c cu. c d¯a. i cu˙’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`y d¯u˙’, c´o dmax d¯ı˙’nh th`ı γ(G) ≤ dmax. 2.2.1 C´ach t`ımsˇa´c sˆo´ X´etd¯ˆo` thi. G = (V, Γ) c´o n d¯ı˙’nh v`a m ca.nh; muˆo´n t`ımsˇa´c sˆo´ cu˙’a n´ota c´othˆe˙’ d`ungmˆo.t . . . . . . . . phuong ph´apthu. c nghiˆe.m rˆa´t d¯on gia˙’n, ´apdu. ng tru. c tiˆe´p d¯uo. c, nhung khˆongpha˙’i l´ucn`ao . . . c˜ungc´ohiˆe.u qua˙’ hoˇa.c c´othˆe˙’ d`ungphuong ph´apgia˙’i t´ıch, n´ocho ta mˆo.t l`oi gia˙’i hˆe. thˆo´ng, . . nhung n´oichung cˆa`n m´ayt´ınhd¯iˆe.n tu˙’ . 54
54. . . . Phuong ph´apthu. c nghiˆe.m Bˇa`ng c´ach tˆom`aut`uy´yd`ungc´acm`au1, 2, . . . , p v`at`ımc´ach loa.i dˆa`n mˆo.t m`aun`aod¯´o(go.i . . l`a“m`aut´oi ha.n”) trong c´acm`auˆa´y. Muˆo´n vˆa.y, ta x´etd¯ı˙’nh v c´om`aut´oi ha.n d¯´ov`ac´ac jk jk . . th`anhphˆa`n liˆenthˆong C1 ,C2 , cu˙’a d¯ˆo` thi. con sinh ra bo˙’ i hai m`aukhˆongt´oi ha.n j v`a . . jk jk k. Ta c´othˆe˙’ lˆa.p t´uc thay m`aucu˙’a d¯ı˙’nh v nˆe´u c´actˆa.p ho. p C1 ∩ Γ(v),C2 ∩ Γ(v), khˆong pha˙’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´acd¯ı˙’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ˆongthay d¯ˆo˙’i m`au cu˙’a c´acd¯ı˙’nh kh´ac),cuˆo´i c`ungtˆod¯ı˙’nh v m`au j (l´ucn`ayd¯ı˙’nh v khˆongkˆe` v´o.i d¯ı˙’nh n`aoc´o m`au j). Phu.o.ng ph´apgia˙’i t´ıch . . . . . . Kiˆe˙’m tra bˇa`ng c´ach gia˙’i t´ıch xem d¯ˆo` thi. G c´othˆe˙’ d¯uo. c tˆobˇa`ng p m`aud¯uo. c khˆong.Phuong . . . . . . ph´apd¯´onhu sau: V´oi mˆo˜i c´ach tˆobˇa`ng p m`au,ta cho tuong ´ung v´oi mˆo.t hˆe. thˆo´ng c´acsˆo´ . . . xij, i = 1, 2, . . . , n; j = 1, 2, . . . , p, d¯uo. c x´acd¯i.nh nhu sau: ( 1 nˆe´u d¯ı˙’nh i c´om`au j, xij = . . . . . 0 trong tru`ong ho. p nguo. c la.i. - Dˇa.t ( 1 nˆe´u ca.nh ej liˆenthuˆo.c d¯ı˙’nh vi, rij = . . . . . 0 trong tru`ong ho. p nguo. c la.i. . L´ucd¯´ob`aito´antro˙’ th`anht`ımc´acsˆo´ nguyˆen xij sao cho:   xij ≥ 0, Pp q=1 xiq ≤ 1, i = 1, 2, . . . , n,  Pn k=1 rjkxkq ≤ 1, j = 1, 2, . . . , m; q = 1, 2, . . . , p. . . . . . Ta c´ohˆe. bˆa´t d¯ˇa˙’ng th´uc tuyˆe´n t´ınh.Dˆe˜ r`angthˆa´y rˇa`ng hˆe. d¯´oth´ıch ho. p v´oi c´acphuong . . . . ph´apthˆongthu`ong cu˙’a quy hoa.ch nguyˆenv`ado d¯´oc´othˆe˙’ d`ungphuong ph´apcu˙’a Gomory . . . . (du. a trˆenphuong ph´apd¯on h`ınhcu˙’a Dantzig) d¯ˆe˙’ gia˙’i. 2.3 Sˆo´ ˆo˙’n d¯i.nh trong . . . . . . V´oi d¯ˆo` thi. G = (V, Γ) cho tru´oc ta thu`ong quan tˆamd¯ˆe´n tˆa.p con cu˙’a V c´onh˜ung t´ınhchˆa´t . . n`aod¯´o.Chˇa˙’ng ha.n, t`ımmˆo.t tˆa.p con S ⊂ V c´osˆo´ phˆa`n tu˙’ l´on nhˆa´t sao cho d¯ˆo` thi. con sinh 55
55. . . bo˙’ i S l`ad¯ˆa`y d¯u˙’? Hoˇa.c t`ımtˆa.p con c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. G c´osˆo´ phˆa`n tu˙’ 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`n tu˙’ . ´ıtnhˆa´t sao cho mo.i d¯ı˙’nh thuˆo.c V \ S kˆe` v´oi mˆo.t d¯ı˙’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 . . trong cu˙’a d¯ˆo` thi. v`ac´onhiˆe` u ´ung du. ng tru. c tiˆe´p trong b`aito´anlˆa.p li.ch, phˆant´ıch cluster, . . phˆanloa.i sˆo´, xu˙’ l´ysong song trˆenm´ayt´ınh,vi. tr´ıthuˆa.n lo. i v`athay thˆe´ c´acth`anhphˆa`n . d¯iˆe.n tu˙’ , v.v. . . . . . . D- .inh ngh˜ıa2.3.1 X´etd¯ˆo` thi. vˆohu´ong G := (V, Γ); tˆa.p ho. p S ⊂ V d¯uo. c go.i l`a tˆa. p ho. p . ˆo˙’n d¯i.nh trong nˆe´u hai d¯ı˙’nh bˆa´t k`ycu˙’a S d¯ˆe` u khˆongkˆe` nhau; n´oic´ach kh´ac,v´oi mo.i cˇa.p d¯ı˙’nh a, b ∈ S th`ı b∈ / Γ(a). K´yhiˆe.u S l`aho. c´actˆa.p ˆo˙’n d¯i.nh trong cu˙’a d¯ˆo` thi. G. Khi d¯´o 1. Tˆa.p trˆo´ng ∅ thuˆo.c S. 2. Nˆe´u S ∈ S v`a A ⊂ S th`ı A ∈ S. N´oic´ach kh´ac,tˆa.p con cu˙’a mˆo.t tˆa.p ˆo˙’n d¯i.nh trong c˜ungl`amˆo.t tˆa.p ˆo˙’n d¯i.nh trong. . Tˆa.p ˆo˙’n d¯i.nh trong l`a cu. c d¯a. i nˆe´u thˆemmˆo.t d¯ı˙’nh bˆa´t k`yv`aon´oth`ıs˜ekhˆongc`onˆo˙’n d¯i.nh . . . trong n˜ua. D- a.i luo. ng α(G) := max{#S | S ∈ S} . . d¯uo. c go.i l`a sˆo´ ˆo˙’n d¯i.nh trong cu˙’a G. . V´ıdu. 2.3.2 X´etd¯ˆo` thi. trong H`ınh2.2. Tˆa.p c´acd¯ı˙’nh {v7, v8, v2} l`aˆo˙’n d¯i.nh trong nhung . . khˆongcu. c d¯a.i; tˆa.p {v7, v8, v2, v5} l`aˆo˙’n d¯i.nh trong cu. c d¯a.i. C´actˆa.p {v1, v3, v7} v`a {v4, v6} . c˜ungl`atˆa.p ˆo˙’n d¯i.nh trong cu. c d¯a.i v`ado d¯´o,n´oichung c´othˆe˙’ c´onhiˆe` u tˆa.p ˆo˙’n d¯i.nh trong . . cu. c d¯a.i. Ho. c´actˆa.p ˆo˙’n d¯i.nh trong cu. c d¯a.i cu˙’a d¯ˆo` thi. n`ayl`a {v7, v8, v2, v5}, {v1, v3, v7}, {v4, v6}, {v3, v6}, {v1, v5, v7}, {v1, v4}, {v3, v7, v8}. . 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´emd¯uo. c con n`aokhˆong?B`aito´annˆo˙’i tiˆe´ng n`ayd¯ua vˆe` t`ımmˆo.t . . . . . tˆa.p ho. p ˆo˙’n d¯i.nh trong cu. c d¯a.i cu˙’a d¯ˆo` thi. vˆohu´ong c´o64 d¯ı˙’nh (l`ac´acˆotrˆenb`anc`o), trong . . . d¯´o y ∈ Γ(x) nˆe´u c´acˆo x v`a y nˇa`m trˆenc`ungmˆo.t h`ang,mˆo.t cˆo.t hay mˆo.t d¯u`ong ch´eo.Thu. c . . . . . . . . tˆe´, kh´okhˇanla.i l´on hon l`akhi ngu`oi ta m´oi thoa.t nh`ın: l´ucd¯ˆa`u Gauss tuo˙’ ng c´o76 l`oi 56