Lí thuyết đồ thị part 1

Chia sẻ: ágffq ằefgsd | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

121
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong toán học và tin học, lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lí thuyết đồ thị part 1

Muc luc .. L`.i n´i d` u o o ¯ˆ a 7 1 Dai cu.o.ng vˆ d` thi -. ` ¯ˆ . eo 9 -. 1.1 Dinh ngh˜ v` c´c kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . ıa a a ae 9 . D` thi c´ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o 1.1.1 o 9 -ˆ . aa D` thi v` ´nh xa d a tri . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 o .¯ 10 . D` thi vˆ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o 1.1.3 o 10 1.1.4 C´c d inh ngh˜ ch´ . . . . . . . . . . . . . . . . . . . . . . . . . . . a ¯. ıa ınh 11 Ma trˆn biˆ’u diˆn d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ˜ ¯ˆ . 1.2 a e eo 13 . o ¯˙ ’ 1.2.1 Ma trˆn liˆn thuˆc d ınh-cung . . . . . . . . . . . . . . . . . . . . . . ae 13 . . o ¯˙ ’ 1.2.2 Ma trˆn liˆn thuˆc d ınh-canh . . . . . . . . . . . . . . . . . . . . . . ae 15 . . . a` o ¯˙ ¯˙ ’ ’ 1.2.3 Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ınh-d ınh . . . . . . . . . . . . . .e ae 17 . . C´c biˆ’u diˆn cua d` thi . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ˜ ˙ ¯o . ’ˆ 1.2.4 a e e 18 1.3 T´ liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ınh e o 23 ` 1.3.1 Dˆy chuyˆn v` chu tr` . . . . . . . . . . . . . . . . . . . . . . . . . a ea ınh 23 Du.`.ng d i v` mach . . . . . . . . . . . . . . . . . . . . . . . . . . . . -o 1.3.2 ¯a. 24 1.3.3 T´ liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ınh e o 24 1
` 1.3.4 Cˆu, k −liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . a e o 28 -ˆ . e D` thi liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5 o o 31 . 1.4 Pham vi v` liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . . ae o 33 . . 1.4.1 Ma trˆn pham vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 33 . . ` 1.4.2 T` c´c th`nh phˆn liˆn thˆng manh . . . . . . . . . . . . . . . . . . ım a a ae o 36 . Co. so. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ’ 1.4.3 39 -a ˙ ’ Dˇng cˆ u cua c´c d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˙ a ¯ˆ . ’ 1.5 a o 41 ˙ ’ ´ 1.5.1 1−d ˇng cˆ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¯a a 42 ˙ ’ ´ 1.5.2 2−d ˇng cˆ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¯a a 43 C´c d` thi d ac biˆt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 a ¯o . ¯ˇ ˆ e 46 . . -ˆ . o D` thi khˆng c´ mach . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.1 o o. 46 -ˆ . a ˙ ’ D` thi phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.2 o 46 2 C´c sˆ co. ban cua d` thi ´ ˙ ’ ˙ ¯ˆ . ’ ao o 49 ´ 2.1 Chu sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 49 ´´ 2.2 Sˇc sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ao 52 ´´ 2.2.1 C´ch t` sˇc sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a ım a o 54 Sˆ ˆ’n d .nh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´˙ 2.3 o o ¯i 55 Sˆ ˆ’n d .nh ngo`i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´˙ 2.4 o o ¯i a 61 ˙ ’ 2.5 Phu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Nhˆn cua d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a ˙ ¯ˆ . ’o 2.6 69 y`` . a ´ 2.6.1 C´c d inh l´ vˆ tˆn tai v` duy nhˆ t . . . . . . . . . . . . . . . . . . . a ¯. eo a 69 Tr` cho.i Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 o 72 2
3 C´c b`i to´n vˆ d .`.ng d a ` ¯u o aa e ¯i 75 Du.`.ng d i gi˜.a hai d ınh -o ¯˙’ 3.1 ¯u ............................. 75 Du.`.ng d i gi˜.a hai d ınh . . . . . . . . . . . . . . . . . . . . . . . . . -o ¯˙’ 3.1.1 ¯u 75 -ˆ . e D` thi liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 o o 76 . Du.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh . . . . . . . . . . . . . . . . . . . . . . . -o ´ ´u ¯˙’ 3.2 ¯ a a 78 Tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm . . . . . . . . . . . . . . 3.2.1 o a oa 78 . . . . Tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y . . . . . . . . . . . . . . . . . 3.2.2 o a y´ 82 . . . . Du.`.ng d i ngˇn nhˆ t gi˜.a tˆ t ca c´c cˇp d ınh . . . . . . . . . . . . . . . . . -o ´ ´ u a ˙ a a ¯˙ ´’ ’ 3.3 ¯ a a 87 . Thuˆt to´n Hedetniemi (tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm) 3.3.1 a a o a oa 88 . . . . . Thuˆt to´n Floyd (tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y) . . . . . . 3.3.2 a a o a y´ 93 . . . . . 3.4 Ph´t hiˆn mach c´ d ˆ d`i ˆm . . . . . . . . . . . . . . . . . . . . . . . . . . a e o ¯o a a 96 . . . Mach tˆi u.u trong d` thi c´ hai trong lu.o.ng . . . . . . . . . . . . . . ´ 3.4.1 o ¯ˆ . o o 96 . . . ˆ 4 CAY 99 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ¯ˆ ’a 4.1 99 4.2 Cˆy Huﬀman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 a ´ 4.2.1 C´c bˆ m˜ “tˆt” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 aoao. 4.2.2 M˜ Huﬀman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 a 4.3 Cˆy bao tr`m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 a u ´ `o 4.3.1 Thuˆt to´n t` kiˆm theo chiˆu rˆng x´c d .nh cˆy bao tr`m . . . . . 107 a a ım e e. a ¯i a u . ´ ` a a ¯. 4.3.2 Thuˆt to´n t` kiˆm theo chiˆu sˆu x´c d inh cˆy bao tr`m . . . . . 107 a a ım e e a u . T` cˆy bao tr`m du.a trˆn hai mang tuyˆn t´ ´ ˙ ’ 4.3.3 ım a u e e ınh . . . . . . . . . . . 108 . ´’ a ım a ˙ a a 4.3.4 Thuˆt to´n t` tˆ t ca c´c cˆy bao tr`m . . . . . . . . . . . . . . . . 112 a u . Hˆ co. so. cua c´c chu tr` d ˆc lˆp . . . . . . . . . . . . . . . . . . . 112 ˙˙a ’’ 4.3.5 e ınh ¯o a . .. 3
Cˆy bao tr`m tˆi thiˆ’u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 ˙ ´ 4.4 a u o e 4.4.1 Thuˆt to´n Kruskal a a . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 . 4.4.2 Thuˆt to´n Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 a a . 4.4.3 Thuˆt to´n Dijkstra-Kevin-Whitney a a . . . . . . . . . . . . . . . . . . 121 . 4.5 B`i to´n Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 aa 5 B`i to´n Euler v` b`i to´n Hamilton a a aa a 127 5.1 B`i to´n Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 aa ` 5.1.1 Thuˆt to´n t` dˆy chuyˆn Euler . . . . . . . . . . . . . . . . . . . . 129 a a ım a e . B`i to´n ngu.`.i d u.a thu. Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . 131 5.2 aa o¯ 5.3 B`i to´n Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 aa C´c d iˆu kiˆn cˆn dˆ’ tˆn tai chu tr` Hamilton . . . . . . . . . . . . 138 ˙o a ¯` e ` ¯e ` . 5.3.1 e .a ınh C´c d iˆu kiˆn d u vˆ su. tˆn tai chu tr` Hamilton a ¯` e ¯˙ ` . ` . ’e 5.3.2 e o ınh . . . . . . . . . . 139 . C´c d iˆu kiˆn d u vˆ su. tˆn tai mach Hamilton . . . . . . . . . . . . . 142 a ¯` e ¯˙ ` . ` . ’e 5.3.3 e o . . -ˆ . ˙ ’ 6 D` thi phˇ ng o a 149 -. 6.1 Dinh ngh˜ v` c´c v´ du . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 ıa a a ı . C´c biˆ’u diˆn kh´c nhau cua mˆt d` thi phˇng . . . . . . . . . . . . . . . . 151 ˙ ˜ ˙ ’ ˙ ’ 6.2 a e e a o ¯o . a .ˆ ˙ ’ C´c t´ chˆ t cua d` thi phˇng . . . . . . . . . . . . . . . . . . . . . . . . . 154 ´’o a ınh a ˙ ¯ˆ . a 6.3 ˙ ’ 6.4 Ph´t hiˆn t´ phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 a e ınh a . Kiˆ’m tra t´ phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 ˙ ˙ ’ 6.4.1 e ınh a -o ˜ ´ 6.5 Dˆi ngˆ u h` hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 a ınh . Dˆi ngˆ u tˆ’ ho.p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 -o ˙ ˜ ´ 6.6 ao. ˙ ’ 7 Mang vˆn ta i a 173 . . 4
Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 ˙ ¯ˆ ’a 7.1 B`i to´n luˆng l´.n nhˆ t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 ` ´ 7.2 aa o o a Thuˆt to´n g´n nh˜n dˆ’ t` luˆng l´.n nhˆ t . . . . . . . . . . . . . . 180 ˙ a ¯e ım ` ´ 7.2.1 a aa o o a . - ˆ . ¯` D` thi d iˆu chınh luˆng . . . . . . . . . . . . . . . . . . . . . . . . . . 181 ` ˙ ’ 7.2.2 o e o a ıch ` 7.2.3 Phˆn t´ luˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 o C´c cai biˆn d o.n gian cua b`i to´n luˆng l´.n nhˆ t . . . . . . . . . . . . . . . 183 ` ´ a˙ ’ e¯ ˙ ’ ˙aa ’ 7.3 o o a C´c d` thi c´ nhiˆu nguˆn v` nhiˆu d´ . . . . . . . . . . . . . . . . 183 ` `a ` ¯ıch 7.3.1 a ¯ˆ . o o e o e C´c d` thi v´.i r`ng buˆc tai c´c cung v` d ınh . . . . . . . . . . . . . 184 a ¯˙’ 7.3.2 a ¯ˆ . o a o o.a . C´c d` thi c´ cˆn trˆn v` cˆn du.´.i vˆ luˆng . . . . . . . . . . . . . . 185 o`` 7.3.3 a ¯ˆ . o a o e aa eo . . Luˆng v´.i chi ph´ nho nhˆ t . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 ` ´ ˙ ’a 7.4 o o ı 7.4.1 Thuˆt to´n Klein, Busacker, Gowen . . . . . . . . . . . . . . . . . . . 186 a a . 7.5 Cˇp gh´p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 a e . a a a `a 7.5.1 C´c b`i to´n vˆ cˇp gh´p . . . . . . . . . . . . . . . . . . . . . . . . 189 e. e Cˇp gh´p l´.n nhˆ t trong d` thi hai phˆn . . . . . . . . . . . . . . . . 192 ´ ` 7.5.2 a eo a ¯ˆ . o a . Cˇp gh´p ho`n hao trong d` thi hai phˆn . . . . . . . . . . . . . . . 193 ` ˙ ’ 7.5.3 a e a ¯ˆ . o a . A Thu. viˆn Graph.h e 197 . ˙ ’ T`i liˆu tham kha o ae 209 . 5
6
L`.i n´i d` u o o ¯ˆ a Trong thu.c tˆ dˆ’ miˆu ta mˆt sˆ t` huˆng ngu.`.i ta thu.`.ng biˆ’u thi bˇ ng mˆt h` anh ´˙ ˙ .` ’.´ ´ . e ¯e e ˙ o o ınh o o ınh ˙ ’ o o e a . ˙m (c´c d ınh)-biˆ’u diˆn c´c thu.c thˆ’-v` v˜ c´c d oan thˇng nˆi cˇp c´c d ınh biˆ’u ’ ˙ ˙ a ea ¯. ˙ ˜a ˙’ ` ´. a ¯˙ ’ o a a ¯˙ ’ gˆm c´c d iˆ o a ¯e e e e a e . .a ch´ng. Nh˜.ng h` nhu. thˆ thu.`.ng goi l` c´c d` thi. Muc d´ cua ˜ ´ ´ . ¯ıch ˙ ’ diˆn mˆi quan hˆ gi˜ e o eu u u ınh e o . a a ¯o . ˆ . .ng kiˆn th´.c co. ban dˆ’ nghiˆn c´.u c´c d` thi. C´c d` thi xuˆ t ˙ ´ ´ ´ ˙ ¯e ’ gi´o tr` n`y cung cˆ p nh˜ a ınh a a u e u e u a ¯o . a ¯ˆ . a ˆ o ` u l˜ vu.c v´.i c´c tˆn goi kh´c nhau: “cˆ u tr´c” trong cˆng tr` xˆy du.ng, ´ hiˆn trong nhiˆ ınh . o a e . e e a a u o ınh a . . “mach” trong d iˆn tu., “lu.o.c d` quan hˆ”, “cˆ u tr´c truyˆn thˆng”, “cˆ u tr´c tˆ’ ch´.c” ˙ ´ ` ´ ˙ ’ ¯e ¯o ˆ e a u e o a uou . . . . trong x˜ hˆi v` kinh tˆ, “cˆ u tr´c phˆn tu.” trong ho´ hoc, vˆn vˆn. ´a ´ a˙ ’ aoa e u a. aa . Do nh˜.ng u.ng dung rˆng r˜i cua n´ trong nhiˆu l˜ vu.c, c´ rˆ t nhiˆu nghiˆn c´.u ` ınh . ´ ` a˙ ’o u ´ o e oa e eu . . .ng nˇm gˆn d ay; mˆt nhˆn tˆ chu yˆu g´p phˆn th´c xung quanh l´ thuyˆt d` thi trong nh˜ ´ˆ a ` ¯ˆ ´ ’´ ` a o ˙e o y e ¯o . u a o a u . ˙y su. ph´t triˆ’n d o l` xuˆ t hiˆn c´c m´y t´ l´.n c´ thˆ’ thu.c hiˆn nhiˆu ph´p to´n v´.i ’. ˙ ¯´ a a ˙. ´ea ` da ¯ˆ a e a ınh o o e e e e ao . . tˆc d o rˆ t nhanh. Viˆc biˆ’u diˆn tru.c tiˆp v` chi tiˆt c´c hˆ thˆng thu.c tˆ, chˇng han c´c ˙ ˜ ˙ ’ ´ .´ ´ ´ ´ ´a o ¯ˆ a e e e ea eaeo e .a . . . . .a dˆn nh˜.ng d` thi c´ k´ thu.´.c l´.n v` viˆc phˆn t´ th`nh ` ´ mang truyˆn thˆng, d ˜ d u ¯e e o ¯a ¯ u ¯ˆ . o ıch o oo ae a ıch a . . ´ng phu thuˆc rˆ t nhiˆu v`o c´c thuˆt to´n “tˆt” c˜ng nhu. kha nˇng cua m´y ´ ` ´ ˙a ’ ˙ ’ cˆng hˆ thˆ o eo oa eaa a a o u a . . . . ınh. Theo d o, gi´o tr` n`y s˜ tˆp trung v`o viˆc ph´t triˆ’n v` tr` b`y c´c thuˆt to´n ˙ t´ ¯´ a ınh a e a a e a e a ınh a a a a . . . dˆ’ phˆn t´ c´c d` thi. ˙ ¯e a ıch a ¯o . ˆ C´c phu.o.ng ph´p phˆn t´ v` thiˆt kˆ c´c thuˆt to´n trong gi´o tr` cho ph´p sinh ´´ a a a ıch a e ea a a a ınh e . .o.ng tr` minh hoa. Gi´o tr` d u.o.c biˆn soan cho c´c d oi viˆn c´ thˆ’ viˆt dˆ d`ng c´c chu ˙´e e o e e ˜a ´ a ınh a ınh ¯ . e a ¯ˆ . . .o.ng l` sinh viˆn To´n-Tin v` Tin hoc. tu . a e a a . Gi´o tr` su. dung ngˆn ng˜. C dˆ’ minh hoa, tuy nhiˆn c´ thˆ’ dˆ d`ng chuyˆ’n d ˆ’i ˙ ˙e ˙ ˙ e o e˜a ınh ˙ . ’ a o u ¯e e ¯o . . kh´c; v` do d ´, sinh viˆn cˆn c´ mˆt sˆ kiˆn th´.c vˆ ngˆn ng˜. C. Ngo`i e` oooe .´´ u`o sang c´c ngˆn ng˜ a a o u a ¯o a e u a ra, hˆu hˆt c´c chu.o.ng tr` thao t´c trˆn cˆ u tr´c d˜. liˆu nhu. danh s´ch liˆn kˆt, nˆn d `i ` ´ ´ ´ e ¯o aea ınh a ea u ue a ee . hoi sinh viˆn phai c´ nh˜.ng k˜ nˇng lˆp tr` tˆt. ´ ˙ ’ ˙ou ’ e ya a ınh o . Gi´o tr` bao gˆm bay chu.o.ng v` mˆt phˆn phu luc v´.i nh˜.ng nˆi dung ch´ nhu. ` ` ˙ ’ a ınh o ao a .. o u o ınh . . sau: • Chu.o.ng th´. nhˆ t tr` b`y nh˜.ng kh´i niˆm cˇn ban vˆ d` thi. ´ ınh a ˙ ` ¯o . ’ eˆ ua u ae a . • Chu.o.ng 2 tr` b`y nh˜.ng sˆ co. ban cua d` thi. Y ngh˜ thu.c tiˆn cua c´c sˆ n`y. ˙ ¯ˆ . ´ ˜ ˙ aoa ´ ´ ˙ ’ ’o ’ ınh a u o ıa . e 7
• Chu.o.ng 3 t` hiˆ’u b`i to´n t` d u.`.ng d i ngˇn nhˆ t. ˙ ´ ´ ım e a a ım ¯ o ¯ a a ` a ´. • Chu.o.ng 4 d` cˆp dˆn kh´i niˆm vˆ cˆy. U ng dung cua cˆy Huﬀman trong n´n d˜. ´ ˙a ’ ¯ˆ a ¯e e. ae e eu . . liˆu. Ngo`i ra xˆy du.ng c´c thuˆt to´n t` cˆy bao tr`m nho nhˆ t. ´ ˙ ’a e a a a a a ım a u . . . • B`i to´n Euler v` b`i to´n Hamilton v` nh˜.ng mo. rˆng cua ch´ng s˜ d u.o.c n´i dˆn ´ ˙o ’. ˙ ’ a a aa a au u e ¯ . o ¯e .o.ng 5. trong Chu • Chu.o.ng 6 nghiˆn c´.u c´c t´ chˆ t phˇng cua d` thi; v` cuˆi c`ng ˙ ’ ´ ´ ˙ ¯ˆ . a o u ’o e u a ınh a a • Chu.o.ng 7 t` hiˆ’u c´c b`i to´n trˆn mang vˆn tai. ˙ a˙ ’ ım e a a a e . . Ngo`i ra, phˆn phu luc tr` b`y c´c cˆ u tr´c d˜. liˆu v` nh˜.ng thu tuc cˆn thiˆt dˆ’ ´˙ ` ´ ˙.` ’ a a ınh a a a u ue a u a e ¯e .. . .n gian ho´ c´c d oan chu.o.ng tr` minh hoa c´c thuˆt to´n d u.o.c tr` b`y. ˙ ’ do ¯ aa ¯. ınh .a a a¯. ınh a . Gi´o tr` d u.o.c biˆn soan lˆn d` u tiˆn nˆn khˆng tr´nh khoi kh´ nhiˆu thiˆu s´t. T´c . ` ¯a e e a` ´ ˙ ’ a ınh ¯ . e aˆ o a e eo a .ng d ´ng g´p t`. ban d oc. ˙ ’ gia mong c´ nh˜ ou ¯o o u . ¯. Tˆi xin cam o.n nh˜.ng gi´p d o. d a nhˆn d u.o.c t`. nhiˆu ngu.`.i m` khˆng thˆ’ liˆt kˆ ˙. ` ˙ ’ o u u ¯˜ ¯˜ a ¯ . u e o ao ee e . ´ hˆt, d ˇc biˆt l` c´c ban sinh viˆn, trong qu´ tr` biˆn soan gi´o tr` n`y. e ¯a eaa . e a ınh e a ınh a . . . -a . D` Lat, ng`y 5 th´ng 3 nˇm 2002 a a a PHAM Tiˆn So.n ´ e . 8
Chu.o.ng 1 Dai cu.o.ng vˆ d` thi -. ` ¯ˆ . eo -. 1.1 Dinh ngh˜ v` c´c kh´i niˆm ıa a a a e . D` thi c´ hu.´.ng -ˆ . o 1.1.1 o o D` thi c´ hu.´.ng G = (V, E ) gˆm mˆt tˆp V c´c phˆn tu. goi l` d ınh (hay n´t) v` mˆt tˆp -ˆ . o o ` ` a ˙ . a ¯˙ ’ ’ o o oa a u aoa .. .. .o.ng u.ng v´.i mˆt cˇp c´c d ınh d u.o.c sˇp th´. tu.. Nˆu ˜ ´ ´ o o a a ¯˙ ¯ . a ’ E c´c cung sao cho mˆ i cung e ∈ E tu a o ´ u. e .. .o.ng u.ng c´c d ınh d u.o.c sˇp th´. tu. (a, b), ta s˜ viˆt e := (a, b). ´ ´ ˙ ¯. a ’ c´ d ung mˆt cung e tu o ¯´ o ´ a¯ u. ee . Ch´ng ta s˜ gia su. c´c d ınh d u.o.c d anh sˆ l` v1 , v2 , . . . , vn hay gian tiˆn, 1, 2, . . . , n, ´ e ˙ ˙ a ¯˙ ’’ ’ ˙ ’ u ¯ . ¯´ oa e . trong d o n = #V l` sˆ c´c d ınh cua d` thi. ´ a o a ¯˙ ’ ˙ ¯ˆ . ’o ¯´ Nˆu e l` mˆt cung tu.o.ng u.ng cˇp c´c d ınh d u.o.c sˇp th´. tu. vi v` vj th` d ınh vi goi l` ´ ´ a a ¯˙ ¯ . a ’ ı ¯˙’ e ao ´ u. a .a . . .`.ng ´ o a ¯˙ ’ ¯˙ ’ gˆc v` d ınh vj goi l` ngon; cung e goi l` liˆn thuˆc hai d ınh vi v` vj . Ch´ng ta s˜ thu o .a . .ae o a u e . ´ canh cua d` thi G. C´c canh thu.`.ng d u.o.c d ´nh sˆ l` e1 , e2 , . . . , em . ´a ˙ ¯ˆ . ’o k´ hiˆu m = #E −sˆ . ye o a. o ¯ . ¯a o . Mˆt c´ch h` hoc, c´c d ınh d u.o.c biˆ’u diˆn bo.i c´c d iˆ’m, v` e = (vi , vj ) d u.o.c biˆ’u ˙ ˙ ˙ ˜ a ¯˙ ’ ¯. ˙ a ¯e ’ oa ınh . e e a ¯. e . .i mˆt cung nˆi c´c d iˆ’m v v` v . ˙ ˜ ´ ˙ ’ diˆn bo e o o a ¯e iaj . Mˆt cung c´ gˆc tr`ng v´.i ngon goi l` khuyˆn. ´u o oo o .a e . . Nˆu c´ nhiˆu ho.n mˆt cung v´.i gˆc tai vi v` ngon tai vj th` G goi l` d a d` thi v` c´c ´ ` ´ eo e o oo. a.. ı . a ¯ ¯o . a a ˆ . .o.ng u.ng goi l` song song. Do.n d` thi c´ hu.´.ng l` d` thi khˆng khuyˆn trong d o hai - cung tu ´ .a ¯o . o o ˆ a ¯o . o ˆ e ¯´ ˙ ’ d ınh bˆ t k` vi v` vj c´ nhiˆu nhˆ t mˆt cung (vi , vj ). Chˇng han, d` thi trong H` 1.1 c´ ´ ` ´o ¯˙’ ay a o e a a ¯o . ˆ ınh o . . .o.ng u.ng cˇp d ınh v v` v . a ¯˙’ cung e8 l` khuyˆn; c´c cung e4 v` e9 l` song song do c`ng tu a e a a a u ´ 3a4 . 9
e4 .. . v2 e3 v3 ................................................. ........................................ .. ............ ......... ....... ...... ..... ..... .... .... •v4 ... ... • • .. . . ............................................................................... ............................................................................. . . .. . . . ... ... . ... . . .. .. . .... ..... . ...... .. .. . ...... ......... ................................................. .. . .......................... . ............. . . . . . . . . ............... .. . . . .. . . . . e9 . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . .. . . . . . . . . . . .. . . . . . . . . .. . . .. . . . . . . . . .. . . . .. . . . . . . .. . . . .. . . . . . . .. . . . .. . . . . . . . .. . . .... . e1 e2 e6 e7 .. ... . . ... . ... . . . .. . .. . . . . . . .... . .. ... . . .. . . . . . . . . . . . ... ... . . . . . . . . .. . . .... . . . ... . . . . . .. . .. . ... . . ... . . . . . . . ... ... . . . . . . .. . . .. . . . ... . ... . . . . . ... . . ... . . . . . . ... ... . . . . . . ... ... . . . . . . ... . ... . . . . . .. . ... . . . .... . . . .... . . . . .... . . .... . . . . e5 . . .... . . .... . . . . . . .. . .. . . . . ....... . . ......... .. .. .. . • • v5 . ... ............................................................................. . ............................................................................. .. . .. .. .. v1 .. .. . . . . . .. . . . . . . . . .. . ... ... . . . . . . . .. . .. .. ...... ..... e8 H` 1.1: V´ du cua 2−d` thi c´ hu.´.ng. ı.˙ ’ ınh ¯ˆ . o o o -ˆ . aa D` thi v` ´nh xa d tri 1.1.2 o . ¯a . V´.i mˆi x ∈ V, k´ hiˆu Γ(x) := {y ∈ V | (x, y ) ∈ E }. Khi d ´ ta c´ mˆt ´nh xa d a tri ˜ o o ye ¯o o oa .¯ . . . Γ: V → 2V , x → Γ(x). K´ hiˆu Γ−1 l` ´nh xa (d a tri) ngu.o.c cua Γ. ˙ ’ ye aa ¯ . . . . Nˆu G l` d o.n d` thi, th` d` thi n`y ho`n to`n d u.o.c x´c d .nh bo.i tˆp V v` ´nh xa d a ´ ˙a ’. e a¯ ¯ˆ . o ı ¯ˆ . a o a a ¯ . a ¯i aa .¯ . V v`o 2V . V` vˆy, d` thi n`y c`n c´ thˆ’ k´ hiˆu l` G = (V, Γ). ˙y e a tri Γ t` u a ı a ¯o . a o o e ˆ . . . Nˆu xo´ cung e9 trong H` 1.1 ta nhˆn d u.o.c d o.n d` thi v` do d o c´ thˆ’ biˆ’u diˆn ˙˙ ˜ ´ e a ınh a ¯. ¯ ¯o . a ˆ ¯´ o e e e . .i ´nh xa d a tri Γ. Trong tru.`.ng ho.p n`y ta c´ ˙ ’ bo a .¯ o a o . . Γ(v1 ) = {v2 }, Γ(v2 ) = {v1 , v3 }, Γ(v3 ) = {v4 , v5 }, Γ(v4 ) = {v5 }, Γ(v5 ) = {v1 , v5 }. D` thi vˆ hu.´.ng -ˆ . o 1.1.3 o o Khi nghiˆn c´.u mˆt sˆ t´ chˆ t cua c´c d` thi, ta thˆ y rˇ ng ch´ng khˆng phu thuˆc v`o a` .´ ´’ ´a o o ınh a ˙ a ¯o . eu ˆ u o oa . . .´.ng cua c´c cung, t´.c l` khˆng cˆn phˆn biˆt su. kh´c nhau gi˜.a c´c d iˆ’m bˇt d` u v` ˙ ´ˆ ` ˙a ’ hu o uao a a e. a u a ¯e a ¯a a . kˆt th´c. Diˆu n`y d o.n gian l` mˆi khi c´ ´ nhˆ t mˆt cung gi˜.a hai d ınh ta khˆng quan u -` ˜ ´ ´o ˙ao ’ ¯˙’ e e a¯ o ıt a u o . ´n th´. tu. cua ch´ng. ˙ ’ tˆm dˆ a ¯e u. u V´.i mˆ i cung, t´.c l` mˆ i cˇp c´ th´. tu. (vi , vj ) ta cho tu.o.ng u.ng cˇp khˆng c´ th´. ˜ ˜. o o uaoa o u. ´ a o ou . . (v , v ) goi l` c´c canh. Tu.o.ng d u.o.ng, ta n´i rˇ ng canh l` mˆt cung m` hu.´.ng d a bi bo ` ¯˜ . ˙ ’ tu i j . a a . ¯ oa ao ao . . . quˆn. Vˆ h` hoc, canh (vi , vj ) d u.o.c biˆ’u diˆn bo.i c´c d oan thˇng (hoˇc cong) v` khˆng ˙ ˜ ˙ ’ ` ınh . ˙ a ¯. ’ e e ¯. e e a a ao . . c´ m˜i tˆn liˆn thuˆc hai d iˆ’m tu.o.ng u.ng hai d ınh vi v` vj . ˙ ¯˙ ’ oue e o ¯e ´ a . 10
Nghiˆn c´.u c´c t´ chˆ t vˆ hu.´.ng cua d` thi G = (V, E ) d u.a vˆ khao s´t tˆp E l` ´ ` ˙ ¯o . ’ˆ ˙aa ’ e u a ınh a o o ¯ e a . .c l`, mˆt tˆp h˜.u han c´c phˆn tu. m` mˆ i phˆn tu. l` mˆt cˇp hai d ınh ˜ ` ` a˙ao ’ a ˙a o a ’ ¯˙ ’ tˆp c´c canh, t´ a o a u aa. u a . .. . .. phˆn biˆt hay d` ng nhˆ t cua V. ´’ a˙ a e ¯ˆ o . Da d` thi vˆ hu.´.ng l` d` thi m` c´ thˆ’ c´ nhiˆu ho.n mˆt canh liˆn thuˆc hai d ınh. - ¯o . o o ˙ ` ¯˙’ ˆ a ¯o . a o e o ˆ e o. e o . . D` thi goi l` d o.n nˆu n´ khˆng c´ khuyˆn v` hai d ınh bˆ t k` c´ nhiˆu nhˆ t mˆt canh -ˆ . . a¯ ´ a yo ` ´ ´o. ¯˙’ o eoo o ea e a . liˆn thuˆc ch´ng. e o u . e4 v...2..............................................................e...3.....................................................v...3......................................................................................................................................................... .. v ..•.. .. . • .• 4 . .. . .. . .. . .. . .. . .. . . . . ........ . .... ..... . .. ..... . . ..................... . ....... .. . ......... ................................................ .. . . . . .................................. . . . . . . . . . . . e9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . .. . . . .. . . . . . . . . . .. . . . . . . . .. . . . .. . . . . . . . .. . . . .. . . . . . . .. . . . .. . . . e1 e2 e6 e7 . . . .. . . .. . . . . . . . . . . .. . . . .. . . . . . . . .. . ... . . . . . ... . . . . ... . . . .. . . . . ... . . ... . . . . . . . . . . . ... . ... . . . . . . ... . . ... . . . . . . . ... ... . . . . . . ... ... . . . . . . ... . ... . . . . . . .. . . . . ... ... . . . . . . .... . ... . . . . . . .. . . .... . . . . . .... . . . .... . . .. . e5 .... . .... . . . . . . .... . .... . . . . .. ... . .... .... . .. .. • • v5 . ................................................................................ ............................................................................... . . .. ... . .. v1 . . . . . . . . . . . .. . . . . . . . . . . . . . . . ... .. .. .. ...... .... e8 H` 1.2: D` thi vˆ hu.´.ng tu.o.ng u.ng d` thi trong H` 1.1. -ˆ . o o ınh o ´ ¯ˆ . o ınh 1.1.4 C´c d .nh ngh˜ ch´ a ¯i ıa ınh ˙ ’ . a` ´ ´ o ¯˙.’ Hai cung, hoˇc hai canh goi l` kˆ nhau nˆu ch´ng c´ ´ nhˆ t mˆt d ınh chung. Chˇng han, a e e u o ıt a a . . . a` a` e`. ´o ¯˙’ hai canh e1 v` e3 trong H` 1.2 l` kˆ nhau. Hai d ınh vi v` vj goi l` kˆ nhau nˆu tˆn tai a ınh e a e . . a` ¯˙ ’ canh hoˇc cung ek liˆn thuˆc ch´ng. V´ du trong H` 1.2 hai d ınh v2 v` v3 l` kˆ nhau (liˆn a e o u ı. ınh a e e . . . ˙.i canh e3 ), nhu.ng d ınh v2 v` v5 khˆng kˆ nhau. ` ’. ˙ ’ thuˆc bo o ¯ a o e . Bˆc v` nu.a bˆc aa˙ ’ a . . Bˆc ngo`i cua d ınh v ∈ V, k´ hiˆu d+ (v ) (hay d+ (v ) nˆu khˆng so. nhˆm lˆ n) l` sˆ c´c cung ˜ ´ .` ´ a ˙ ¯˙ ’’ a yeG e o aa aoa . . ´c. Bˆc trong cua d ınh v ∈ V, k´ hiˆu d− (v ) (hay d− (v ) nˆu khˆng so. nhˆm ´ .` o ¯˙ ’ ˙ ¯˙ ’ ’ c´ d ınh v l` gˆ ao a yeG e o a . . ˜ ´ o ¯˙ ’ lˆ n) l` sˆ c´c cung c´ d ınh v l` ngon. a aoa a. Chˇng han, d` thi c´ hu.´.ng trong H` 1.1 c´ d+ (v2 ) = 2, d− (v2 ) = 1. ˙ ’ a . ¯ˆ . o o o ınh o 11
Hiˆ’n nhiˆn rˇ ng, tˆ’ng c´c bˆc ngo`i cua c´c d ınh bˇ ng tˆ’ng c´c bˆc trong cua c´c ˙ ˙ ˙ ` ` a ˙ a ¯˙ ’ ’ ˙a ’ e ea o aa a o aa . . .c l` d ınh v` bˇ ng tˆ’ng sˆ cung cua d` thi G, t´ a ˙ a` ´ ¯˙’ ˙ ¯o . ’ˆ a o o u n n d+ (vi ) = d− (vi ) = m. i=1 i=1 Nˆu G l` d` thi vˆ hu.´.ng, bˆc cua d ınh v ∈ V, k´ hiˆu dG (v ) (hay d(v ) nˆu khˆng so. ´ ´ ˙ ¯˙ ’’ e a ¯ˆ . o o o a ye e o . . . ` m lˆ n) l` sˆ c´c canh liˆn thuˆc d ınh v v´.i khuyˆn d u.o.c dˆm hai lˆn. V´ du d` thi vˆ ˜ ´a . ´ ` ˙ ’ nhˆ a a ao e o¯ o e ¯ . ¯e a ı . ¯ˆ . o o . hu.´.ng trong H` 1.2 c´ d(v2 ) = 3, d(v5 ) = 5. o ınh o ´ C´c cung (canh) liˆn thuˆc tˆp A ⊂ V. C´c d oi chu tr` a e oa a ¯ˆ ınh . . . Gia su. A ⊂ V. K´ hiˆu ω + (A) l` tˆp tˆ t ca c´c cung c´ d ınh gˆc thuˆc A v` d ınh ngon ´’ ´ ˙˙ ’’ aa a ˙a o ¯˙ ’ a ¯˙ ’ ye o o . . . . .´’ ´ c − aa a ˙a o ¯˙’ a ¯˙’ thuˆc A := V \ A, v` ω (A) l` tˆp tˆ t ca c´c cung c´ d ınh ngon thuˆc A v` d ınh gˆc thuˆc o a o o o . . . . -a Ac . Dˇt . ω (A) = ω + (A) ∪ ω − (A). Tˆp c´c cung hoˇc canh c´ dang ω (A) goi l` d ˆi chu tr` cua d` thi. ´ ınh ˙ ¯o . ’ˆ aa a. o. . a ¯o . . -ˆ . o . D` thi c´ trong sˆ ´ o o D` thi c´ trong sˆ nˆu trˆn mˆ i cung (hoˇc canh) e ∈ E c´ tu.o.ng u.ng mˆt sˆ thu.c w(e) goi -ˆ . o . ˜ ´´ .´ o oe e o a. o ´ oo . . . .o.ng cua cung e. ˙ ’ l` trong lu . a. D` thi d oi x´.ng - ˆ . ¯ˆ u ´ o D` thi c´ hu.´.ng goi l` d ˆi x´.ng nˆu c´ bao nhiˆu cung dang (vi , vj ) th` c˜ng c´ bˆ y nhiˆu -ˆ . o o ´ ´ ´ o . a ¯o u eo e ıu oa e . cung dang (vj , vi ). . D` thi phan d oi x´.ng -ˆ . ´ ˙ ¯ˆ u ’ o D` thi c´ hu.´.ng goi l` phan d ˆi x´.ng nˆu c´ cung dang (vi , vj ) th` khˆng c´ cung dang -ˆ . o ´ ´ ˙ ¯o u ’ o o .a eo ıo o . . (vj , vi ). 12
- ˆ . ¯ˆ ¯u D` thi d` y d ˙ ’ o a D` thi vˆ hu.´.ng goi l` d` y d u nˆu hai d ınh bˆ t k` vi v` vj tˆn tai mˆt canh dang (vi , vj ). -ˆ . o o ’´ ´ `. . a ¯ˆ ¯ ˙ e ¯˙’ o a ay a o o. . . .n d` thi vˆ hu.´.ng d` y d u n d ınh d u.o.c k´ hiˆu l` K . - ¯ˆ ¯ ˙ ¯˙ ¯ . y e a n ’ ’ Do ¯o . o o ˆ a . -ˆ . D` thi con o Gia su. A ⊂ V. D` thi con d u.o.c sinh bo.i tˆp A l` d` thi GA := (A, EA ) trong d ´ c´c d ınh l` -ˆ . ˙˙ ’’ ˙a ’. ¯o a ¯ ˙ ’ o ¯. a ¯ˆ . o a . cua tˆp A v` c´c cung trong E l` c´c cung cua G m` hai d ınh n´ liˆn thuˆc ` c´c phˆn tu ˙ a a˙’.’ ˙ ’ ¯˙ ’ a aa aa a oe o. A thuˆc tˆp A. oa .. Nˆu G l` d` thi biˆ’u diˆn ban d` giao thˆng cua nu.´.c Viˆt Nam th` d` thi biˆ’u diˆn ˙ ˙ ˜ ˜ ´ ˙ ¯ˆ ’ ˙ ’ e a ¯o . e ˆ e o o o e ı ¯o . e ˆ e . o - a . a o ¯o . ban d` giao thˆng cua th`nh phˆ D` Lat l` mˆt d` thi con. ´ ˙ ¯ˆ ’ ˙ ’ o o a ˆ . -ˆ . o D` thi bˆ phˆn o a . . X´t d` thi G = (V, E ) v` U ⊂ E. D` thi bˆ phˆn sinh bo.i tˆp U l` d` thi v´.i tˆp d ınh V -ˆ . o a ˙a ’. a ¯ˆ . o a ¯˙ ’ e ¯ˆ . o a o o . . . ˙ ’ ˙’ v` c´c cung thuˆc U (c´c cung cua E \ U bi xo´ khoi G). aa o a a . . -ˆ . D` thi con bˆ phˆn o o a . . X´t d` thi G = (V, E ) v` A ⊂ V, U ⊂ E. D` thi con bˆ phˆn sinh bo.i tˆp A v` U l` d` thi -ˆ . ˙a ’. e ¯o . ˆ a o oa a a ¯o . ˆ . . ˙ a GA sinh bo.i U. ’ ˙’ bˆ phˆn cu oa . . Ma trˆn biˆ’u diˆn d` thi ˙ ˜ ¯ˆ . 1.2 a e e o . Ma trˆn liˆn thuˆc d ˙nh-cung ’ 1.2.1 a e o ¯ı . . Ma trˆn liˆn thuˆc d ınh-cung cua d` thi G = (V, E ) l` ma trˆn A = (aij ), i = 1, 2, . . . , n, j = o ¯˙ .’ ˙ ¯o . ’ˆ ae a a . . .i c´c phˆn tu. 0, 1 v` −1, trong d o mˆi cˆt biˆ’u diˆn mˆt cung cua G v` mˆi ˙ ˜o ˜ ˜ ` ˙’ ˙ ’ 1, 2, . . . , m, v´ a o a a ¯´ o . e e o ao . . cua cˆt k bˇ ng h`ng biˆ’u diˆn mˆt d ınh cua G. Nˆu ek = (vi , vj ) ∈ E th` tˆ t ca c´c phˆn tu ˙ o ˙ ˜ ` ´ ´’ ` ˙’. o ¯˙ .’ ˙’ ıa ˙a a’ a e e e a . khˆng ngoai tr` o .u aik = 1, ajk = −1. 13
V´ du 1.2.1 Ma trˆn liˆn thuˆc d ınh-cung cua d` thi trong H` 1.3 l` o ¯˙ ’ ˙ ¯o . ’ˆ ı. ae ınh a . . e1 e2 e3 e4 e5   a +1 +1 0 0 0 b  −1 0 0 +1 +1   .  c  0 −1 −1 0 +1  d 0 0 0 −1 −1 a...........................................................................e...1...........................................................................b •.................. ...• ... . . . ... . ... . . ... . . ... . ... . . ... ... . ... ... . ... ... . ... ... . .. . . e4..................... ... ... ... ... . . ... . ... . . ... ... . . ... ... . . .. . . . ... . ... ... ... . . ... ... ... . ... . ... ... ... . ... . ... . ... ... ... . ... ... ...... ...... ... ...... .... . e3 . . . .. . ...... ....... . .. . . ... . ... ... . ... .. . . ... . ... ... ... . . .... . ... ... ... . .... .... . ..... ...... . . . . ... . ... ... ... . . .. ... . e2 ... . ... ... . ... ... . .. . . ... ... ... . ... . .. ... . . ... ... . ... . ... ... . .. . . ... ... ... ... ... . . .. ... . ... . ... ... ... . . .. ... .. • • ................................................................................. .. ................................................................................. . .. . .. .. ... .. e5 c d H` 1.3: ınh Nhˇc lai rˇ ng, ma trˆn vuˆng goi l` unimodular nˆu d inh th´.c cua n´ bˇ ng 1 hoˇc a.` ´ ` ´ u˙ ’ oa a a o .a e ¯. a . . ´ ´´’ e a ˙a −1. Ma trˆn A cˆ p m × n goi l` total unimodular nˆu tˆ t ca c´c ma trˆn vuˆng con khˆng a a a a o o . . . ´˙ ’ suy biˆn cua A l` unimodular. e a Mˆnh d` 1.2.2 Ma trˆn liˆn thuˆc d ı’nh-cung cu a d` thi G = (V, E ) l` total unimodular. o ¯˙ ˙ ¯ˆ . ’o e ¯ˆ e ae a . . . Ch´.ng minh. Ch´ y rˇ ng ma trˆn liˆn thuˆc d ınh-cung cua d` thi G = (V, E ) ch´.a d ung ` o ¯˙ ’ ˙ ¯o . ’ˆ u u´ a ae u ¯´ . . . kh´c khˆng trˆn mˆ i cˆt, mˆt bˇ ng 1 v` mˆt bˇ ng −1. Do d ´ ta c´ thˆ’ ch´.ng ˙ ˜. o` ao` `a˙ ’ hai phˆn tu a o e oo a a ¯o oeu . . . sau: Hiˆ’n nhiˆn, tˆ t ca c´c ma trˆn vuˆng con khˆng suy biˆn cˆ p 1 ˙ ´’ ´´ e a ˙a minh theo quy nap nhu e a o o ea . . ˙ a A l` modular; gia su. khˇng d .nh d ung cho moi ma trˆn con khˆng suy biˆn cˆ p (k − 1). ˙ ’ ´a ´ ’ ˙˙ ’ ’ a ¯i ¯ ´ cu a a o e . . X´t ma trˆn vuˆng con A cˆ p k cua A. Nˆu mˆ i cˆt cua A ch´.a d ung hai phˆn tu. ˜. ´ ´ ` ˙ ’ oo˙ ’ a˙ ’ e a o a e u ¯´ . ˙ng tˆ t ca c´c h`ng cua A l` vector khˆng, do d ´ c´c ’ ´’ a ˙a a ˙ ’ kh´c khˆng th` det(A ) = 0 (thˆt vˆy, tˆ a o ı aao a o ¯o a .. ´u tˆn tai mˆt cˆt cua A khˆng c´ phˆn tu. kh´c khˆng th` ´n t´ `. ` ˙ ’ ˙ ’ h`ng l` d ˆc lˆp tuyˆ ınh). Nˆ o a a ¯o a e e oo o oa a o ı .. .. det(A ) = 0. Cuˆi c`ng, nˆu tˆn tai cˆt j cua A sao cho c´ d ung mˆt phˆn tu. kh´c khˆng ´ e`.o ´o ` ˙ ’ a˙ ’ ou o ¯´ o a o . . ` ´ aij (bˇ ng 1, hay −1) th` det(A ) = ± det(A ), trong d o A l` ma trˆn vuˆng cˆ p (k − 1) a ı ¯´ a a o a . .o.c t`. A bˇ ng c´ch xo´ h`ng i v` cˆt j. Theo gia thiˆt quy nap, det(A ) bˇ ng 1, −1 ` ` ´ ˙’ nhˆn d u . u a¯ a a aa ao e a . . . .o.c ch´.ng minh. hay 0 v` do d ´ mˆnh d` d u . a ¯o e ¯ˆ ¯ e u . 14
Ma trˆn liˆn thuˆc d ˙nh-canh ’ 1.2.2 a e o ¯ı . . . X´t d` thi vˆ hu.´.ng G = (V, E ). Ma trˆn liˆn thuˆc d ınh-canh cua d` thi G l` ma trˆn o ¯˙ ’ ˙ ¯ˆ . ’ e ¯o . o ˆ o ae o a a . . . . .i c´c phˆn tu. 0 v` 1, trong d ´ mˆ i cˆt biˆ’u diˆn ˙ ˜o ˜ ` a˙ ’ A = (aij ), i = 1, 2, . . . , n, j = 1, 2, . . . , m, v´ ao a ¯o o . e e mˆt canh cua G v` mˆ i h`ng biˆ’u diˆn mˆt d ınh cua G; ngo`i ra, nˆu canh ek liˆn thuˆc ˙ ˜ ˜ ´ ˙ ’ o ¯˙ .’ ˙ ’ o. aoa e e a e. e o . . . cua cˆt k bˇ ng khˆng ngoai tr`. ` ´’ ` hai d ınh vi v` vj th` tˆ t ca c´c phˆn tu ˙ o ¯˙’ ıa ˙a a˙’. ’ a a o u . aik = 1, ajk = 1. V´ du 1.2.3 Ma trˆn liˆn thuˆc d ınh-canh cua d` thi trong H` 1.4 l` o ¯˙ ’ ˙ ¯o . ’ˆ ı. ae ınh a . . . e1 e2 e3 e4 e5   a1 1 0 0 0 b1 0 0 1 1     c 0 1 1 0 1 d0 0 0 1 1 a..........................................................................e...1..........................................................................b •................ ...• .. .. . .. . ... . .... . ... . ... . ... . . . ... ... ... ... . ... ... ... . ... . .. e4................... . ... . ... ... ... . ... . ... . ... . ... . ... . ... . .. . . ... . ... ... . ... . ... . ... ... ... . ... ... ... . ... . ... ... ... . ... . ... . ...... ...... ... ...... e3 . . . .. . ....... ........ . . .. . . ... ... ... . ... . .. . ... ... . ... ... . ... . ... .. . . ... ... ... . ... . .. . ... ... . ... ... . ... . ... .. e2 . . ... ... ... . ... . .. . ... ... . ... ... . ... . ... .. . . ... ... ... . ... . .. . ... ... . ... ... . ... ... . ... .. . . ... ... .. . ... . . • • . ................................................................................. ... . ................................................................................. .. .. .. e5 c d H` 1.4: ınh Tr´i v´.i ma trˆn liˆn thuˆc d ınh-cung, n´i chung ma trˆn liˆn thuˆc d ınh-canh khˆng o ¯˙ .’ o ¯˙ .’ ao ae o ae o . . . ˙ ’ total unimodular. Chˇng han, trong v´ du trˆn, ma trˆn con a ı.e a . .   110   1 0 1 011 c´ d inh th´.c bˇ ng −2. ` o ¯. ua D` thi vˆ hu.´.ng G = (V, E ) goi l` hai phˆn nˆu c´ thˆ’ phˆn hoach tˆp c´c d ınh -ˆ . o ˙a ` ´ a a ¯˙ ’ o o .a a eoe . . .i nhau V v` V sao cho d ˆi v´.i mˆ i canh (v , v ) ∈ E th` hoˇc ˜ ´ V th`nh hai tˆp con r` a a o a2 ¯o o o. ıa . . 1 ij vi ∈ V1 , vj ∈ V2 hoˇc vj ∈ V1 , vi ∈ V2 . a . 15
a. b •............................... • .. .. . ..... .... . . . ....... . ....... . . . . .... .. . .... .. . . . ... .... . ... ..... .... ... . .... ... . . ... ..... .... .... . . .... ..... .... ... . . . . .... .. .... ... . . . ... .... .... . . .. .... . . . .... ... .... . . ... . ... . ... . . .... .... ... . .. . .... ... . ... . .... . ... .... . .......... ... ......... . . ... ... . . . . . ... ... . . ... ... ...... ... .. ..... . . ... ....... .... ..... . . . .... .... .... ... . . . . . . .... . ...... ..... . ..... . . . .. . .... . . .. . .. .. . . . ... ..... .... ... ... ....... .... .... . . . . .. . . . . ... .... ... . .... . .... .... ... . ... . . .. . . . .... ... . .... .... ... . ....... ... . ... .... . .... . . . .. ... .... .... . ... ... ....... . .. ..... • • • .. . ... ... . .. . . c e d -ˆ . H` 1.5: D` thi hai phˆn K2,3 . ` ınh o a V´ du 1.2.4 Dˆ kiˆ’m tra d` thi K2,3 trong H` 1.5 l` hai phˆn. e˙ ˜e ` ı. ¯o . ˆ ınh a a Mˆnh d` 1.2.5 Ma trˆn liˆn thuˆc d ı’nh-canh cu a d` thi vˆ hu.´.ng G = (V, E ) l` total o ¯˙ ˙ ¯ˆ . o ’ e ¯ˆe a e o o a . . . . unimodular nˆu v` chı’ nˆu G l` d` thi hai phˆn. ´ ´ ` e a ˙e a ¯ˆ . o a Ch´.ng minh. (1) Nˆu d` thi l` hai phˆn, th` ch´ng ta c´ thˆ’ ch´.ng minh theo quy nap rˇ ng ˙ ` ´ˆ ` u e ¯o . a a ıu oeu .a .c det(B ) = 0, 1 hoˇc ˙ ’ o ¯˙ .’ moi ma trˆn vuˆng con B cua ma trˆn liˆn thuˆc d ınh-canh c´ d inh th´ a o ae o ¯. u a . . . . . - iˆu n`y d ung v´.i c´c ma trˆn vuˆng con cˆ p 1; gia su. khˇng d .nh d ung v´.i c´c ma ˙ ’ ` ´ ˙˙ ’’ −1. D e a ¯´ oa a o a a ¯i ¯´ oa . ´ ´ trˆn vuˆng con cˆ p (k − 1). X´t ma trˆn vuˆng con B cˆ p k. a o a e a o a . . Nˆu mˆi cˆt B j cua B ch´.a d ung hai phˆn tu. bˇ ng 1 th` ˜. a ˙` ´ ` ˙ ’ ’a e oo u ¯´ ı Bi = Bi , i∈I1 i∈I2 trong d o I1 v` I2 l` c´c tˆp chı sˆ tu.o.ng u.ng hai phˆn hoach cua tˆp c´c d ınh V v` Bi l` ’´ ˙o ˙ a a ¯˙ ’. ’ ¯´ a aa a ´ a a a . . ´ ınh, nˆn det(B ) = 0. ˙ a B. C´c vector h`ng phu thuˆc tuyˆn t´ ’ vector h`ng cu a a a o e e . . Nˆu, ngu.o.c lai, tˆn tai cˆt c´ d ung mˆt phˆn tu. bˇ ng 1, chˇng han bij = 1, k´ hiˆu C a ˙` ˙ ’ ´ . . ` . o o ¯´ ` ’a e o o a ye . . . . .o.c t`. B bˇ ng c´ch xo´ h`ng i v` cˆt j. Th` ` l` ma trˆn nhˆn d u . u a a a¯ a a aa ao ı . . . det(B ) = ± det(C ) (= 0, 1 hoˇc − 1 theo quy nap). a . . (2) Mˇt kh´c, dˆ d`ng ch´.ng minh rˇ ng ma trˆn liˆn thuˆc d ınh-canh cua d` thi l` mˆt chu ˜a ` o ¯˙ .’ ˙ ¯ˆ . a o ’o a a e u a ae . . . . .c l` sˆ canh trˆn chu tr` l` le-xem Phˆn 1.3) c´ d inh th´.c bˇ ng ±2. Do u` ´ ` ınh ¯ˆ a ˙ u’ ınh a ˙’ tr` d o d`i le (t´ a o . e a o ¯. a . d o G khˆng ch´.a chu tr` d o d`i le v` v` vˆy n´ l` hai phˆn theo bˆ’ d` sau. ˙e ` ınh ¯ˆ a ˙ a ı a o a ’ ¯´ o u a o ¯ˆ . . Bˆ’ d` 1.2.6 D` thi vˆ hu.´.ng G l` hai phˆn nˆu v` chı’ nˆu G khˆng ch´.a chu tr` c´ d ˆ -ˆ . o o ˙e ` ´ ´ a e a ˙e o ¯ˆ o a o u ınh o ¯o . a˙ ’ d`i le . Ch´.ng minh. Diˆu kiˆn cˆn. Do V d u.o.c phˆn hoach th`nh V1 v` V2 : -` e` u e .a ¯. a a a . V = V2 ∪ V2 , V1 ∩ V 2 = ∅. 16
e` . ´o ˙ ’ ınh o ¯o a ˙ ’ Gia thiˆt tˆn tai mˆt chu tr` c´ d ˆ d`i le o . . µ = {vi1 , vi2 , . . . , viq , vi1 } v` khˆng mˆ t t´ tˆ’ng qu´t, lˆ y vi1 ∈ V1 . Do G l` hai phˆn, nˆn hai d ınh liˆn tiˆp trˆn ˙ ´ ´ ` ´ ¯˙ ’ ao a ınh o aa a a e e e e ˙ o o ¯˙ ’ ’ a ¯˙ ’ chu tr` µ phai c´ mˆt d ınh thuˆc V1 v` d ınh kia thuˆc V2 . Do d o vi2 ∈ V2 , vi3 ∈ V1 , . . . , ınh o o ¯´ . . . ˜ v` tˆ’ng qu´t, vik ∈ V1 nˆu k le v` vik ∈ V2 nˆu k chˇn. M` chu tr` µ c´ d ˆ d`i le nˆn ˙ ´ ´ ˙a ’ o ¯o a ˙ e ’ ao a e e a a ınh . ˙.i vˆy vi1 ∈ V2 . Diˆu n`y mˆu thuˆn v´.i V1 ∩ V2 = ∅. -` ˜o ’a viq ∈ V1 v` bo . a ea a a Diˆu kiˆn d u. Khˆng mˆ t t´ tˆ’ng qu´t gia thiˆt d` thi G liˆn thˆng. Gia su. khˆng tˆn -` ˙ ´ ´ˆ ` e ¯˙ ’ ˙ ’ ˙˙ ’’ e o a ınh o a e ¯o . e o o o . ınh o ¯ˆ a ˙ ’ tai chu tr` c´ d o d`i le. . . ˙ ’ ´ . ¯˙’ Chon d ınh bˆ t k`, chˇng han vi v` g´n nh˜n cho n´ l` “ + ”. Sau d o lˇp lai c´c ph´p ay a aa a oa ¯´ a . a e . . to´n sau: a Chon d ınh d a d u.o.c g´n nh˜n vj v` g´n nh˜n ngu.o.c v´.i nh˜n cua vj cho tˆ t ca c´c ´’ . ¯˙ ’ ¯˜ ¯ . a ˙ ’ a ˙a a aa a .o a .i d ınh v . `o ’ d ınh kˆ v´ ¯˙ ¯˙’ e j Tiˆp tuc qu´ tr` n`y cho dˆn khi xay ra mˆt trong hai tru.`.ng ho.p: ´ ´ ˙ ’ e. a ınh a ¯e o o . . (a) Tˆ t ca c´c d ınh d ˜ d u.o.c g´n nh˜n v` hai d ınh bˆ t k` kˆ nhau c´ nh˜n kh´c nhau (mˆt ´’ a y` ´ a ˙ a ¯ ˙ ¯a ¯ . a ’ ¯˙’ aa e oa a o . ´u + v` mˆt mang dˆ u −); hoˇc ´ mang dˆ a ao a a . . (b) Tˆn tai d ınh, chˇng han vjk , d u.o.c g´n hai nh˜n kh´c nhau. ˙ ’ ` . ¯˙ ’ o a ¯. a a a . Trong Tru.`.ng ho.p (a), d at V1 l` tˆp tˆ t ca c´c d ınh d u.o.c g´n nh˜n “+” v` V2 l` tˆp tˆ t ´’ ´ a a a ˙ a ¯˙ ’ ¯. a o ¯ˇ a a aa a . . . . .o.c g´n nh˜n “−”. Do tˆ t ca c´c canh liˆn thuˆc gi˜.a c´c cˇp d ınh c´ nh˜n ´’ ˙ a ¯˙ ’ ’¯ a ˙a . u a a ¯˙ ’ ca c´c d ınh d u . a a e o oa . . kh´c nhau nˆn d` thi G l` hai phˆn.` a e ¯o .ˆ a a Trong Tru.`.ng ho.p (b), d ınh vjk d u.o.c g´n nh˜n “+” doc theo mˆt dˆy chuyˆn µ1 n`o ` ¯˙ ’ o ¯. a a oa e a . . . .i c´c d ınh d u.o.c g´n nh˜n “+” v` “−” xen k˜ nhau xuˆ t ph´t t`. v v` kˆt th´c tai ´ ´ d o, v´ a ¯˙ ’ ¯. a ¯´ o a a e a auiae u. .o.ng tu., d ınh v d u.o.c g´n nh˜n “−” doc theo mˆt dˆy chuyˆn µ n`o d ´, v´.i c´c ` . ¯˙ ’ vjk . Tu jk ¯ . a a oa e 2 a ¯o oa . . d ınh d u.o.c g´n nh˜n “+” v` “−” xen k˜ nhau xuˆ t ph´t t`. vi v` kˆt th´c tai vjk . Nhu.ng ´ ´ ¯˙’ ¯. a a a e a au ae u. nhu. thˆ chu tr` d i doc theo µ1 t`. d ınh vi dˆn d ınh vjk sau d o d i ngu.o.c lai doc theo µ2 ´ ´’ u ¯˙’ ¯e ¯ ˙ e ınh ¯ . ¯´ ¯ ... ` lai vi c´ d ˆ d`i le. Diˆu n`y mˆu thuˆn v´.i gia thiˆt, v` do d ´ khˆng thˆ’ xay ra Tru.`.ng ˙ -` ˙’ ˜o ´a ’ ˙ ’ e˙ vˆ . e o ¯o a ea a a e ¯o o o . .p (b). Dinh l´ d u.o.c ch´.ng minh. -. ho y¯ . u . a` Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ˙nh-d ˙nh ’ ’ 1.2.3 e a e o ¯ı ¯ı . . . Gia su. G = (V, E ) l` d` thi sao cho c´ nhiˆu nhˆ t mˆt cung liˆn thuˆc hai d ınh bˆ t k` vi ` ´o ´ ˙˙ ’’ ¯˙’ a ¯o . ˆ o e a e o ay . . a` ´ o ¯˙ ¯˙ ’ ’ v` vj . Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ınh-d ınh l` ma trˆn vuˆng A = (aij ) cˆ p n × n a e ae a a o a . . . . 17
v´.i c´c phˆn tu. 0 hoˇc 1: ` a˙ ’ oa a . ´ 1 nˆu (vi , vj ) ∈ E, e aij := nˆu ngu.o.c lai. ´ 0 e .. Trong tru.`.ng ho.p d` thi vˆ hu.´.ng, ma trˆn kˆ cua d o.n d` thi c˜ng c´ thˆ’ d u.o.c d .nh ˙ a`˙¯ . e’ o . ¯o . o o ˆ ¯o . u ˆ o e ¯ . ¯i .o.ng u.ng hai cung (v , v ) v` (v , v ). Trong tru.`.ng ıa ` ˜ ngh˜ bˇ ng c´ch xem mˆ i canh (vi , vj ) tu a a o. ´ aji o ij .p n`y, ma trˆn kˆ l` d oi x´.ng. ` a ¯ˆ u ´ ho a ae . . C´c biˆ’u diˆn cua d` thi ˙ ˜ ˙ ¯ˆ . ’ 1.2.4 a e e o Dˆ’ mˆ ta mˆt d` thi, ta c´ thˆ’ su. dung mˆt sˆ c´ch biˆ’u diˆn kh´c nhau. V´.i quan d iˆ’m - e o ˙ o ¯ˆ . ˙ ˙’ ˙ ˙ ˜ .´ ’.o o e˙ . o oa e e a o ¯e .o.ng d u.o.ng theo kh´ canh hiˆu qua cua ınh, n´i chung c´c biˆ’u diˆn n`y khˆng tu ˙ ˜ ˙˙ ’’ lˆp tr` a o a e e a o ¯ ıa . e . . thuˆt to´n. a a . ınh: Th´. nhˆ t, su. dung ma trˆn kˆ hoˇc c´c dˆ n xuˆ t cua C´ hai c´ch biˆ’u diˆn ch´ ˙ ˜ ˜ ´ a` ´’ ˙. ’ a˙ o a e e u a eaaa . . . hai, su. dung ma trˆn liˆn thuˆc hoˇc c´c dˆn xuˆ t cua n´. ˜ ´’ ˙. ’ a˙o n´; th´ o u ae o aaa . . . Su. dung ma trˆn kˆ a` ˙. ’ e . Ch´ng ta biˆt rˇ ng c´c ma trˆn kˆ cho ph´p miˆu ta hoˇc c´c 1-d` thi d .nh hu.´.ng, hoˇc e` ´a a` e˙aa ’ u a e e ¯ˆ . ¯i o o a . . . .n d` thi vˆ hu.´.ng. V´.i c´ch biˆ’u diˆn d` thi qua ma trˆn kˆ, ta thˆ y sˆ lu.o.ng thˆng ˙ ˜ ¯o . a` ´´ c´c d o ¯o . o o a¯ ˆ oa e eˆ e ao. o . tin, gˆm c´c bit 0 v` 1, cˆn lu.u tr˜. l` n2 . C´c bit c´ thˆ’ d u.o.c kˆt ho.p trong c´c t`.. K´ ˙ ` ` ´ o a a a ua a o e¯ . e . au y . (t´.c l` sˆ c´c bit trong mˆt t`. m´y t´ ˜ ´ a ¯ˆ a ˙ u ’ ˙ ’ hiˆu w l` d o d`i cua t` u a o a e o u a ınh). Khi d ´ mˆ i h`ng cua ma ¯o o a . . . trˆn kˆ c´ thˆ’ d u.o.c viˆt nhu. mˆt d˜y n bit trong n/w tu. 1 . Do d o sˆ c´c t`. dˆ’ lu.u tr˜. ˙ ˙ a ` o e¯ . ´ ´ e e oa ` ¯´ o a u ¯e u . . ` l` n n/w . ma trˆn kˆ a ae . Ma trˆn kˆ cua d` thi vˆ hu.´.ng l` d oi x´.ng, nˆn ta chı cˆn lu.u tr˜. nu.a tam gi´c trˆn a ` ˙ ¯o . o o ´ ˙` . e’ ˆ ’a u˙ ’ a ¯ˆ u e ae ` n n(n − 1)/2 bit. Tuy nhiˆn, v´.i c´ch lu.u tr˜. n`y, s˜ tˇng d ˆ ph´.c ˙oa ’ ¯´ ˙ a ’ cua n´, v` do d o chı cˆ e oa u a e a ¯o u . tap v` th`.i gian t´ to´n trong mˆt sˆ b`i to´n. ´ ao ınh a ooa a . . Trong tru.`.ng ho.p c´c ma trˆn thu.a (m n2 v´.i d` thi c´ hu.´.ng; m 1 ´ o .a a o ¯o . o o ˆ n(n + 1) d ˆi ¯o . 2 .i d` thi vˆ hu.´.ng) c´ch biˆu diˆn n`y l` l˜ng ph´ Do d o ta s˜ t` c´ch biˆ’u diˆn chı c´c ˙ ˜ ˜ a aa ˜ ˙a ’ v´ ¯ˆ . o o oo a e e ı. ¯´ e ım a e e phˆn tu. kh´c khˆng. `a˙ ’ a o V` muc d´ n`y ta s˜ su. dung mˆt mang danh s´ch kˆ cho d` thi c´ hu.´.ng. D` thi c´ -ˆ . o ` e˙ . ’ ˙ ’ ı . ¯ıch a o a e ¯o . o o ˆ o . .´.ng d u.o.c biˆ’u diˆn bo.i mˆt mang c´c con tro V out[1], V out[2], . . . , V out[n], trong d o ˙ ˜ ˙’ ˙’ ˙ ’ hu o ¯. e e o a ¯´ . .o.ng u.ng v´.i mˆt d ınh trong d` thi c´ hu.´.ng. Mˆ i phˆn tu. cua mang V out[i] ˜ ˜ ` ˙˙ ˙ ’ o o ¯˙ .’ a ’’ ˙ ’ mˆi con tro tu o ´ ¯ˆ . o o o o ˙ dˆn mˆt n´t d` u lu.u tr˜. muc d˜. liˆu cua n´t tu.o.ng u.ng d ınh vi v` ch´.a mˆt con tro ´ ’ ¯e ˙u ’ ˙’ ˙ ’ chı o u ¯a ˆ u . ue ´ ¯ au o . . . K´ hiˆu x l` sˆ nguyˆn nho nhˆ t khˆng b´ ho.n x. 1 ´ ´ ˙ ’a ye ao e o e . 18
chı dˆn mˆt danh s´ch liˆn kˆt cua c´c d ınh kˆ (d ınh d u.o.c nˆi v´.i vi theo hu.´.ng t`. vi ra). ’´ ´’ ` ¯˙ ¯ . o o ´ ˙ ¯e e e ˙ a ¯˙ ’ e’ o a o u . .`.ng: ˜ o u`o Mˆi n´t kˆ c´ hai tru o e 1. Tru.`.ng sˆ nguyˆn: lu.u tr˜. sˆ hiˆu cua d ınh kˆ; v` ´ ´. `a u o e ˙ ¯˙ ’ ’ o o e e 2. Tru.`.ng liˆn kˆt chı dˆn n´t kˆ tiˆp trong danh s´ch kˆ n`y. ´ ’´ ´´ `a ˙ ¯e u e e o ee a e v1 v2 •..........................................................................•............ . . ... ... . .. ...... ....... . . . .. ... . . ... . . . .. . .. . .. . .. . ..... . ... ... .. ... .. . ... .. . ... ... .. ... . .. ... . .. . ... ... . ... . . .. ... . .. . ... ... ... . . .... . . .. . . . ... .. .... ... . ... . .... . . . .. . .... . .... .. ... ... . .. . .. . . . .. ... . .. ... .. ... . . ... . . ... . . ... .. . ... . .. . ... . . ... . ... . . .. . ... . ... .. . ... . ... . . . . .. ... . . ... ... .. ... . . . . . ... . .. ... .............. . ... ... ............... ... . . .. .... . v6 • . .. ... .. .. ... .. ... .. ... • . . . ... ... . . . . . . . . . .. ... ... . ... .. . . .... . .. .. . . ... .. ...... .. ... . .. .. ... .. ... . . ........ ............... . .. ........ .............. .. . . . ... . ... v3 .. .. . . .. . .... .... . .... .... . .. . ... . ... . . .. . .. .... ... . . .... .... .. ... . . ... . . .. ... . .. . ... .... . ... .. . ... .... .. . . . . ...... ... . ... ... .. . ....... . ... .. . . ... ... ... . .. . . . ... ..... .. . .. . ... .. ....... .... .. . . . ..... .. ....... ... . . .. . ... . ... . . .. . ... .... . . . . .. . . ... . .. ... .... .. . . ... .... ... . ... . . ... . . ... . .. .... ... . ... . . ... ....... .. ... .. . ... . .. . .. . ... .. . .. . .... ..... . ... ..... .. . .... ... . . ... . ... . ....... .. .. . .... . ... . ....... ... ... ......... . ..... . • • . .... . ..... . . .. v5 v4 H` 1.6: ınh C´ch biˆ’u diˆn mang danh s´ch kˆ V out[] cua d` thi c´ hu.´.ng trong H` 1.6 d u.o.c ˙ ˜ ` ˙ ’ ˙ ¯ˆ . o o ’o a e e a e ınh ¯. .o.ng u.ng trong H` 1.7 (gia su. c´c muc d˜. liˆu tu.o.ng u.ng c´c d ınh theo th´. tu. l` ˙˙a ’’ ˙ ’ cho tu ´ ınh . ue ´ a¯ u.a . A, B, C, D, E, F ). N´t . d` u u ¯ˆ a . . . . . . . . . . . . v4 v5 . . . • • •............................................. NULL V out[1] . . . A . . . ............... . . . .. . . .............. .. . . . ...................... ..................... . ...................... ..................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................ v1 •............................................ v3 . . . •............................................. NULL V out[2].................................. B . . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................ v3 . . •............................................ NULL V out[3].................................. C . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •.............................................. v2 •.............................................. v3 . . . •............................................... NULL V out[4]................................. D . . . . . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................. v3 •............................................. v6 •.............................................. NULL V out[5]................................... E . . . . . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................ v1 . . •............................................ NULL V out[6].................................. F . . . . .. . .. . . . . . . . . . . . . . . . . . H` 1.7: Danh s´ch kˆ V out[] tu.o.ng u.ng d` thi trong H` 1.6. ` ınh a e ´ ¯o . ˆ ınh Thay v` con tro chı dˆn mˆt danh s´ch c´c d ınh t`. vi d i ra trong V out[i], ta tro dˆn ’ ’´ ’´ ˙ ˙ ¯e a ¯˙ ’ ˙ ¯e ı o a u ¯ . ˙ lu.u tr˜. d` thi thˆng qua mang c´c danh s´ch ’ ´ a ¯˙ ¯ ¯e ’ ˙ ’ danh s´ch c´c d ınh d i dˆn vi v` do d o c´ thˆ a a ¯´ o e u ¯o . o ˆ a a 19
k` V in[i]. H` 1.8 minh hoa mang c´c danh s´ch kˆ V in[] cua d` thi c´ hu.´.ng trong H` ` ˙ ’ ˙ ¯o . o o ’ˆ ˆ e ınh a a e ınh . 1.6. Dˆ’ y rˇ ng, c´c sˆ trong n´t kˆ cua V out[] (tu.o.ng u.ng, V in[]) l` nh˜.ng chı sˆ cˆt -e ´ ` ˙ ´ u`˙ ’´. e’ ˙oo a ao ´ au .o.ng u.ng, h`ng) trong ma trˆn kˆ cua d` thi m` o. d ´ sˆ 1 xuˆ t hiˆn. Ngo`i ra, trong ` ˙ ¯o . a ˙ ¯o o ´ ´e ’ ’ (tu ´ a ae ˆ a a . . tru.`.ng ho.p d` thi vˆ hu.´.ng, hai danh s´ch kˆ n`y l` tr`ng nhau. `aau o ¯ˆ . o o o a e . Khi d` thi c´ trong sˆ, t´.c l` nˆu mˆi cung hoˇc canh e ∈ E c´ mˆt trong lu.o.ng w(e), ˜ ´ ´ ¯o . o . ˆ ouae o a. oo . . . . . rˆng cˆ u tr´c cua mˆi n´t trong danh s´ch kˆ bˇ ng c´ch thˆm mˆt tru.`.ng ˜ e` ˙` ´ `a ’a ˙. ’ u˙ ’ ta chı cˆn mo o a ou a a e o o . .u tr˜. trong lu.o.ng cua cung. ˙ ’ lu u. . C´ch biˆ’u diˆn bˇ ng danh s´ch kˆ cua d` thi c´ hu.´.ng c´ thˆ’ d u.o.c c`i d at trong ngˆn ˙ ˙ ˜a e` ` ˙ ¯ˆ . o o e’ o a e a o e ¯ . a ¯ˇ o . . lˆp tr` C v´.i c´c khai b´o trong thu. viˆn Graph.h (xem Phu luc A). Dˆ’ xˆy du.ng -e a ˙ ng˜ a u. ınh oa a e . .. . mang c´c danh s´ch kˆ V out[] v` V in[] cho mˆt d` thi, ta c´ thˆ’ su. dung c´c thu tuc ˙’ ` ˙ ’ o e˙. ˙. ’ a a e a o ¯ˆ . .o a MakeV out() v` MakeV in() tu.o.ng u.ng. a ´ N´t . d` u u ¯a ˆ . . . . . . . . . . . . •............................................. v2 •............................................. v6 . . . •............................................... NULL V in[1] ................................... A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................. v4 . . •............................................. NULL V in[2] .................................. B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................. v2 •............................................. v3 •............................................... v4 •............................................ v5 . . . . . •............................................ NULL V in[3] .................................. C . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................. v1 •............................................. NULL V in[4] .................................. D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................... v1 . . •............................................... NULL V in[5] .................................. E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................... v5 . . •............................................... NULL V in[6] ................................... F . . . . . . . . . . . . . . . . . . . . . . . . . . H` 1.8: Danh s´ch kˆ V in[] tu.o.ng u.ng d` thi trong H` 1.6. ` ınh a e ´ ¯o . ˆ ınh Su. dung c´c ma trˆn liˆn thuˆc d ˙nh-cung hoˇc d ˙nh-canh ˙. ’ ’ ’ a a e o ¯ı a ¯ı . . . . Ma trˆn liˆn thuˆc d ınh-cung hoˇc d ınh-canh cho ph´p ch´ng ta mˆ ta d` y d u cˆ u tr´c cua ’´ o ¯˙ .’ a ¯˙ .’ o ˙ ¯ˆ ¯ ˙ a ’a u˙ ’ ae e u . . . kh´c khˆng trong mˆ i ˜ mˆt d a d` thi khˆng c´ khuyˆn. Tuy nhiˆn, do chı c´ hai phˆn tu ` ˙o ’ a˙ ’ o ¯ ¯o . o ˆ o e e a o o . ˙ biˆ’u diˆn thˆng tin o. dang th´ ho.p ho.n. ’e ˙ ˜ ˙. ’ cˆt, nˆn c´ thˆ o eoe e o ıch . . Ch´ng ta d .nh ngh˜ hai mang tuyˆn t´ α[] v` β [] chiˆu m trong d o v´.i mˆ i cung ˜ ´ ` ˙ ’ u ¯i ıa e ınh a e ¯´ o o ’´’ ˙ o ˙ a ¯˙ ’ hoˇc canh ek , k = 1, 2, . . . , m, c´c gi´ tri α[k ] v` β [k ] l` c´c chı sˆ cua c´c d ınh m` ek liˆn a. a a. a aa a e . 20