http://www.ebook.edu.vn
Mu
.c lu
.c
L`o
.i n´oi d¯ˆa
`u 7
1 D
-a
.i cu
.o
.ng vˆe
`d¯ˆo
`thi
.9
1.1 D
-i
.nh ngh˜ıa v`a c´ac kh´ai niˆe
.m........................... 9
1.1.1 D
-ˆo
`thi
.c´o hu
.´o
.ng.............................. 9
1.1.2 D
-ˆo
`thi
.v`a ´anh xa
.d¯a tri
........................... 10
1.1.3 D
-ˆo
`thi
.vˆo hu
.´o
.ng ............................. 10
1.1.4 C´ac d¯i
.nhngh˜ıach´ınh........................... 11
1.2 Ma trˆa
.n biˆe
˙’u diˆe
˜n d¯ˆo
`thi
.............................. 13
1.2.1 Ma trˆa
.n liˆen thuˆo
.c d¯ı
˙’nh-cung ...................... 13
1.2.2 Ma trˆa
.n liˆen thuˆo
.c d¯ı
˙’nh-ca
.nh ...................... 15
1.2.3 Ma trˆa
.n kˆe
`hay ma trˆa
.n liˆen thuˆo
.c d¯ı
˙’nh-d¯ı
˙’nh ............. 17
1.2.4 C´ac biˆe
˙’u diˆe
˜n cu
˙’a d¯ˆo
`thi
.......................... 18
1.3 T´ınhliˆenthˆong .................................. 23
1.3.1 Dˆay chuyˆe
`nv`achutr`ınh......................... 23
1.3.2 D
-u
.`o
.ng d¯i v`a ma
.ch ............................ 24
1.3.3 T´ınhliˆenthˆong.............................. 24
1
http://www.ebook.edu.vn
1.3.4 Cˆa
`u, k−liˆenthˆong ............................ 28
1.3.5 D
-ˆo
`thi
.liˆen thˆong ma
.nh.......................... 31
1.4 Pha
.m vi v`a liˆen thˆong ma
.nh........................... 33
1.4.1 Ma trˆa
.n pha
.mvi ............................. 33
1.4.2 T`ım c´ac th`anh phˆa
`n liˆen thˆong ma
.nh.................. 36
1.4.3 Co.so.
˙’ ................................... 39
1.5 D
-ˇa
˙’ng cˆa
´u cu
˙’a c´ac d¯ˆo
`thi
.............................. 41
1.5.1 1−d¯ˇa
˙’ng cˆa
´u................................ 42
1.5.2 2−d¯ˇa
˙’ng cˆa
´u................................ 43
1.6 C´ac d¯ˆo
`thi
.d¯ˇa
.c biˆe
.t................................ 46
1.6.1 D
-ˆo
`thi
.khˆong c´o ma
.ch .......................... 46
1.6.2 D
-ˆo
`thi
.phˇa
˙’ng ............................... 46
2 C´ac sˆo
´co
.ba
˙’n cu
˙’a d¯ˆo
`thi
.49
2.1 Chu sˆo
´....................................... 49
2.2 Sˇa
´c sˆo
´....................................... 52
2.2.1 C´ach t`ım sˇa
´c sˆo
´.............................. 54
2.3 Sˆo
´ˆo
˙’n d¯i
.nhtrong ................................. 55
2.4 Sˆo
´ˆo
˙’n d¯i
.nhngo`ai ................................. 61
2.5 Phu
˙’ ........................................ 65
2.6 Nhˆan cu
˙’a d¯ˆo
`thi
................................... 69
2.6.1 C´ac d¯i
.nh l´y vˆe
`tˆo
`n ta
.i v`a duy nhˆa
´t ................... 69
2.6.2 Tr`o cho
.iNim ............................... 72
2
http://www.ebook.edu.vn
3 C´ac b`ai to´an vˆe
`d¯u
.`o
.ng d¯i 75
3.1 D
-u
.`o
.ng d¯i gi˜u
.a hai d¯ı
˙’nh ............................. 75
3.1.1 D
-u
.`o
.ng d¯i gi˜u
.a hai d¯ı
˙’nh ......................... 75
3.1.2 D
-ˆo
`thi
.liˆen thˆong ma
.nh.......................... 76
3.2 D
-u
.`o
.ng d¯i ngˇa
´n nhˆa
´t gi˜u
.a hai d¯ı
˙’nh ....................... 78
3.2.1 Tru
.`o
.ng ho
..p ma trˆa
.n tro
.ng lu
.o
..ng khˆong ˆam . . . . . . . . . . . . . . 78
3.2.2 Tru
.`o
.ng ho
..p ma trˆa
.n tro
.ng lu
.o
..ngtu`y´y................. 82
3.3 D
-u
.`o
.ng d¯i ngˇa
´n nhˆa
´t gi˜u
.a tˆa
´t ca
˙’ c´ac cˇa
.p d¯ı
˙’nh ................. 87
3.3.1 Thuˆa
.t to´an Hedetniemi (tru
.`o
.ng ho
..p ma trˆa
.n tro
.ng lu
.o
..ng khˆong ˆam) 88
3.3.2 Thuˆa
.t to´an Floyd (tru
.`o
.ng ho
..p ma trˆa
.n tro
.ng lu
.o
..ng tu`y ´y) . . . . . . 93
3.4 Ph´at hiˆe
.n ma
.ch c´o d¯ˆo
.d`aiˆam .......................... 96
3.4.1 Ma
.ch tˆo
´i u
.u trong d¯ˆo
`thi
.c´o hai tro
.ng lu
.o
..ng.............. 96
4 C ˆ
AY 99
4.1 Mo.
˙’ d¯ˆa
`u ...................................... 99
4.2 CˆayHuffman ................................... 101
4.2.1 C´ac bˆo
.m˜a “tˆo
´t” ............................. 101
4.2.2 M˜aHuffman................................ 103
4.3 Cˆaybaotr`um................................... 105
4.3.1 Thuˆa
.t to´an t`ım kiˆe
´m theo chiˆe
`u rˆo
.ng x´ac d¯i
.nh cˆay bao tr`um . . . . . 107
4.3.2 Thuˆa
.t to´an t`ım kiˆe
´m theo chiˆe
`u sˆau x´ac d¯i
.nh cˆay bao tr`um . . . . . 107
4.3.3 T`ım cˆay bao tr`um du
..a trˆen hai ma
˙’ng tuyˆe
´n t´ınh . . . . . . . . . . . 108
4.3.4 Thuˆa
.t to´an t`ım tˆa
´t ca
˙’ c´ac cˆay bao tr`um . . . . . . . . . . . . . . . . 112
4.3.5 Hˆe
.co.so.
˙’ cu
˙’a c´ac chu tr`ınh d¯ˆo
.c lˆa
.p ................... 112
3
http://www.ebook.edu.vn
4.4 Cˆay bao tr`um tˆo
´i thiˆe
˙’u.............................. 114
4.4.1 Thuˆa
.tto´anKruskal ........................... 116
4.4.2 Thuˆa
.tto´anPrim ............................. 119
4.4.3 Thuˆa
.t to´an Dijkstra-Kevin-Whitney . . . . . . . . . . . . . . . . . . 121
4.5 B`aito´anSteiner.................................. 122
5 B`ai to´an Euler v`a b`ai to´an Hamilton 127
5.1 B`aito´anEuler................................... 127
5.1.1 Thuˆa
.t to´an t`ım dˆay chuyˆe
`nEuler.................... 129
5.2 B`ai to´an ngu
.`o
.i d¯u
.a thu
.TrungHoa....................... 131
5.3 B`aito´anHamilton ................................ 135
5.3.1 C´ac d¯iˆe
`u kiˆe
.n cˆa
`n d¯ˆe
˙’ tˆo
`n ta
.i chu tr`ınh Hamilton . . . . . . . . . . . . 138
5.3.2 C´ac d¯iˆe
`u kiˆe
.n d¯u
˙’ vˆe
`su
..tˆo
`n ta
.i chu tr`ınh Hamilton . . . . . . . . . . 139
5.3.3 C´ac d¯iˆe
`u kiˆe
.n d¯u
˙’ vˆe
`su
..tˆo
`n ta
.i ma
.ch Hamilton . . . . . . . . . . . . . 142
6 D
-ˆo
`thi
.phˇa
˙’ ng 149
6.1 D
-i
.nh ngh˜ıa v`a c´ac v´ı du
.............................. 149
6.2 C´ac biˆe
˙’u diˆe
˜n kh´ac nhau cu
˙’a mˆo
.t d¯ˆo
`thi
.phˇa
˙’ng ................ 151
6.3 C´ac t´ınh chˆa
´t cu
˙’a d¯ˆo
`thi
.phˇa
˙’ng ......................... 154
6.4 Ph´at hiˆe
.n t´ınh phˇa
˙’ng............................... 157
6.4.1 Kiˆe
˙’m tra t´ınh phˇa
˙’ng ........................... 161
6.5 D
-ˆo
´i ngˆa
˜u h`ınh ho
.c ................................ 167
6.6 D
-ˆo
´i ngˆa
˜u tˆo
˙’ ho
..p ................................. 170
7 Ma
.ng vˆa
.n ta
˙’i 173
4
http://www.ebook.edu.vn
7.1 Mo.
˙’ d¯ˆa
`u ...................................... 173
7.2 B`ai to´an luˆo
`ng l´o
.n nhˆa
´t ............................. 174
7.2.1 Thuˆa
.t to´an g´an nh˜an d¯ˆe
˙’ t`ım luˆo
`ng l´o
.n nhˆa
´t .............. 180
7.2.2 D
-ˆo
`thi
.d¯iˆe
`u chı
˙’nh luˆo
`ng.......................... 181
7.2.3 Phˆan t´ıch luˆo
`ng.............................. 182
7.3 C´ac ca
˙’i biˆen d¯o
.n gia
˙’n cu
˙’a b`ai to´an luˆo
`ng l´o
.n nhˆa
´t............... 183
7.3.1 C´ac d¯ˆo
`thi
.c´o nhiˆe
`u nguˆo
`n v`a nhiˆe
`ud¯´ıch................ 183
7.3.2 C´ac d¯ˆo
`thi
.v´o
.i r`ang buˆo
.c ta
.i c´ac cung v`a d¯ı
˙’nh............. 184
7.3.3 C´ac d¯ˆo
`thi
.c´o cˆa
.n trˆen v`a cˆa
.n du
.´o
.i vˆe
`luˆo
`ng .............. 185
7.4 Luˆo
`ng v´o
.i chi ph´ı nho
˙’ nhˆa
´t ........................... 186
7.4.1 Thuˆa
.t to´an Klein, Busacker, Gowen . . . . . . . . . . . . . . . . . . . 186
7.5 Cˇa
.pgh´ep ..................................... 189
7.5.1 C´ac b`ai to´an vˆe
`cˇa
.pgh´ep ........................ 189
7.5.2 Cˇa
.p gh´ep l´o
.n nhˆa
´t trong d¯ˆo
`thi
.hai phˆa
`n................ 192
7.5.3 Cˇa
.p gh´ep ho`an ha
˙’o trong d¯ˆo
`thi
.hai phˆa
`n ............... 193
A Thu
.viˆe
.n Graph.h 197
T`ai liˆe
.u tham kha
˙’o 209
5