Giáo trình đồ thị

Chia sẻ: Trần Bá Trung | Ngày: | Loại File: PDF | Số trang:212

Thêm vào BST

Báo xấu

82
lượt xem 20
download

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

trong thực tế để miêu tả một tình huống người ta thường biểu thị bằng một hình ảnh gồm các điểm(các đỉnh)-biểu diễn các thực thể - và vẽ các đoạn thẳng nối cặp các đỉnh biểu diễn mối quan hệ giữa chúng. Những hình ảnh như thế thường gọi là các đồ thị.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình đồ thị

SÁCH Giáo trình đồ thị
Muc luc . . L`.i n´i d` u o o ¯ˆ a 7 1 Dai cu.o.ng vˆ d` thi - . ` ¯ˆ . e o 9 1.1 -. Dinh ngh˜ v` c´c kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . ıa a a a e . 9 1.1.1 D` thi c´ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o o 9 1.1.2 -ˆ . aa D` thi v` ´nh xa d a tri . . . . . . . . . . . . . . . . . . . . . . . . . . o . ¯ . 10 1.1.3 D` thi vˆ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o o 10 1.1.4 C´c d inh ngh˜ ch´ . . . . . . . . . . . . . . . . . . . . . . . . . . . a ¯. ıa ınh 11 1.2 Ma trˆn biˆ’u diˆn d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a . e˙ ˜ ¯ˆ . e o 13 1.2.1 a e . o ¯˙ . ’ Ma trˆn liˆn thuˆc d ınh-cung . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2 a e . o ¯˙ . ’ Ma trˆn liˆn thuˆc d ınh-canh . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.3 a ` o ¯˙ ¯˙ ’ ’ Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ınh-d ınh . . . . . . . . . . . . . . e a e . . 17 1.2.4 C´c biˆ’u diˆn cua d` thi . . . . . . . . . . . . . . . . . . . . . . . . . a e˙ ˜ ˙ ¯o . e ’ ˆ 18 1.3 T´ liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ınh e o 23 1.3.1 a ` Dˆy chuyˆn v` chu tr` . . . . . . . . . . . . . . . . . . . . . . . . . e a ınh 23 1.3.2 Du.`.ng d i v` mach . . . . . . . . . . . . . . . . . . . . . . . . . . . . - o ¯ 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 1.3.5 -ˆ . e D` thi liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . o o . 31 1.4 Pham vi v` liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . . . a e o . 33 1.4.1 Ma trˆn pham vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a . . 33 1.4.2 a ` T` c´c th`nh phˆn liˆn thˆng manh . . . . . . . . . . . . . . . . . . ım a a e o . 36 1.4.3 Co. so. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ’ 39 1.5 -a ˙ ’ Dˇng cˆ u cua c´c d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˙ a ¯ˆ . 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 1.6 C´c d` thi d ac biˆt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a ¯o . ¯ˇ ˆ . e . 46 1.6.1 -ˆ . o D` thi khˆng c´ mach . . . . . . . . . . . . . . . . . . . . . . . . . . o o . 46 1.6.2 -ˆ . a ˙ ’ D` thi phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 46 2 C´c sˆ co. ban cua d` thi a o ´ ˙ ’ ˙ ¯ˆ . ’ o 49 2.1 ´ Chu sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 49 2.2 ´ ´ Sˇc sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a o 52 2.2.1 a ´ ´ C´ch t` sˇc sˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ım a o 54 2.3 Sˆ ˆ’n d .nh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˙ o o ¯i 55 2.4 Sˆ ˆ’n d .nh ngo`i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˙ o o ¯i a 61 2.5 ˙ ’ Phu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.6 Nhˆn cua d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a ˙ ¯ˆ . ’ o 69 2.6.1 a ¯. y ` ` . a e o ´ C´c d inh l´ vˆ tˆn tai v` duy nhˆ t . . . . . . . . . . . . . . . . . . . a 69 2.6.2 Tr` cho.i Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 72 2
3 C´c b`i to´n vˆ d .`.ng d a a a ` ¯u o e ¯i 75 3.1 Du.`.ng d i gi˜.a hai d ınh - o ¯ u ¯˙’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.1.1 Du.`.ng d i gi˜.a hai d ınh . . . . . . . . . . . . . . . . . . . . . . . . . - o ¯ u ¯˙’ 75 3.1.2 -ˆ . e D` thi liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . o o . 76 3.2 Du.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh . . . . . . . . . . . . . . . . . . . . . . . - o ¯ ´ a ´ u a ¯˙’ 78 3.2.1 Tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm . . . . . . . . . . . . . . o . a . . . o a 78 3.2.2 Tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y . . . . . . . . . . . . . . . . . o . a . . . y´ 82 3.3 Du.`.ng d i ngˇn nhˆ t gi˜.a tˆ t ca c´c cˇp d ınh . . . . . . . . . . . . . . . . . - o ¯ ´ a ´ u a ˙ a a ¯˙ a ´ ’ . ’ 87 3.3.1 Thuˆt to´n Hedetniemi (tru.`.ng ho.p ma trˆn trong lu.o.ng khˆng ˆm) a . a o . a . . . o a 88 3.3.2 Thuˆt to´n Floyd (tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y) . . . . . . 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 3.4.1 Mach tˆi u.u trong d` thi c´ hai trong lu.o.ng . . . . . . . . . . . . . . . ´ o ¯ˆ . o o . . 96 ˆ 4 CAY 99 4.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ¯ˆ ’ a 99 4.2 Cˆy Huﬀman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 a 4.2.1 ´ C´c bˆ m˜ “tˆt” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 a o a o . 4.2.2 M˜ Huﬀman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 a 4.3 Cˆy bao tr`m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 a u 4.3.1 . a ım e ´ ` o Thuˆt to´n t` kiˆm theo chiˆu rˆng x´c d .nh cˆy bao tr`m . . . . . 107 a e . a ¯i a u 4.3.2 . a ım e ´ ` a a ¯. Thuˆt to´n t` kiˆm theo chiˆu sˆu x´c d inh cˆy bao tr`m . . . . . 107 a e a u 4.3.3 T` cˆy bao tr`m du.a trˆn hai mang tuyˆn t´ ım a u . e ˙ ’ ´ e ınh . . . . . . . . . . . 108 4.3.4 ´ ’ a ım a ˙ a a Thuˆt to´n t` tˆ t ca c´c cˆy bao tr`m . . . . . . . . . . . . . . . . 112 a . u 4.3.5 Hˆ co. so. cua c´c chu tr` d ˆc lˆp . . . . . . . . . . . . . . . . . . . 112 e . ˙ ˙ a ’ ’ ınh ¯o a . . 3
4.4 Cˆy bao tr`m tˆi thiˆ’u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 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 a a 5 B`i to´n Euler v` b`i to´n Hamilton a a a a a 127 5.1 B`i to´n Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 a a 5.1.1 a . a ım a ` Thuˆt to´n t` dˆy chuyˆn Euler . . . . . . . . . . . . . . . . . . . . 129 e 5.2 B`i to´n ngu.`.i d u.a thu. Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . 131 a a o ¯ 5.3 B`i to´n Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 a a 5.3.1 C´c d iˆu kiˆn cˆn dˆ’ tˆn tai chu tr` Hamilton . . . . . . . . . . . . 138 a ¯` e . a ˙ o e ` ¯e ` . ınh 5.3.2 C´c d iˆu kiˆn d u vˆ su. tˆn tai chu tr` Hamilton a ¯` e e ¯˙ ` . ` . . ’ e o ınh . . . . . . . . . . 139 5.3.3 C´c d iˆu kiˆn d u vˆ su. tˆn tai mach Hamilton . . . . . . . . . . . . . 142 a ¯` e e ¯˙ ` . ` . . ’ e o . -ˆ . ˙ ’ 6 D` thi phˇ ng o a 149 6.1 -. Dinh ngh˜ v` c´c v´ du . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 ıa a a ı . 6.2 C´c biˆ’u diˆn kh´c nhau cua mˆt d` thi phˇng . . . . . . . . . . . . . . . . 151 a e˙ ˜ e a ˙ ’ o ¯o . a . ˆ ˙ ’ 6.3 ´ ’ o a ınh a ˙ ¯ˆ . a ˙ ’ C´c t´ chˆ t cua d` thi phˇng . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.4 ˙ ’ Ph´t hiˆn t´ phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 a e ınh a . 6.4.1 Kiˆ’m tra t´ phˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 e˙ ˙ ’ ınh a 6.5 -o ´ ˜ Dˆi ngˆ u h` hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 a ınh . 6.6 Dˆi ngˆ u tˆ’ ho.p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 -o ´ ˜ a o . ˙ . a . ˙ ’ 7 Mang vˆn ta i 173 4
7.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 ˙ ¯ˆ ’ a 7.2 B`i to´n luˆng l´.n nhˆ t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 a a ` o o ´ a 7.2.1 Thuˆt to´n g´n nh˜n dˆ’ t` luˆng l´.n nhˆ t . . . . . . . . . . . . . . 180 a . a a ˙ a ¯e ım ` o o ´ a 7.2.2 - ˆ . ¯` D` thi d iˆu chınh luˆng . . . . . . . . . . . . . . . . . . . . . . . . . . 181 o e ˙ ’ ` o 7.2.3 a ıch ` Phˆn t´ luˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 o 7.3 C´c cai biˆn d o.n gian cua b`i to´n luˆng l´.n nhˆ t . . . . . . . . . . . . . . . 183 a ˙ ’ e ¯ ˙ ’ ˙ a a ’ ` o o ´ a 7.3.1 C´c d` thi c´ nhiˆu nguˆn v` nhiˆu d´ . . . . . . . . . . . . . . . . 183 a ¯ˆ . o o `e ` a o ` ¯ıch e 7.3.2 C´c d` thi v´.i r`ng buˆc tai c´c cung v` d ınh . . . . . . . . . . . . . 184 a ¯ˆ . o a o o . a . a ¯˙’ 7.3.3 C´c d` thi c´ cˆn trˆn v` cˆn du.´.i vˆ luˆng . . . . . . . . . . . . . . 185 a ¯ˆ . o a o . e a a . o ` `e o 7.4 Luˆng v´.i chi ph´ nho nhˆ t . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 ` o o ı ˙ ’ a ´ 7.4.1 Thuˆt to´n Klein, Busacker, Gowen . . . . . . . . . . . . . . . . . . . 186 a . a 7.5 Cˇp gh´p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 a . e 7.5.1 a a a ` a C´c b`i to´n vˆ cˇp gh´p . . . . . . . . . . . . . . . . . . . . . . . . 189 e . e 7.5.2 Cˇp gh´p l´.n nhˆ t trong d` thi hai phˆn . . . . . . . . . . . . . . . . 192 a . e o ´ a ¯ˆ . o ` a 7.5.3 Cˇp gh´p ho`n hao trong d` thi hai phˆn . . . . . . . . . . . . . . . 193 a . e a ˙ ’ ¯ˆ . o ` a A Thu. viˆn Graph.h e . 197 a e . ˙ ’ T`i liˆu tham kha o 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 o e˙ . `a o ınh ˙ . ’ ` gˆm c´c d iˆ o a ¯e ˙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 ¯˙’ e˙ ˜ a e . e˙ a e a ¯ . ˙ a’ ´ . o a a ¯˙ ’ e˙ ˜ ´ .a ch´ng. Nh˜.ng h` nhu. thˆ thu.`.ng goi l` c´c d` thi. Muc d´ cua ´ diˆn mˆi quan hˆ gi˜ e o e u . u u ınh e o . a a ¯o .ˆ . ¯ıch ˙ ’ a ınh a ´ gi´o tr` n`y cung cˆ p nh˜ a u.ng kiˆn th´.c co. ban dˆ’ nghiˆn c´.u c´c d` thi. C´c d` thi xuˆ t ´ e u ˙ ¯e ’ ˙ e u a ¯o . a ¯ˆ . a ˆ o ´ e. ` 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 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 u o u ˙ trong x˜ hˆi v` kinh tˆ, “cˆ u tr´c phˆn tu.” trong ho´ hoc, vˆn vˆn. a o a . ´ a e ´ u a ˙ ’ a . a a 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 u ´ . o . a ˙ ’ o ` ınh . e o a´ ` e e u xung quanh l´ thuyˆt d` thi trong nh˜ y ´ ˆ e ¯o . u.ng nˇm gˆn d ay; mˆt nhˆn tˆ chu yˆu g´p phˆn th´c a ` ¯ˆ a o ´ ’ ´ a o ˙ e o ` a u . da ¯ˆ ˙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 e˙ ¯´ a a ´ e a. a ınh o o e ˙ . e. ` e e a o 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 ´ . ´ o ¯ˆ a e. e˙ ˜ e . ´ e a ´ e a e o . ´ . ´ a e ˙ ’ . a ` mang truyˆn thˆng, d ˜ d u ¯e e o ¯a ¯ .a dˆn nh˜.ng d` thi c´ k´ thu.´.c l´.n v` viˆc phˆn t´ th`nh ´ u ¯ˆ . o ıch o o o a e a ıch a . . cˆng hˆ thˆ o e o . ´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 . o a . ´ `e a a a. a ´ o u ˙ a ’ ˙ ’ 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 e a a . a a ınh e viˆn c´ thˆ’ viˆt dˆ d`ng c´c chu ˙ ´ e e o e e ˜ a a .o.ng tr` minh hoa. Gi´o tr` d u.o.c biˆn soan cho c´c d oi ı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 a ınh ˙ . ’ o u ¯e˙ . e o e ˜ a˙ 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 ` o o o e sang c´c ngˆn ng˜ a a o u a ¯o a . ´ ´ u ` oe 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 ` a e a ´ ınh a e a ´ u u e. a e e ´ e ¯o hoi sinh viˆn phai c´ nh˜.ng k˜ nˇng lˆp tr` tˆt. ˙ ’ e ˙ o u ’ y a 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 ˙ ’ a o. ` 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. u a ´ ınh a u a e . a ˙ ` ¯o . ’ e ˆ • 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. ınh a u ´ o ˙ ’ ˙ ¯ˆ . ´ ’ o ıa . ˜ ˙ a 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 ¯e e . a e . ` 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˜. ´ e . ˙ a ’ e u liˆu. Ngo`i ra xˆy du.ng c´c thuˆt to´n t` cˆy bao tr`m nho nhˆ t. e . a a . a a . a ım a u ˙ ’ a´ • 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 a a a a a a u ˙ o ’ . ˙ ’ u e ¯ . o ¯e ´ trong Chu .o.ng 5. • Chu.o.ng 6 nghiˆn c´.u c´c t´ chˆ t phˇng cua d` thi; v` cuˆi c`ng e u a ınh a ´ ˙ ’ a ˙ ¯ˆ . a o u ’ o ´ • Chu.o.ng 7 t` hiˆ’u c´c b`i to´n trˆn mang vˆn tai. ˙ ım e a a a e . a ˙ . ’ 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 u e a u. ˙ . ` ’ a ´ ˙ e ¯e do ¯ .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. ˙ ’ a a ¯ . ı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 ınh ¯ . e . ` ¯a e e a ˆ o a ˙ ’ a ` e ´ e o a ˙ ’ gia mong c´ nh˜ o u .ng d ´ng g´p t`. ban d oc. ¯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 a o ˙ . e e 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 . e a a . . 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 - . ` ¯ˆ . e o 1.1 -. Dinh ngh˜ v` c´c kh´i niˆm ıa a a a e . 1.1.1 D` thi c´ hu.´.ng -ˆ . o 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 o ` o o a . . a ` a ˙ . a ¯˙ ’ ’ u a o a. . ˜ E c´c cung sao cho mˆ i cung e ∈ E tu a o .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 ’ ´ u . ´ e . . c´ d ung mˆt cung e tu o ¯´ o .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 ¯ ˙ ¯ . a ’ ´ u . e e ´ . 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, u e ˙ ˙ a ¯˙ ’ ’ ’ ¯ . ¯´ ´ o a ˙ ’ 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` ´ e a o . ´ a a ¯˙ ¯ . a . ’ ´ u . a ı ¯˙’ . a ´ 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 .`.ng . a . . a e o . a u e k´ hiˆu m = #E−sˆ . y e . ´ canh cua d` thi G. C´c canh thu.`.ng d u.o.c d ´nh sˆ l` e1 , e2 , . . . , em . o ˙ ¯ˆ . ’ o a . o ¯ . ¯a ´ 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 o a . ınh . a ¯˙ ’ ¯ . e˙ ˜ e ˙ a ¯e ’ ˙ a ¯ . e˙ ˜ e ˙ ’ diˆn bo.i mˆt cung nˆi c´c d iˆ’m v v` v . o ´ o a ¯e ˙ . i a j Mˆt cung c´ gˆc tr`ng v´.i ngon goi l` khuyˆn. o . o o´ u 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 ´ e o `e o . ´ o o . a . . ı . a ¯ ¯o . a a ˆ cung tu .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 ´ - . a ¯o . o o ˆ a ¯o . o ˆ e ¯´ ¯˙’ a y a o e a´ o . ˙ ’ 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´ ´ ` a . ¯o . ˆ ınh o cung e8 l` khuyˆn; c´c cung e4 v` e9 l` song song do c`ng tu a e a a a u .o.ng u.ng cˇp d ınh v v` v . ´ a ¯˙’ . 3 a 4 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 1.1.2 -ˆ . aa D` thi v` ´nh xa d tri 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 y e . ¯o o o a . . ¯ . Γ: V → 2V , x → Γ(x). K´ hiˆu Γ−1 l` ´nh xa (d a tri) ngu.o.c cua Γ. y e. 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 ´ e a ¯ ¯ˆ . o ı ¯ˆ . a o a a ¯ . a ¯i ˙ a ’ . aa . ¯ tri Γ t` u. V v`o 2V . V` vˆy, d` thi n`y c`n c´ thˆ’ k´ hiˆu l` G = (V, Γ). a ı a ¯o . a o o e ˆ ˙ y e a . . . 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 }. 1.1.3 D` thi vˆ hu.´.ng -ˆ . o 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 e u . ´ ´ ’ o o ınh a ˙ a ¯o . ˆ a ` ´ a u o . o a . .´.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` hu o ˙ a ’ u a o ` 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 ´ e u - ` e a ¯ ˙ a o ’ ˜ o ıt a ´ o . u ¯˙’ o tˆm dˆ a ¯e ´n th´. tu. cua ch´ng. 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 ˜ . u a o a o u . ´ a. o o u . (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 . ¯ o a ` a o a o ¯˜ . ˙ ’ . . . 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 e ` ınh . e . ¯ . e˙ ˜ e ˙ a ¯ . ’ ˙ ’ a a. a o c´ m˜i tˆn liˆn thuˆc hai d iˆ’m tu.o.ng u.ng hai d ınh vi v` vj . o u e 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` e u a ınh a o o ´ ˙ ¯o . ’ ˆ ¯ `e ˙ a a ’ . 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 tˆp c´c canh, t´ a o a u a a . u a ` a ˙ a o ’ ˜ ` a ˙ a o a ’ ¯˙’ . . . . . . phˆn biˆt hay d` ng nhˆ t cua V. a e. ¯ˆ o ´ ’ a ˙ 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 ¯ o ´ e o o o e a ¯˙’ a y o ` ´ e ´ o . 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. ınh -ˆ . o o o ´ ¯ˆ . o ınh 1.1.4 C´c d .nh ngh˜ ch´ a ¯i ıa ınh . . . a ` e ´ e u ´ o ¯˙ o ıt a . ’ ˙ ’ 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 a . . a ınh a `e ¯˙’ a . a ` e 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 . e o. u ı . ınh ¯˙ ’ a 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 e e thuˆc bo o. ˙.i canh e3 ), nhu.ng d ınh v2 v` v5 khˆng kˆ nhau. ’ . ¯ ˙ ’ a o ` e Bˆc v` nu.a bˆc a a ˙ . ’ 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 ˙ ¯˙ ’ ’ y e G. ´ e o . ` a a ˜ ´ a o a o ¯˙ ’ c´ d ınh v l` gˆ a o´c. Bˆc trong cua d ınh v ∈ V, k´ hiˆu d− (v) (hay d− (v) nˆu khˆng so. nhˆm a . ˙ ¯˙ ’ ’ y e G . ´ e o . ` a ˜ ´ o ¯˙ ’ lˆ n) l` sˆ c´c cung c´ d ınh v l` ngon. a a o a 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 e˙ e a ` o˙ a a . a ˙ a ¯˙ ’ ’ ` a o˙ a a . ˙ a ’ ¯˙’ a ` a o ´ o ˙ ¯o . ’ ˆ u.c l` d ınh v` bˇ ng tˆ’ng sˆ cung cua d` thi G, t´ a ˙ 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 . ˙ ¯˙ ’ ’ y e . ´ 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ˆ nhˆ a a ˜ a o´ a . e o ¯ . ˙ ’ o e ¯ . ¯e ´ ` a ı . ¯ˆ . o o hu.´.ng trong H` 1.2 c´ d(v2 ) = 3, d(v5 ) = 5. o ınh o a . e o a . . a ¯ˆ ´ C´c cung (canh) liˆn thuˆc tˆp A ⊂ V. C´c d oi chu tr` ı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 ˙ ˙ ’ ’ y e . . ´ ’ a a a ˙ a o ¯˙ ’ ´ o o . a ¯˙ ’ . . ´ ’ ´ c − . a a a a ˙ a o ¯˙’ . 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 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. a a . a . . o . . a ¯o ´ ınh ˙ ¯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 ´ ´ o e e ˜ o a . . o ´ . ´ o o . . .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 ´ e o e . ı u o a´ e cung dang (vj , vi ). . D` thi phan d oi x´.ng -ˆ . o ´ ˙ ¯ˆ u ’ 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 o . a ´ ˙ ¯o u ’ ´ e o . ı 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 o . a ¯ˆ ¯ ˙ e a ’ ´ ¯˙’ ´ a y 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 . Do ¯o . o o ˆ ¯ˆ ¯ ˙ ¯˙ ¯ . y e a n 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` ˙ ˙ ’ ’ -ˆ . o ¯ . ˙ a ’ . a ¯ˆ . o ¯o a ¯ ˙ ’ a 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 a a a ˙ ’ a ¯˙ ’ o e o A . thuˆc tˆp A. o a . . 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 o ˙ ’ a o - a . a o ¯o . ban d` giao thˆng cua th`nh phˆ D` Lat l` mˆt d` thi con. ´ . ˆ -ˆ . 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 e ¯ˆ . o a -ˆ . o a o . . ˙ a ’ . a ¯ˆ . o a ¯˙ o . ’ a a o . a ˙ ’ . a ˙ ’ v` c´c cung thuˆc U (c´c cung cua E \ U bi xo´ khoi G). -ˆ . 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 e ¯o . ˆ a -ˆ . o o a . . ˙ a ’ . a a ¯o . ˆ bˆ phˆn cu o a . . ˙ a GA sinh bo.i U. ’ ˙ ’ 1.2 Ma trˆn biˆ’u diˆn d` thi a . e˙ ˜ ¯ˆ . e o 1.2.1 Ma trˆn liˆn thuˆc d ˙nh-cung 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 = a e . o ¯˙ . ’ ˙ ¯o . ’ ˆ 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 1, 2, . . . , m, v´ a o `a ˙’ a ˜ o ¯´ o . e˙ ˜ e o ˙ ’ a o ˜ . ˙ ˜ o ¯˙ ´ ´ ’ . 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 ` ˙ ’ . ` a e e . ’ ˙’ e ı a ˙ a a ’ 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` ı . a e . o ¯˙ . ’ ˙ ¯o . ’ ˆ ınh 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...........................................................................e...1...........................................................................b •.................. . . ... . ... . . ...• ... . ... . ... . ... . . . ... ... ... ... . . ... ... .. . ... ... . . . ... ... ... ... ... ... ... ... .. . e4..................... ... ... . . . . . . . . . . ... ... .... . ... ... ... ... . . . ... ... ...... . . ... ... ...... . . ... ...... ...... ... . ... ... ...... .... . .. .... ... .. . .. ...... ....... ... ... ... . . . . . . . . . . e3 ... ... ... ... ....... .... . . . . . .... .... ..... ...... . . . .. . ... ... ... ...... . . . ... ... .. . .. ... ... . ... ... ... ... ... ... ... ... ... ... e2 ... . . . . . . . . . . .. ... . ... . .. .... ... ... . ... . ..... ... ... . ... . . .. ... • ................................................................................... ................................................................................. ... ... . .. .. .. • d e5 c 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 . ` ´ a a . o . a ´ e ¯. u ˙ ’ o a ` a . . ´ . 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 . 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. e . ¯ˆ e a e . o ¯˙ . ˙ ¯ˆ . ’ o 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 u u´ a` a e . o ¯˙ . ’ ˙ ¯o . ’ ˆ u ¯´ `a ˙ ’. 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 hai phˆn tu a o e ˜ . o o o ` a a o ` a ¯o o e u˙ . . minh theo quy nap nhu . 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˙ ´ ’ e a ˙ a a o o ´ ´ e a . . ˙ 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). ’ cu a ˙ ˙ ˙ ’ ’ ’ a ¯i ¯ ´ . a . o e´ a ´ 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. e a . o ´ a ˙ ’ e´ ˜ . o o ˙ ’ u ¯´ ` a ˙ ’ kh´c khˆng th` det(A ) = 0 (thˆt vˆy, tˆ a o ı a a o . . ˙ng tˆ t ca c´c h`ng cua A l` vector khˆng, do d ´ c´c ’ ´ ’ a ˙ a a ˙ ’ a o ¯o a a ¯o a . . e´n t´ h`ng l` d ˆc lˆp tuyˆ ınh). Nˆ o a ´u tˆn tai mˆt cˆt cua A khˆng c´ phˆn tu. kh´c khˆng th` e ` . o o . . ˙ ’ o o a ` ˙ ’ 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 ´ o u e ` . o ´ o . ˙ ’ o ¯´ o . ` a ˙ ’ 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 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 a a o ˙’ ´ e ` a . . . hay 0 v` do d ´ mˆnh d` d u . a ¯o e ¯ˆ ¯ e .o.c ch´.ng minh. u . 14
1.2.2 Ma trˆn liˆn thuˆc d ˙nh-canh 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 e ¯o . o ˆ o a e . o ¯˙ . ’ . ˙ ¯ˆ . ’ o a a . A = (aij ), i = 1, 2, . . . , n, j = 1, 2, . . . , m, v´ ao.i c´c phˆn tu. 0 v` 1, trong d ´ mˆ i cˆt biˆ’u diˆn ` a ˙ ’ a ˜ o ¯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 . . ˙ ’ a o a ˜ e˙ ˜ e o ¯˙ . ’ ˙ ’ a ´ e . e o . ¯˙’ a ´ ’ ı a ˙ a ` hai d ınh vi v` vj th` tˆ t ca c´c phˆn tu ˙ o a ˙ ’ .’. cua cˆt k bˇ ng khˆng ngoai tr`. ` 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` ı . a e . o ¯˙ . ’ . ˙ ¯o . ’ ˆ ınh 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..........................................................................e...1..........................................................................b •................ .. . .. . .. . ...• ... . ... . ... . ... .... . . . ... ... ... ... . ... ... .. ... ... . . ... ... ... ... ... ... ... ... .. . e4................... ... ... . . . . . . . . . . ... ... .... . ... ... ...... . . ... ... ...... . . ... ... ...... . . ... ... ... . . ... ...... ... ...... ... ... .. . .. ....... ........... ... . . . . . . . . . e3 ..... . ... ... . .. .... ... ... . . . .. . ... ... ... ...... ... . . . .. ... ... ... ... . . .. ... ... .... ... .. . ... ... . ... ... ... ... ... ... ... ... e2 . . . . . . . . . .. ... . ... ... . .. .... ... ... . ... . . .... ... .. . ... . • . ................................................................................. ... ................................................................................. .. . .. .. • d e5 c 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 a o a e . o ¯˙ . ’ o a e . o ¯˙ . ’ . o ˙ ’ total unimodular. Chˇng han, trong v´ du trˆn, ma trˆn con a . ı . e a.   1 1 0   1 0 1 0 1 1 c´ d inh th´.c bˇ ng −2. o ¯. u a ` 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 o o . a ` a ´ e o e ˙ a . a a ¯˙ . ’ V th`nh hai tˆp con r` a a o.i nhau V v` V sao cho d ˆi v´.i mˆ i canh (v , v ) ∈ E th` hoˇc a 2 ´ ¯o o ˜ o . ı a . 1 i j . vi ∈ V1 , vj ∈ V2 hoˇc vj ∈ V1 , vi ∈ V2 . a . 15
a. b •............................... .. . . . . . . •.. ..... .... ....... . ....... . . . . ... .... . ... ..... .... .. . .... .. . . ... ..... .... ... . .... ... . . . . . ... ... ... .... .... .... .. . .... .... .... ..... . . . . . . ... .... .... .... .... .. . . . . . ... .... .... . ...... ... . ... ... . . . . . . ... ... .... .... .......... .... ... . . . . . ... ... ......... ... . . . . . . ... ... ... ...... .. ..... ... ... . . . . . ... ....... ... .... . .... ..... .... .... . . . . . . . . .... ...... . .. . .. ..... ..... .... . . . . .. . . .. . . . . .. . .... ... .... .... .... ..... ... ....... . . . . . . .. . .... .... ... ... . ... ... .... .... .... . . . . ....... . . . .. .... ... ... ... ... .... .... . .... . . ....... . .. ... .... ... ... .... . ..... • . .. . • ... ... • .. . . c d e ınh -ˆ . H` 1.5: D` thi hai phˆn K2,3 . 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 e . ¯ˆe a . e o ¯˙ . . ˙ ¯ˆ . o ’ 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 o e u ˙ . a ` ˙ ’ o ¯˙ .c det(B) = 0, 1 hoˇc . . o a e . . ’ 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 ¯. 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 ¯´ o a a . o ´ a ˙ ˙ ’ ’ ˙ ’ a ¯i ¯´ o a a . o ´ trˆn vuˆng con cˆ p (k − 1). X´t ma trˆn vuˆng con B cˆ p k. 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` ´ e ˜ . o o ˙ ’ u ¯´ a ˙ ` ` ’ a ı 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` ¯´ a a a a . ’ ´ ˙ o ´ a . ˙ a a ¯˙ ’ . ’ a a vector h`ng cu a ˙ a B. C´c vector h`ng phu thuˆc tuyˆn t´ ’ a a . o . e´ ınh, nˆn det(B) = 0. 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 ´ e . . ` . o o ¯´ o . o. a ˙ ` ` ’ a ˙ ’ a . y e . a ¯ .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 a a o ı . . . 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 . a ˜ a e u ` a a e . o ¯˙ . ’ . ˙ ¯ˆ . a o ’ o . ınh ¯ˆ a ˙ u’ .c l` sˆ canh trˆn chu tr` l` le-xem Phˆn 1.3) c´ d inh th´.c bˇ ng ±2. Do tr` d o d`i le (t´ a o . ´ e ınh a ˙’ `a o ¯. u ` 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. ¯´ o u ınh ¯ˆ a ˙ a ı a o a . ’ . ` a ˙ e 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 ˆ ˙ e o ¯ˆ -ˆ . o o o a ` ´ a e a ˙ e ´ 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 : u - ` e e ` . a ¯ . a . a a V = V2 ∪ V2 , V1 ∩ V2 = ∅. 16
˙ ’ e ` . ´ o o . ınh o ¯o a ˙ . ’ Gia thiˆt tˆn tai mˆt chu tr` c´ d ˆ d`i le µ = {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 a o ´ a ınh o ˙ a a ´ a ` a e ¯˙ ’ e ´ e e ınh ˙ o 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 , . . . , o . ¯´ a o ˙ a ´ e ˙ a ’ ´ e a˜ 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 ınh o ¯o a ˙ e . ’ viq ∈ V1 v` bo . a ˙.i vˆy vi1 ∈ V2 . Diˆu n`y mˆu thuˆn v´.i V1 ∩ V2 = ∅. ’ a - ` e a a ˜ o 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 a y a . a a a o a ¯´ 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 a . o a ˙ ’ ´ ’ a ˙ a ¯˙’ e .i d ınh v . ` o ’ d ınh kˆ v´ ¯˙ 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 ˙ a ¯ ˙ ¯a ¯ . a ’ a a ¯˙’ a y ` ´ e o a a o . mang dˆ ´u + v` mˆt mang dˆ u −); hoˇc a a o . ´ 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 o . ¯ˇ. . ´ ’ a a a ˙ a ¯˙ ’ ¯ . a a a a a a . ´ ˙ 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 ca c´c d ınh d u . a a ´ ’ a ˙ a . e o u a a ¯˙ ’ o a . . 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 . o a . `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 ¯˙ ¯´ o ’ ¯ . a a a e ´ a a u i a e ´ 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 . o a . e 2 a ¯o o a 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 a u a e´ 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 ´ e ınh ¯ . u ¯˙’ ´ ’ ¯e ¯ ˙ ¯´ ¯ . . . ` 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 vˆ . e o ¯o a . ˙ - ` ’ e a a ˜ o a ˙ ’ ´ a e ¯o o ˙ ’ e ˙ o ho .p (b). Dinh l´ d u.o.c ch´.ng minh. -. y ¯ . u . 1.2.3 a ` Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ˙nh-d ˙nh . 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 ˙ ˙ ’ ’ a ¯o . ˆ o `e a´ o . e o . ¯˙’ ´ a y a a ` . e a e . o ¯˙ ¯˙ . ’ ’ a 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 17
v´.i c´c phˆn tu. 0 hoˇc 1: o a ` a ˙ ’ a . 1 ´ nˆu (vi , vj ) ∈ E, e aij := 0 nˆu ngu.o.c lai. ´ 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 o . ¯o . o o ˆ a ` ˙ ¯ . e ’ ¯o . u ˆ ˙ o e ¯ . ¯i ıa ` a ˜ ngh˜ bˇ ng c´ch xem mˆ i canh (vi , vj ) tu a o . .o.ng u.ng hai cung (v , v ) v` (v , v ). Trong tru.`.ng ´ a j i o i j .p n`y, ma trˆn kˆ l` d oi x´.ng. ho a a e ` a ¯ˆ u ´ . . 1.2.4 C´c biˆ’u diˆn cua d` thi 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 o a e˙ ˜ e a o ¯e ˙ lˆp tr` a ınh, n´i chung c´c biˆ’u diˆn n`y khˆng tu o a e˙ ˜ e a o .o.ng d u.o.ng theo kh´ canh hiˆu qua cua ¯ ıa . e ˙ ˙ ’ ’ . . thuˆt to´n. a . a C´ hai c´ch biˆ’u diˆn ch´ o a e˙ ˜ e ınh: Th´. nhˆ t, su. dung ma trˆn kˆ hoˇc c´c dˆ n xuˆ t cua u a´ ˙ . ’ a ` . e a a a . ˜ ´ ’ a ˙ n´; th´ o u. hai, su. dung ma trˆn liˆn thuˆc hoˇc c´c dˆn xuˆ t cua n´. ˙ . ’ a e o a a a ˜ ´ ’ a ˙ o . . . 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 u e ` ´ a a a ` . e e e ˙ a a ’ . ¯ˆ . ¯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 c´c d o ¯o . o o a ¯ ˆ o a e˙ ˜ ¯o . e ˆ a ` e ´ ´ a o . 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 u a a ˙ o e ¯ . e . ´ a u y a ¯ˆ a ˙ u ’ . (t´.c l` sˆ c´c bit trong mˆt t`. m´y t´ 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 t`. 1 . Do d o sˆ c´c t`. dˆ’ lu.u tr˜. a ` o e ¯ . . e ˙ ´ e o a . u ´ ¯´ o a u ¯e ˙ u ma trˆn kˆ a a e . ` l` n n/w . 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 e ˙ ` ’ a u ˙ ’ a e ˙ o a ’ ¯´ ˙ a ’ ` n n(n − 1)/2 bit. Tuy nhiˆn, v´.i c´ch lu.u tr˜. n`y, s˜ tˇng d ˆ ph´.c cua n´, v` do d o chı cˆ e o a u a e a ¯o u . tap v` th`.i gian t´ to´n trong mˆt sˆ b`i to´n. . a o ınh a ´ o o a a . Trong tru.`.ng ho.p c´c ma trˆn thu.a (m o . a a . n2 v´.i d` thi c´ hu.´.ng; m o ¯o . o o ˆ 1 2 ´ n(n + 1) d ˆi ¯o .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 v´ ¯ˆ . o o o o a ˜ e ˜ a a a e ı. ¯´ e ım a e˙ ˜ e ˙ a ’ 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´ ı . ¯ıch a e ˙ . ’ o . ˙ ’ a ` e ¯o . 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 ¯˙ ˜ ` ˙ ˙ mˆi con tro tu o ´ . ’ ¯ˆ . o o o o a ’ ’ ˙ ’ ˙ 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 chı ´ o u ¯a . ˆ u . u e . ˙ u ’ ´ ¯ ˙’ a u o. ˙ ’ 1 K´ hiˆu x l` sˆ nguyˆn nho nhˆ t khˆng b´ ho.n x. y e . a o´ e ˙ ’ a ´ 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). ’ ´ ˙ ¯e o . a ´ ’ e e ˙ a ¯˙ ’ ` ¯˙ ¯ . o o e ’ ´ o u ˜ o u ` o .`.ng: 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` o ´ o e ´ . u o e ˙ ¯˙ ’ ’ ` a e 2. Tru.`.ng liˆn kˆt chı dˆn n´t kˆ tiˆp trong danh s´ch kˆ n`y. o e e ´ ’ ´ ˙ ¯e u e e ´ ´ a ` 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 a e˙ ˜ e ˙ ’ a `e ˙ ¯ˆ . o o ’ o ınh ¯ . cho tu.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` ´ ınh ˙ ˙ a ’ ’ ˙ ’ . u e . ´ a ¯ u . a A, B, C, D, E, F ). N´t . d` u u ¯ˆ a . . . . . . . . . . . . V out[1] ............... . .. .............. .. A . . . . . . . . . • . . ...................... ..................... . . v4 . . . . . . . . . • . . ...................... ..................... . . v5 . . . . . . . . . •............................................. NULL . . . . . . . . . . . . . . . . . . . . . . . . . . •............................................ v1 •............................................ v3 . . . V out[2].................................. B . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . •............................................. NULL . . . . . . . . . . . . . •............................................ v3 . . V out[3].................................. C . . . . . . . . .. . . . . . . . . . •............................................ NULL .. . . . . . . . . . . . . . . . . . •.............................................. v2 •.............................................. v3 . . . V out[4]................................. D . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . •............................................... NULL . . . . . . . . . . . . . . . . . . . . V out[5]................................... E . . . . . . . . . •............................................. v3 .. . . . . . . . . . . •............................................. v6 .. . . . . . . . . . . •.............................................. NULL . . . . . . . . . . . . . . . . •............................................ v1 . . V out[6].................................. F . . . . . . . . . .. . . . . . . . . . . •............................................ NULL .. . . . 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 o . a a ¯˙ ’ u ¯ ’ ´ ˙ ¯e a ¯˙ ¯ ¯e ’ ´ danh s´ch c´c d ınh d i dˆn vi v` do d o c´ thˆ a a ¯´ o e ˙ lu.u tr˜. d` thi thˆng qua mang c´c danh s´ch ’ u ¯o . o ˆ ˙ ’ a a 19