Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Đồ thị và các thuật toán
Nội dung xem thử
Mô tả chi tiết
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
.nh ngh˜ıa ch´ı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´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.1 Dˆay chuyˆe` n v`a chu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.2 D- u
.`o
.ng d¯i v`a ma. ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3.3 T´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1
http://www.ebook.edu.vn
1.3.4 Cˆa`u, k−liˆen thˆ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.m vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
.nh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4 Sˆo´ ˆo˙’n d¯i
.nh ngo`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.
i Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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.
.ng tu`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 CAYˆ 99
4.1 Mo.
˙’ d¯ˆa`u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2 Cˆay Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.2.1 C´ac bˆo. m˜a “tˆo´t” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.2.2 M˜a Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.3 Cˆay bao tr`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.
t to´an Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.4.2 Thuˆa.
t to´an Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.4.3 Thuˆa.
t to´an Dijkstra-Kevin-Whitney . . . . . . . . . . . . . . . . . . 121
4.5 B`ai to´an Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5 B`ai to´an Euler v`a b`ai to´an Hamilton 127
5.1 B`ai to´an Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.1.1 Thuˆa.
t to´an t`ım dˆay chuyˆe` n Euler . . . . . . . . . . . . . . . . . . . . 129
5.2 B`ai to´an ngu.`o
.
i d¯u.a thu. Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . 131
5.3 B`ai to´an Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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` u d¯´ı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.p gh´ep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
7.5.1 C´ac b`ai to´an vˆe` cˇa.p gh´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
6
http://www.ebook.edu.vn
http://www.ebook.edu.vn
L`o.
i n´oi d¯ˆa`
u
Trong thu.
. c tˆe´ d¯ˆe˙’ miˆeu ta˙’ mˆo.
t sˆo´ t`ınh huˆo´ng ngu.`o
.
i ta thu.`o
.ng biˆe˙’u thi
. bˇa`ng mˆo.
t h`ınh a˙’nh
gˆo`m c´ac d¯iˆe˙’m (c´ac d¯ı˙’nh)-biˆe˙’u diˆe˜n c´ac thu.
. c thˆe˙’-v`a v˜e c´ac d¯oa.n thˇa˙’ng nˆo´i cˇa.p c´ac d¯ı˙’nh biˆe˙’u
diˆe˜n mˆo´i quan hˆe. gi˜u.a ch´ung. Nh˜u.ng h`ınh nhu.
thˆe´ thu.`o
.ng go.
i l`a c´ac d¯ˆo` thi
.
. Mu. c d¯´ıch cu˙’a
gi´ao tr`ınh n`ay cung cˆa´p nh˜u.ng kiˆe´n th´u.
c co. ba˙’n d¯ˆe˙’ nghiˆen c´u.u c´ac d¯ˆo` thi
.
. C´ac d¯ˆo` thi
. xuˆa´t
hiˆe.n trong nhiˆe` u l˜ınh vu.
. c v´o.
i c´ac tˆen go.
i kh´ac nhau: “cˆa´u tr´uc” trong cˆong tr`ınh xˆay du.
. ng,
“ma. ch” trong d¯iˆe.n tu.
˙’ , “lu.o
.
. c d¯ˆo` quan hˆe.”, “cˆa´u tr´uc truyˆe` n thˆong”, “cˆa´u tr´uc tˆo˙’ ch´u.
c”
trong x˜a hˆo.
i v`a kinh tˆe´, “cˆa´u tr´uc phˆan tu.
˙’ ” trong ho´a ho. c, vˆan vˆan.
Do nh˜u.ng ´u.ng du. ng rˆo.ng r˜ai cu˙’a n´o trong nhiˆe` u l˜ınh vu.
. c, c´o rˆa´t nhiˆe` u nghiˆen c´u.u
xung quanh l´y thuyˆe´t d¯ˆo` thi
.
trong nh˜u.ng nˇam gˆa`n d¯ˆay; mˆo.
t nhˆan tˆo´ chu˙’ yˆe´u g´op phˆa`n th´uc
d¯ˆa˙’y su.
. ph´at triˆe˙’n d¯´o l`a xuˆa´t hiˆe.n c´ac m´ay t´ınh l´o.n c´o thˆe˙’ thu.
. c hiˆe.n nhiˆe` u ph´ep to´an v´o.
i
tˆo´c d¯ˆo.
rˆa´t nhanh. Viˆe.c biˆe˙’u diˆe˜n tru.
. c tiˆe´p v`a chi tiˆe´t c´ac hˆe.
thˆo´ng thu.
. c tˆe´, chˇa˙’ng ha.n c´ac
ma.ng truyˆe` n thˆong, d¯˜a d¯u.a d¯ˆe´n nh˜u.ng d¯ˆo` thi
. c´o k´ıch thu.´o
.
c l´o.n v`a viˆe.c phˆan t´ıch th`anh
cˆong hˆe.
thˆo´ng phu.
thuˆo. c rˆa´t nhiˆe` u v`ao c´ac thuˆa.
t to´an “tˆo´t” c˜ung nhu. kha˙’ nˇang cu˙’a m´ay
t´ınh. Theo d¯´o, gi´ao tr`ınh n`ay s˜e tˆa.p trung v`ao viˆe.c ph´at triˆe˙’n v`a tr`ınh b`ay c´ac thuˆa.
t to´an
d¯ˆe˙’ phˆan t´ıch c´ac d¯ˆo` thi
.
.
C´ac phu.o
.ng ph´ap phˆan t´ıch v`a thiˆe´t kˆe´ c´ac thuˆa.
t to´an trong gi´ao tr`ınh cho ph´ep sinh
viˆen c´o thˆe˙’ viˆe´t dˆe˜ d`ang c´ac chu.o
.ng tr`ınh minh ho.a. Gi´ao tr`ınh d¯u.o
.
. c biˆen soa.n cho c´ac d¯ˆo´i
tu.o
.
. ng l`a sinh viˆen To´an-Tin v`a Tin ho. c.
Gi´ao tr`ınh su.
˙’ du.ng ngˆon ng˜u. C d¯ˆe˙’ minh ho.a, tuy nhiˆen c´o thˆe˙’ dˆe˜ d`ang chuyˆe˙’n d¯ˆo˙’i
sang c´ac ngˆon ng˜u. kh´ac; v`a do d¯´o, sinh viˆen cˆa`n c´o mˆo.
t sˆo´ kiˆe´n th´u.
c vˆe` ngˆon ng˜u. C. Ngo`ai
ra, hˆa`u hˆe´t c´ac chu.o
.ng tr`ınh thao t´ac trˆen cˆa´u tr´uc d˜u.
liˆe.u nhu. danh s´ach liˆen kˆe´t, nˆen d¯`oi
ho˙’i sinh viˆen pha˙’i c´o nh˜u.ng k˜y nˇang lˆa.p tr`ınh tˆo´t.
Gi´ao tr`ınh bao gˆo`m ba˙’y chu.o
.ng v`a mˆo.
t phˆa`n phu.
lu. c v´o.
i nh˜u.ng nˆo.
i dung ch´ınh nhu.
sau:
• Chu.o
.ng th´u. nhˆa´t tr`ınh b`ay nh˜u.ng kh´ai niˆe.m cˇan ba˙’n vˆe` d¯ˆo` thi
.
.
• Chu.o
.ng 2 tr`ınh b`ay nh˜u.ng sˆo´ co. ba˙’n cu˙’a d¯ˆo` thi
.
. Y ngh˜ıa thu ´ .
. c tiˆe˜n cu˙’a c´ac sˆo´ n`ay.
7
http://www.ebook.edu.vn
• Chu.o
.ng 3 t`ım hiˆe˙’u b`ai to´an t`ım d¯u.`o
.ng d¯i ngˇa´n nhˆa´t.
• Chu.o
.ng 4 d¯ˆe` cˆa.p d¯ˆe´n kh´ai niˆe.m vˆe` cˆay. U´
.
ng du. ng cu˙’a cˆay Huffman trong n´en d˜u.
liˆe.u. Ngo`ai ra xˆay du.
. ng c´ac thuˆa.
t to´an t`ım cˆay bao tr`um nho˙’ nhˆa´t.
• B`ai to´an Euler v`a b`ai to´an Hamilton v`a nh˜u.ng mo.
˙’ rˆo.ng cu˙’a ch´ung s˜e d¯u.o
.
. c n´oi d¯ˆe´n
trong Chu.o
.ng 5.
• Chu.o
.ng 6 nghiˆen c´u.u c´ac t´ınh chˆa´t phˇa˙’ng cu˙’a d¯ˆo` thi
.
; v`a cuˆo´i c`ung
• Chu.o
.ng 7 t`ım hiˆe˙’u c´ac b`ai to´an trˆen ma.ng vˆa.n ta˙’i.
Ngo`ai ra, phˆa`n phu.
lu. c tr`ınh b`ay c´ac cˆa´u tr´uc d˜u.
liˆe.u v`a nh˜u.ng thu˙’ tu. c cˆa`n thiˆe´t d¯ˆe˙’
d¯o.n gia˙’n ho´a c´ac d¯oa.n chu.o
.ng tr`ınh minh ho.a c´ac thuˆa.
t to´an d¯u.o
.
. c tr`ınh b`ay.
Gi´ao tr`ınh d¯u.o
.
. c biˆen soa.n lˆa`n d¯ˆa`u tiˆen nˆen khˆong tr´anh kho˙’i kh´a nhiˆe` u thiˆe´u s´ot. T´ac
gia˙’ mong c´o nh˜u.ng d¯´ong g´op t`u. ba.n d¯o. c.
Tˆoi xin ca˙’m o.n nh˜u.ng gi´up d¯˜o. d¯˜a nhˆa.n d¯u.o
.
. c t`u. nhiˆe` u ngu.`o
.
i m`a khˆong thˆe˙’ liˆe.
t kˆe
hˆe´t, d¯ˇa. c biˆe.
t l`a c´ac ba.n sinh viˆen, trong qu´a tr`ınh biˆen soa.n gi´ao tr`ınh n`ay.
D- `a La.
t, ng`ay 5 th´ang 3 nˇam 2002
PHA. M Tiˆe´n So.n
8
http://www.ebook.edu.vn
Chu.o
.ng 1
D- a.
i cu.o
.ng vˆe` d¯ˆo` thi
.
1.1 D- i
.nh ngh˜ıa v`a c´ac kh´ai niˆe.m
1.1.1 D- `ˆo thi
.
c´o hu.´o
.ng
D- `ˆo thi
. c´o hu.´o
.ng G = (V, E) gˆo`m mˆo.
t tˆa.p V c´ac phˆa`n tu.
˙’ go.
i l`a d¯ı˙’nh (hay n´ut) v`a mˆo.
t tˆa.p
E c´ac cung sao cho mˆo˜i cung e ∈ E tu.o
.ng ´u.ng v´o.
i mˆo.
t cˇa.p c´ac d¯ı˙’nh d¯u.o
.
. c sˇa´p th´u.
tu.
.
. Nˆe´u
c´o d¯´ung mˆo.
t cung e tu.o
.ng ´u.ng c´ac d¯ı˙’nh d¯u.o
.
. c sˇa´p th´u.
tu.
.
(a, b), ta s˜e viˆe´t e := (a, b).
Ch´ung ta s˜e gia˙’ su.
˙’ c´ac d¯ı˙’nh d¯u.o
.
. c d¯´anh sˆo´ l`a v1, v2, . . . , vn hay gia˙’n tiˆe.n, 1, 2, . . . , n,
trong d¯´o n = #V l`a sˆo´ c´ac d¯ı˙’nh cu˙’a d¯ˆo` thi
.
.
Nˆe´u e l`a mˆo.
t cung tu.o
.ng ´u.ng cˇa.p c´ac d¯ı˙’nh d¯u.o
.
. c sˇa´p th´u.
tu.
. vi v`a vj th`ı d¯ı˙’nh vi go.
i l`a
gˆo´c v`a d¯ı˙’nh vj go.
i l`a ngo. n; cung e go.
i l`a liˆen thuˆo. c hai d¯ı˙’nh vi v`a vj
. Ch´ung ta s˜e thu.`o
.ng
k´y hiˆe.u m = #E−sˆo´ ca.nh cu˙’a d¯ˆo` thi
. G. C´ac ca.nh thu.`o
.ng d¯u.o
.
. c d¯´anh sˆo´ l`a e1, e2, . . . , em.
Mˆo.
t c´ach h`ınh ho. c, c´ac d¯ı˙’nh d¯u.o
.
. c biˆe˙’u diˆe˜n bo.
˙’ i c´ac d¯iˆe˙’m, v`a e = (vi
, vj ) d¯u.o
.
. c biˆe˙’u
diˆe˜n bo.
˙’ i mˆo.
t cung nˆo´i c´ac d¯iˆe˙’m vi v`a vj
.
Mˆo.
t cung c´o gˆo´c tr`ung v´o.
i ngo.n go.
i l`a khuyˆen.
Nˆe´u c´o nhiˆe` u ho.n mˆo.
t cung v´o.
i gˆo´c ta.
i vi v`a ngo.n ta.
i vj th`ı G go.
i l`a d¯a d¯ˆo` thi
. v`a c´ac
cung tu.o
.ng ´u.ng go.
i l`a song song. D- o
.n d¯ˆo` thi
. c´o hu.´o
.ng l`a d¯ˆo` thi
. khˆong khuyˆen trong d¯´o hai
d¯ı˙’nh bˆa´t k`y vi v`a vj c´o nhiˆe` u nhˆa´t mˆo.
t cung (vi
, vj ). Chˇa˙’ng ha.n, d¯ˆo` thi
.
trong H`ınh 1.1 c´o
cung e8 l`a khuyˆen; c´ac cung e4 v`a e9 l`a song song do c`ung tu.o
.ng ´u.ng cˇa.p d¯ı˙’nh v3 v`a v4.
9
http://www.ebook.edu.vn
......... ...............................................................................................................................................
....
..............
.
.
............................................................................................................................................... ..........
...
..........
.... ...............................................................................................................................................
............................................................................................................................................... ............................................................................................................................
.
...........
.....
........
...
.
. .
.
....... .
.............
......
.
.
.
.
......................................................................................................................................................................................................................................................................................
...
......
........
..........
............
................
......................
........................................... ...................................................... .......... ................
......................
................
............
..........
........
......
....
.................................... ..........
...
..........
....
.................................... ..........
...
..........
....
v1
v2 v3
v4
v5
e1 e2
e3
e4
e5
e6 e7
e8
e9
•
• •
•
•
H`ınh 1.1: V´ı du. cu˙’a 2−d¯ˆo` thi
. c´o hu.´o
.ng.
1.1.2 D- `ˆo thi
. v`a ´anh xa. d¯a tri
.
V´o.
i mˆo˜i x ∈ V, k´y hiˆe.u Γ(x) := {y ∈ V | (x, y) ∈ E}. Khi d¯´o ta c´o mˆo.
t ´anh xa. d¯a tri
.
Γ: V → 2
V
, x 7→ Γ(x). K´y hiˆe.u Γ−1
l`a ´anh xa.
(d¯a tri.
) ngu.o
.
. c cu˙’a Γ.
Nˆe´u G l`a d¯o.n d¯ˆo` thi
.
, th`ı d¯ˆo` thi
. n`ay ho`an to`an d¯u.o
.
. c x´ac d¯i
.nh bo.
˙’ i tˆa.p V v`a ´anh xa. d¯a
tri
. Γ t`u. V v`ao 2V
. V`ı vˆa.y, d¯ˆo` thi
. n`ay c`on c´o thˆe˙’ k´y hiˆe.u l`a G = (V, Γ).
Nˆe´u xo´a cung e9 trong H`ınh 1.1 ta nhˆa.n d¯u.o
.
. c d¯o.n d¯ˆo` thi
. v`a do d¯´o c´o thˆe˙’ biˆe˙’u diˆe˜n
bo.
˙’ i ´anh xa. d¯a tri
. Γ. Trong tru.`o
.ng ho.
. p n`ay ta c´o
Γ(v1) = {v2}, Γ(v2) = {v1, v3}, Γ(v3) = {v4, v5}, Γ(v4) = {v5}, Γ(v5) = {v1, v5}.
1.1.3 D- `ˆo thi
. vˆo hu.´o
.ng
Khi nghiˆen c´u.u mˆo.
t sˆo´ t´ınh chˆa´t cu˙’a c´ac d¯ˆo` thi
.
, ta thˆa´y rˇa`ng ch´ung khˆong phu.
thuˆo. c v`ao
hu.´o
.ng cu˙’a c´ac cung, t´u.
c l`a khˆong cˆa`n phˆan biˆe.
t su.
. kh´ac nhau gi˜u.a c´ac d¯iˆe˙’m bˇa´t d¯ˆa`u v`a
kˆe´t th´uc. D- iˆe` u n`ay d¯o.n gia˙’n l`a mˆo˜i khi c´o ´ıt nhˆa´t mˆo.
t cung gi˜u.a hai d¯ı˙’nh ta khˆong quan
tˆam d¯ˆe´n th´u.
tu.
. cu˙’a ch´ung.
V´o.
i mˆo˜i cung, t´u.
c l`a mˆo˜i cˇa.p c´o th´u.
tu.
.
(vi
, vj ) ta cho tu.o
.ng ´u.ng cˇa.p khˆong c´o th´u.
tu.
.
(vi
, vj ) go.
i l`a c´ac ca. nh. Tu.o
.ng d¯u.o
.ng, ta n´oi rˇa`ng ca.nh l`a mˆo.
t cung m`a hu.´o
.ng d¯˜a bi
. bo˙’
quˆen. Vˆe` h`ınh ho. c, ca.nh (vi
, vj ) d¯u.o
.
. c biˆe˙’u diˆe˜n bo.
˙’ i c´ac d¯oa.n thˇa˙’ng (hoˇa. c cong) v`a khˆong
c´o m˜ui tˆen liˆen thuˆo. c hai d¯iˆe˙’m tu.o
.ng ´u.ng hai d¯ı˙’nh vi v`a vj
.
10
http://www.ebook.edu.vn
Nghiˆen c´u.u c´ac t´ınh chˆa´t vˆo hu.´o
.ng cu˙’a d¯ˆo` thi
. G = (V, E) d¯u.a vˆe` kha˙’o s´at tˆa.p E l`a
tˆa.p c´ac ca. nh, t´u.
c l`a, mˆo.
t tˆa.p h˜u.u ha.n c´ac phˆa`n tu.
˙’ m`a mˆo˜i phˆa`n tu.
˙’ l`a mˆo.
t cˇa.p hai d¯ı˙’nh
phˆan biˆe.
t hay d¯ˆo`ng nhˆa´t cu˙’a V.
D- a d¯ˆo` thi
. vˆo hu.´o
.ng l`a d¯ˆo` thi
. m`a c´o thˆe˙’ c´o nhiˆe` u ho.n mˆo.
t ca.nh liˆen thuˆo.c hai d¯ı˙’nh.
D- `ˆo thi
. go.
i l`a d¯o.n nˆe´u n´o khˆong c´o khuyˆen v`a hai d¯ı˙’nh bˆa´t k`y c´o nhiˆe` u nhˆa´t mˆo.
t ca.nh
liˆen thuˆo. c ch´ung.
..............................................................................................................................................................................................................................................................................................
.............................................................................................................................................................................................................................................................................................
.............................................................................................................................
.....
........
... ....... .
.............
......
.
.
......................................................................................................................................................................................................................................................................................
...
......
........
..........
............
................
......................
........................................... ....................................................... ........ .................
......................
................
............
..........
........
......
....
v1
v2 v3
v4
v5
e1 e2
e3
e4
e5
e6 e7
e8
e9
•
• •
•
•
H`ınh 1.2: D- `ˆo thi
. vˆo hu.´o
.ng tu.o
.ng ´u.ng d¯ˆo` thi
.
trong H`ınh 1.1.
1.1.4 C´ac d¯i
.nh ngh˜ıa ch´ınh
Hai cung, hoˇa. c hai ca.nh go.
i l`a kˆe` nhau nˆe´u ch´ung c´o ´ıt nhˆa´t mˆo.
t d¯ı˙’nh chung. Chˇa˙’ng ha.n,
hai ca.nh e1 v`a e3 trong H`ınh 1.2 l`a kˆe` nhau. Hai d¯ı˙’nh vi v`a vj go.
i l`a kˆe` nhau nˆe´u tˆo`n ta.
i
ca.nh hoˇa. c cung ek liˆen thuˆo. c ch´ung. V´ı du.
trong H`ınh 1.2 hai d¯ı˙’nh v2 v`a v3 l`a kˆe` nhau (liˆen
thuˆo. c bo.
˙’ i ca.nh e3), nhu.ng d¯ı˙’nh v2 v`a v5 khˆong kˆe` nhau.
Bˆa.
c v`a nu.
˙’ a bˆa.
c
Bˆa. c ngo`ai cu˙’a d¯ı˙’nh v ∈ V, k´y hiˆe.u d
+
G(v) (hay d
+(v) nˆe´u khˆong so.
. nhˆa`m lˆa˜n) l`a sˆo´ c´ac cung
c´o d¯ı˙’nh v l`a gˆo´c. Bˆa. c trong cu˙’a d¯ı˙’nh v ∈ V, k´y hiˆe.u d
−
G(v) (hay d
−(v) nˆe´u khˆong so.
. nhˆa`m
lˆa˜n) l`a sˆo´ c´ac cung c´o d¯ı˙’nh v l`a ngo.n.
Chˇa˙’ng ha.n, d¯ˆo` thi
. c´o hu.´o
.ng trong H`ınh 1.1 c´o d
+(v2) = 2, d−(v2) = 1.
11
http://www.ebook.edu.vn
Hiˆe˙’n nhiˆen rˇa`ng, tˆo˙’ng c´ac bˆa. c ngo`ai cu˙’a c´ac d¯ı˙’nh bˇa`ng tˆo˙’ng c´ac bˆa. c trong cu˙’a c´ac
d¯ı˙’nh v`a bˇa`ng tˆo˙’ng sˆo´ cung cu˙’a d¯ˆo` thi
. G, t´u.
c l`a
Xn
i=1
d
+
(vi) = Xn
i=1
d
−
(vi) = m.
Nˆe´u G l`a d¯ˆo` thi
. vˆo hu.´o
.ng, bˆa. c cu˙’a d¯ı˙’nh v ∈ V, k´y hiˆe.u dG(v) (hay d(v) nˆe´u khˆong so.
.
nhˆa`m lˆa˜n) l`a sˆo´ c´ac ca.nh liˆen thuˆo. c d¯ı˙’nh v v´o.
i khuyˆen d¯u.o
.
. c d¯ˆe´m hai lˆa`n. V´ı du. d¯ˆo` thi
. vˆo
hu.´o
.ng trong H`ınh 1.2 c´o d(v2) = 3, d(v5) = 5.
C´ac cung (ca.nh) liˆen thuˆo.
c tˆa.p A ⊂ V. C´ac d¯ˆo´i chu tr`ınh
Gia˙’ su.
˙’ A ⊂ V. K´y hiˆe.u ω
+(A) l`a tˆa.p tˆa´t ca˙’ c´ac cung c´o d¯ı˙’nh gˆo´c thuˆo. c A v`a d¯ı˙’nh ngo.n
thuˆo. c Ac
:= V \ A, v`a ω
−(A) l`a tˆa.p tˆa´t ca˙’ c´ac cung c´o d¯ı˙’nh ngo.n thuˆo. c A v`a d¯ı˙’nh gˆo´c thuˆo. c
Ac
. D- ˇa.
t
ω(A) = ω
+(A) ∪ ω
−(A).
Tˆa.p c´ac cung hoˇa. c ca.nh c´o da.ng ω(A) go.
i l`a d¯ˆo´i chu tr`ınh cu˙’a d¯ˆo` thi
.
.
D- `ˆo thi
.
c´o tro.ng sˆo´
D- `ˆo thi
. c´o tro. ng sˆo´ nˆe´u trˆen mˆo˜i cung (hoˇa. c ca.nh) e ∈ E c´o tu.o
.ng ´u.ng mˆo.
t sˆo´ thu.
. c w(e) go.
i
l`a tro.ng lu.o
.
. ng cu˙’a cung e.
D- `ˆo thi
. d¯ˆo´i x´u.ng
D- `ˆo thi
. c´o hu.´o
.ng go.
i l`a d¯ˆo´i x´u.ng nˆe´u c´o bao nhiˆeu cung da.ng (vi
, vj ) th`ı c˜ung c´o bˆa´y nhiˆeu
cung da.ng (vj
, vi).
D- `ˆo thi
. pha˙’n d¯ˆo´i x´u.ng
D- `ˆo thi
. c´o hu.´o
.ng go.
i l`a pha˙’n d¯ˆo´i x´u.ng nˆe´u c´o cung da.ng (vi
, vj ) th`ı khˆong c´o cung da.ng
(vj
, vi).
12
http://www.ebook.edu.vn
D- `ˆo thi
. d¯ˆa`y d¯u˙’
D- `ˆo thi
. vˆo hu.´o
.ng go.
i l`a d¯ˆa`y d¯u˙’ nˆe´u hai d¯ı˙’nh bˆa´t k`y vi v`a vj tˆo`n ta.
i mˆo.
t ca.nh da.ng (vi
, vj ).
D- o
.n d¯ˆo` thi
. vˆo hu.´o
.ng d¯ˆa`y d¯u˙’ n d¯ı˙’nh d¯u.o
.
. c k´y hiˆe.u l`a Kn.
D- `ˆo thi
.
con
Gia˙’ su.
˙’ A ⊂ V. D- `ˆo thi
. con d¯u.o
.
. c sinh bo.
˙’ i tˆa.p A l`a d¯ˆo` thi
. GA := (A, EA) trong d¯´o c´ac d¯ı˙’nh l`a
c´ac phˆa`n tu.
˙’ cu˙’a tˆa.p A v`a c´ac cung trong EA l`a c´ac cung cu˙’a G m`a hai d¯ı˙’nh n´o liˆen thuˆo. c
thuˆo. c tˆa.p A.
Nˆe´u G l`a d¯ˆo` thi
. biˆe˙’u diˆe˜n ba˙’n d¯ˆo` giao thˆong cu˙’a nu.´o
.
c Viˆe.
t Nam th`ı d¯ˆo` thi
. biˆe˙’u diˆe˜n
ba˙’n d¯ˆo` giao thˆong cu˙’a th`anh phˆo´ D- `a La.
t l`a mˆo.
t d¯ˆo` thi
. con.
D- `ˆo thi
. bˆo. phˆa.n
X´et d¯ˆo` thi
. G = (V, E) v`a U ⊂ E. D- `ˆo thi
. bˆo. phˆa. n sinh bo.
˙’ i tˆa.p U l`a d¯ˆo` thi
. v´o.
i tˆa.p d¯ı˙’nh V
v`a c´ac cung thuˆo. c U (c´ac cung cu˙’a E \ U bi
. xo´a kho˙’i G).
D- `ˆo thi
.
con bˆo. phˆa.n
X´et d¯ˆo` thi
. G = (V, E) v`a A ⊂ V, U ⊂ E. D- `ˆo thi
. con bˆo. phˆa. n sinh bo.
˙’ i tˆa.p A v`a U l`a d¯ˆo` thi
.
bˆo. phˆa.n cu˙’a GA sinh bo.
˙’ i U.
1.2 Ma trˆa.n biˆe˙’u diˆe˜n d¯ˆo` thi
.
1.2.1 Ma trˆa.n liˆen thuˆo.
c d¯ı˙’nh-cung
Ma trˆa. n liˆen thuˆo. c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi
. G = (V, E) l`a ma trˆa.n A = (aij ), i = 1, 2, . . . , n, j =
1, 2, . . . , m, v´o.
i c´ac phˆa`n tu.
˙’ 0, 1 v`a −1, trong d¯´o mˆo˜i cˆo.
t biˆe˙’u diˆe˜n mˆo.
t cung cu˙’a G v`a mˆo˜i
h`ang biˆe˙’u diˆe˜n mˆo.
t d¯ı˙’nh cu˙’a G. Nˆe´u ek = (vi
, vj ) ∈ E th`ı tˆa´t ca˙’ c´ac phˆa`n tu.
˙’ cu˙’a cˆo.
t k bˇa`ng
khˆong ngoa.
i tr`u.
aik = 1, ajk = −1.
13
http://www.ebook.edu.vn
V´ı du. 1.2.1 Ma trˆa.n liˆen thuˆo. c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi
.
trong H`ınh 1.3 l`a
e1 e2 e3 e4 e5
a +1 +1 0 0 0
b −1 0 +1 +1 0
c 0 −1 −1 0 +1
d 0 0 0 −1 −1
.
................................................................................................................................................................. ..........
..
..........
... .. ...................................................................................................................................................................................................................................................................................................
........................................................................
.
.
......... .................................................................................................................................................................
....
..............
.................................................................................................................................................................
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
..............
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
..
a b
d c
• •
• •
e1
e2
e3
e4
e5
H`ınh 1.3:
Nhˇa´c la.
i rˇa`ng, ma trˆa.n vuˆong go.
i l`a unimodular nˆe´u d¯i
.nh th´u.
c cu˙’a n´o bˇa`ng 1 hoˇa. c
−1. Ma trˆa.n A cˆa´p m × n go.
i l`a total unimodular nˆe´u tˆa´t ca˙’ c´ac ma trˆa.n vuˆong con khˆong
suy biˆe´n cu˙’a A l`a unimodular.
Mˆe.nh d¯ˆe` 1.2.2 Ma trˆa. n liˆen thuˆo. c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi. G = (V, E) l`a total unimodular.
Ch´u.ng minh. Ch´u ´y rˇa`ng ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-cung cu˙’a d¯ˆo` thi
. G = (V, E) ch´u.a d¯´ung
hai phˆa`n tu.
˙’ kh´ac khˆong trˆen mˆo˜i cˆo.
t, mˆo.
t bˇa`ng 1 v`a mˆo.
t bˇa`ng −1. Do d¯´o ta c´o thˆe˙’ ch´u.ng
minh theo quy na.p nhu.
sau: Hiˆe˙’n nhiˆen, tˆa´t ca˙’ c´ac ma trˆa.n vuˆong con khˆong suy biˆe´n cˆa´p 1
cu˙’a A l`a modular; gia˙’ su.
˙’ khˇa˙’ng d¯i
.nh d¯´ung cho mo.
i ma trˆa.n con khˆong suy biˆe´n cˆa´p (k −1).
X´et ma trˆa.n vuˆong con A0
cˆa´p k cu˙’a A. Nˆe´u mˆo˜i cˆo.
t cu˙’a A0
ch´u.a d¯´ung hai phˆa`n tu.
˙’
kh´ac khˆong th`ı det(A0
) = 0 (thˆa.
t vˆa.y, tˆo˙’ng tˆa´t ca˙’ c´ac h`ang cu˙’a A0
l`a vector khˆong, do d¯´o c´ac
h`ang l`a d¯ˆo. c lˆa.p tuyˆe´n t´ınh). Nˆe´u tˆo`n ta.
i mˆo.
t cˆo.
t cu˙’a A0 khˆong c´o phˆa`n tu.
˙’ kh´ac khˆong th`ı
det(A0
) = 0. Cuˆo´i c`ung, nˆe´u tˆo`n ta.
i cˆo.
t j cu˙’a A0
sao cho c´o d¯´ung mˆo.
t phˆa`n tu.
˙’ kh´ac khˆong
aij (bˇa`ng 1, hay −1) th`ı det(A0
) = ± det(A00), trong d¯´o A00 l`a ma trˆa.n vuˆong cˆa´p (k − 1)
nhˆa.n d¯u.o
.
. c t`u. A0 bˇa`ng c´ach xo´a h`ang i v`a cˆo.
t j. Theo gia˙’ thiˆe´t quy na.p, det(A0
) bˇa`ng 1, −1
hay 0 v`a do d¯´o mˆe.nh d¯ˆe` d¯u.o
.
. c ch´u.ng minh. /
14
http://www.ebook.edu.vn
1.2.2 Ma trˆa.n liˆen thuˆo.
c d¯ı˙’nh-ca.nh
X´et d¯ˆo` thi
. vˆo hu.´o
.ng G = (V, E). Ma trˆa. n liˆen thuˆo. c d¯ı˙’nh-ca. nh cu˙’a d¯ˆo` thi
. G l`a ma trˆa.n
A = (aij ), i = 1, 2, . . . , n, j = 1, 2, . . . , m, v´o.
i c´ac phˆa`n tu.
˙’ 0 v`a 1, trong d¯´o mˆo˜i cˆo.
t biˆe˙’u diˆe˜n
mˆo.
t ca.nh cu˙’a G v`a mˆo˜i h`ang biˆe˙’u diˆe˜n mˆo.
t d¯ı˙’nh cu˙’a G; ngo`ai ra, nˆe´u ca.nh ek liˆen thuˆo. c
hai d¯ı˙’nh vi v`a vj th`ı tˆa´t ca˙’ c´ac phˆa`n tu.
˙’ cu˙’a cˆo.
t k bˇa`ng khˆong ngoa.
i tr`u.
aik = 1, ajk = 1.
V´ı du. 1.2.3 Ma trˆa.n liˆen thuˆo. c d¯ı˙’nh-ca.nh cu˙’a d¯ˆo` thi
.
trong H`ınh 1.4 l`a
e1 e2 e3 e4 e5
a 1 1 0 0 0
b 1 0 1 1 0
c 0 1 1 0 1
d 0 0 0 1 1
..................................................................................................................................................................................................................................................................................................................................
.. .................................................................................................................................................................................................................................................................................................................................
..
...............................................................................................................................................................................................
..............................................................................................................................................................................................
a b
d c
• •
• •
e1
e2
e3
e4
e5
H`ınh 1.4:
Tr´ai v´o.
i ma trˆa.n liˆen thuˆo. c d¯ı˙’nh-cung, n´oi chung ma trˆa.n liˆen thuˆo. c d¯ı˙’nh-ca.nh khˆong
total unimodular. Chˇa˙’ng ha.n, trong v´ı du.
trˆen, ma trˆa.n con
1 1 0
1 0 1
0 1 1
c´o d¯i
.nh th´u.
c bˇa`ng −2.
D- `ˆo thi
. vˆo hu.´o
.ng G = (V, E) go.
i l`a hai phˆa`n nˆe´u c´o thˆe˙’ phˆan hoa. ch tˆa.p c´ac d¯ı˙’nh
V th`anh hai tˆa.p con r`o.
i nhau V1 v`a V2 sao cho d¯ˆo´i v´o.
i mˆo˜i ca.nh (vi
, vj ) ∈ E th`ı hoˇa. c
vi ∈ V1, vj ∈ V2 hoˇa. c vj ∈ V1, vi ∈ V2.
15