Đồ thị và các thuật toán – Chương 1: Đại cương về đồ thị

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

24
lượt xem 2
download

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

Đồ thị và các thuật toán – Chương 1 trình bày những kiến thức cơ bản về đồ thị như: Định nghĩa và các khái niệm, ma trận biểu diễn đồ thị, tính liên thông, phạm vi và liên thông mạnh, đẳng cấu của các đồ thị, các đồ thị đặc biệt. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Đồ thị và các thuật toán – Chương 1: Đại cương về đồ thị

Mu.c lu.c o.i n´ L` oi d`au ¯ˆ 7 - a.i cu.o.ng vˆ 1 D `e d`o thi. ¯ˆ 9 1.1 - i.nh ngh˜ıa v`a c´ac kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . D 9 1.1.1 - `ˆo thi. c´o hu.´o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 9 1.1.2 - `ˆo thi. v`a ´anh xa. d¯a tri. . . . . . . . . . . . . . . . . . . . . . . . . . . D 10 1.1.3 - `ˆo thi. vˆo hu.´o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 10 1.1.4 C´ac d¯i.nh ngh˜ıa ch´ınh . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Ma trˆa.n biˆe˙’u diˆ˜en 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 `e hay ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-d¯ı˙’nh . . . . . . . . . . . . . Ma trˆa.n kˆ 17 1.2.4 C´ac biˆe˙’u diˆ˜en cu˙’a d¯`oˆ thi. . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 T´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 `en v`a chu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . Dˆay chuyˆ 23 1.3.2 - u.`o.ng d¯i v`a ma.ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 24 1.3.3 T´ınh liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1 http://www.ebook.edu.vn
1.3.4 `au, k−liˆen thˆong . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cˆ 28 1.3.5 - `ˆo thi. liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . D 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 `an liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . T`ım c´ac th`anh phˆ 36 1.4.3 Co. so˙’. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5 - ˇa˙’ng cˆa´u cu˙’a c´ac d¯`ˆo thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 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 - `ˆo thi. khˆong c´o ma.ch . . . . . . . . . . . . . . . . . . . . . . . . . . D 46 1.6.2 - `ˆo thi. phˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 46 2 C´ o´ co. ba˙’n cu˙’a d ac sˆ `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¯.inh trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Sˆo´ ˆo˙’n d¯.inh 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´ `e tˆ y vˆ `on 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ˆ ¯u.` `e d o.ng d ¯i 75 3.1 - u.`o.ng d¯i gi˜ D u.a hai d¯ı˙’nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.1.1 - u.`o.ng d¯i gi˜ D u.a hai d¯ı˙’nh . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.1.2 - `ˆo thi. liˆen thˆong ma.nh . . . . . . . . . . . . . . . . . . . . . . . . . . D 76 3.2 - u.`o.ng d¯i ngˇa´n nhˆa´t gi˜ D 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` yy´. . . . . . . . . . . . . . . . . 82 3.3 - u.`o.ng d¯i ngˇa´n nhˆa´t gi˜ D 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` yy´) . . . . . . 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¯`ˆau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ˆ `eu rˆo.ng x´ac d¯.inh cˆay bao tr` um . . . . . 107 4.3.2 Thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu sˆau x´ac d¯i.nh cˆay bao tr` um . . . . . 107 4.3.3 um du..a trˆen hai ma˙’ng tuyˆe´n t´ınh . . . . . . . . . . . 108 T`ım cˆay bao tr` 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 um tˆo´i thiˆe˙’u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Cˆay bao tr` 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 `en Euler . . . . . . . . . . . . . . . . . . . . 129 Thuˆa.t to´an t`ım dˆay chuyˆ 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ˆ `an d¯ˆe˙’ tˆ `eu kiˆe.n cˆ `on ta.i chu tr`ınh Hamilton . . . . . . . . . . . . 138 5.3.2 C´ac d¯iˆ `e su.. tˆ `eu kiˆe.n d¯u˙’ vˆ `on ta.i chu tr`ınh Hamilton . . . . . . . . . . 139 5.3.3 C´ac d¯iˆ `e su.. tˆ `eu kiˆe.n d¯u˙’ vˆ `on ta.i ma.ch Hamilton . . . . . . . . . . . . . 142 - `ˆ 6 D a˙’ ng o thi. phˇ 149 6.1 - .inh ngh˜ıa v`a c´ac v´ı du. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 D 6.2 C´ac biˆe˙’u diˆ˜en 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 - ˆo´i ngˆa˜u h`ınh ho.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 D 6.6 - ˆo´i ngˆa˜u tˆo˙’ ho..p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 D a.n ta˙’ i 7 Ma.ng vˆ 173 4 http://www.ebook.edu.vn
7.1 Mo˙’. d¯`ˆau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 7.2 `ong l´o.n nhˆa´t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 B`ai to´an luˆ 7.2.1 `ong l´o.n nhˆa´t . . . . . . . . . . . . . . 180 Thuˆa.t to´an g´an nh˜an d¯ˆe˙’ t`ım luˆ 7.2.2 - `ˆo thi. d¯iˆ D `eu chı˙’nh luˆ `ong . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2.3 `ong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 Phˆan t´ıch luˆ 7.3 C´ac ca˙’i biˆen d¯o.n gia˙’n cu˙’a b`ai to´an luˆ `ong l´o.n nhˆa´t . . . . . . . . . . . . . . . 183 7.3.1 C´ac d¯`ˆo thi. c´o nhiˆ `eu nguˆ `on v`a nhiˆ `eu 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ˆ `ong . . . . . . . . . . . . . . 185 7.4 `ong v´o.i chi ph´ı nho˙’ nhˆa´t . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 Luˆ 7.4.1 Thuˆa.t to´an Klein, Busacker, Gowen . . . . . . . . . . . . . . . . . . . 186 7.5 Cˇa.p gh´ep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7.5.1 `e cˇa.p gh´ep . . . . . . . . . . . . . . . . . . . . . . . . 189 C´ac b`ai to´an vˆ 7.5.2 Cˇa.p gh´ep l´o.n nhˆa´t trong d¯`ˆo thi. hai phˆ `an . . . . . . . . . . . . . . . . 192 7.5.3 Cˇa.p gh´ep ho`an ha˙’o trong d¯`ˆo thi. hai phˆ `an . . . . . . . . . . . . . . . 193 A Thu. viˆ e.n Graph.h 197 T` e.u tham kha˙’ o ai liˆ 209 5 http://www.ebook.edu.vn
6 http://www.ebook.edu.vn
o.i n´ L` oi d`au ¯ˆ 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 `om c´ac d¯iˆe˙’m (c´ac d¯ı˙’nh)-biˆe˙’u diˆ˜en 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 gˆ diˆ˜en 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ˆ `eu 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ˆ `en 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ˆ `eu l˜ınh vu..c, c´o rˆa´t nhiˆ `eu nghiˆen c´ u.u xung quanh l´ y thuyˆe´t d¯`oˆ thi. trong nh˜ u.ng nˇam gˆ `an d¯aˆy; mˆo.t nhˆan tˆo´ chu˙’ yˆe´u g´op phˆ `an th´ uc d¯aˆ y su. ph´at triˆen 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ˆeu ph´ep to´an v´o.i ˙ ’ . ˙ ’ ´ . ˙ ’ . ` tˆo´c d¯oˆ. rˆa´t nhanh. Viˆe.c biˆe˙’u diˆ˜en 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ˆ `en 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ˆ `eu 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ˆ u.c vˆ `an c´o mˆo.t sˆo´ kiˆe´n th´ u. C. Ngo`ai `e ngˆon ng˜ ra, hˆ . . `au 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. `om ba˙’y chu.o.ng v`a mˆo.t phˆ Gi´ao tr`ınh bao gˆ `an 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ˆ˜en 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ˆ `an phu. lu.c tr`ınh b`ay c´ac cˆa´u tr´ u. liˆe.u v`a nh˜ uc d˜ u.ng thu˙’ tu.c cˆ `an 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ˆ `an d¯`aˆu tiˆen nˆen khˆong tr´anh kho˙’i kh´a nhiˆ `eu 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ˆ `eu 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. - `a La.t, ng`ay 5 th´ang 3 nˇam 2002 D . PHA . M Tiˆe´n So n 8 http://www.ebook.edu.vn
Chu.o.ng 1 - a.i cu.o.ng vˆ D `e d`o thi. ¯ˆ 1.1 - i.nh ngh˜ıa v` D a c´ ac kh´ ai niˆ e.m 1.1.1 - `ˆ D o hu.´ o thi. c´ o.ng - `ˆo thi. c´o hu.´o.ng G = (V, E) gˆ D `om mˆo.t tˆa.p V c´ac phˆ `an 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 . . . . . . u. tu... Nˆe´u ´ ng v´o i mˆo.t cˇa.p c´ac d¯ı˙’nh d¯u o. c sˇa´p th´ c´o d¯u´ng 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¯a´nh 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ˆ˜en bo˙’.i c´ac d¯iˆe˙’m, v`a e = (vi , vj ) d¯u.o..c biˆe˙’u diˆ˜en bo˙’.i mˆo.t cung nˆo´i c´ac d¯iˆe˙’m vi v`a vj . ung v´o.i ngo.n go.i l`a khuyˆen. Mˆo.t cung c´o gˆo´c tr` `eu 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 Nˆe´u c´o nhiˆ 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ˆ`eu 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
e4 .. .................................................................................................... v2 e3 v3 .......... .................. .......... •v4 ...... ...... • . . .. .... .. • ................................................................................................................................................................. .. ........... .................. ......... ............ .... . .... .... ... .... ... .... .. .. ............................................................... . ... ... ... ... ....... .. ... ... ... . .. ... .. ... ... ... ... .... e9 ... ... . ... ... ... ... .... ... ... ... . .. ... .... . ... ... ... ... ... ... ... .... ... .... ... . . .... ... .. . ... .. .......... ... ......... ... e1 .. .... e2 .......... .. .. e6 ... . .... e7 . .. . ... ... ... .. .... ... ..... ... ... ... ........ ... .. .. ........ ... . . ... . ... ...... ... ... .... ...... ... ... ..... ... .... ...... ... ...... ... ... .... ... ... .... ....... ... .. ....... .. ... ....... ... ....... ... ... .... .. e5 ... ... ............. ........ • .... ... . • v5 ....................................................................................................................................................................... . .. v1 ... .. ... .... ... .. .... . . .. ....... ... ... .... ...... ....... e8 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 → 2V , 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¯.inh bo˙’.i tˆa.p V v`a ´anh xa. d¯a u. V v`ao 2V . V`ı vˆa.y, d¯`oˆ thi. n`ay c`on c´o thˆe˙’ k´ tri. Γ t` 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ˆ˜en 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 hu.´ o thi. vˆ 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ˆ `an 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 `eu n`ay d¯o.n gia˙’n l`a mˆo˜i khi c´o ´ıt nhˆa´t mˆo.t cung gi˜ - iˆ 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ˆ˜en 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ˆ . `an tu˙’ m`a mˆo˜i phˆ . `an tu˙’ l`a mˆo.t cˇa.p hai d¯ı˙’nh phˆan biˆe.t hay d¯`ˆong nhˆa´t cu˙’a V. - a d¯`oˆ thi. vˆo hu.´o.ng l`a d¯`oˆ thi. m`a c´o thˆe˙’ c´o nhiˆ D `eu ho.n mˆo.t ca.nh liˆen thuˆo.c hai d¯ı˙’nh. - `ˆ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` D `eu nhˆa´t mˆo.t ca.nh y c´o nhiˆ liˆen thuˆo.c ch´ ung. e4 v...2................................................................e.......3.......................................................v.......3........................................................................................................................................................... ...•..... .. .. •.............................. •... v4 ......... ............. .... ... ... .. ............................ ..................................................................... .... ... ... .. . ... ... . .. ... ... ... . . . .... ... e9 .. ... . .. . ... ... .... ... ... ... ... ... ... ... ... ... ... .... ... ... ... . .. ... .. ... ... ... ... ... ... ... .. ... ... e1 ..... ... e2 .. ... e6 . . .... e7 .. .... . .... ... ... ... ..... ... ... ... ..... ... ... . . .. ...... . ... ... .... ..... ... ... ..... ... ..... ... .. ... ...... ... . ... . . . .. ....... . ... . ... .... ...... ... ... ...... ... ... ...... ... ... ... ....... ....... ... ... ... ... ... ... e5 . . ... ....... ........ . ... .. • • v5 .................................................................................................................................................................... ... ..... v1 .. .... ... ... ..... .. ... .. ... . ... .... ..... ....... e8 - `ˆo thi. vˆo hu.´o.ng tu.o.ng u H`ınh 1.2: D ´.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ˆ ung c´o ´ıt nhˆa´t mˆo.t d¯ı˙’nh chung. Chˇa˙’ng ha.n, `e nhau nˆe´u ch´ 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ˆ `on ta.i ung. V´ı du. trong H`ınh 1.2 hai d¯ı˙’nh v2 v`a v3 l`a kˆ ca.nh hoˇa.c cung ek liˆen thuˆo.c ch´ `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 nu˙’.a bˆ a.c v` 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ˆ `am lˆa˜n) l`a sˆo´ c´ac cung ´ c´o d¯ı˙’nh v l`a gˆoc. Bˆa.c trong cu˙’a d¯ı˙’nh v ∈ V, k´y hiˆe.u dG (v) (hay d (v) nˆe´u khˆong so.. nhˆ − − `am 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 u.c l`a d¯ı˙’nh v`a bˇ`a ng tˆo˙’ng sˆo´ cung cu˙’a d¯`oˆ thi. G, t´ n X n X d+ (vi ) = d− (vi ) = m. i=1 i=1 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.. `am 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ˆ nhˆ `an. 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´ o tro.ng sˆ - `ˆ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 D ´.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 ¯ˆ u.ng o´i x´ - `ˆo thi. c´o hu.´o.ng go.i l`a d¯ˆo´i x´ D 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 ¯ˆ u.ng o´i x´ - `ˆo thi. c´o hu.´o.ng go.i l`a pha˙’n d¯ˆo´i x´ D 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`ay d ¯ˆ ¯u˙’ - `ˆo thi. vˆo hu.´o.ng go.i l`a d¯`ˆay d¯u˙’ nˆe´u hai d¯ı˙’nh bˆa´t k` D `on ta.i mˆo.t ca.nh da.ng (vi , vj ). y vi v`a vj tˆ D . . . . . - o n d¯`oˆ thi. vˆo hu ´o ng d¯`ˆay 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ˆ . `an 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ˆ˜en ba˙’n d¯`ˆo giao thˆong cu˙’a nu.´o.c Viˆe.t Nam th`ı d¯`oˆ thi. biˆe˙’u diˆ˜en 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 - `ˆo thi. con bˆo. phˆa.n sinh bo˙’.i tˆa.p A v`a U l`a d¯`oˆ thi. X´et d¯`oˆ thi. G = (V, E) v`a A ⊂ V, U ⊂ E. D bˆo. phˆa.n cu˙’a GA sinh bo˙’.i U. 1.2 Ma trˆ e˙’u diˆ a.n biˆ ˜ en d`o thi. ¯ˆ 1.2.1 Ma trˆ a.n liˆ en thuˆ ¯ı˙’nh-cung o.c d 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ˆ `an tu˙’. 0, 1 v`a −1, trong d¯o´ mˆo˜i cˆo.t biˆe˙’u diˆ˜en mˆo.t cung cu˙’a G v`a mˆo˜i h`ang biˆe˙’u diˆ˜en mˆo.t d¯ı˙’nh cu˙’a G. Nˆe´u ek = (vi , vj ) ∈ E th`ı tˆa´t ca˙’ c´ac phˆ `an 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...............................................................................e.........1.............................................................................b... •................ . .....• ...... ..... . ...... ...... ...... ...... ... ...... ... ...... ...... ...... ...... ... e 4 . ...... ....... . ...... .... . ... ... .. ...... ...... ... ...... ...... ... ...... ...... .. ...... ...... ...... ...... ............ ........... ....... . ........ . . .... .......... ...... ... ... ... e3 ...... ........ ... ........ ............. . . ............ ... .. ... ... .... ...... . .... . ....... ...... .... e2 .. ....... .. ....... .. ....... ... ... ... .... ..... .. ....... ... . ........ .. ....... .... . .... • .... . .. . . ..................................................................................................................................................................... . . • d e5 c H`ınh 1.3: u.c cu˙’a n´o bˇa` ng 1 hoˇa.c 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´ −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´ uy´ 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¯u´ng hai phˆ . u.ng `an 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´ 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¯.inh d¯u ´ng 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¯u´ng hai phˆ `an 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ˆ `on ta.i mˆo.t cˆo.t cu˙’a A0 khˆong c´o phˆ `an tu˙’. kh´ac khˆong th`ı det(A0 ) = 0. Cuˆo´i c` ung, nˆe´u tˆ `on ta.i cˆo.t j cu˙’a A0 sao cho c´o d¯u ´ng mˆo.t phˆ `an 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ˆ ¯ı˙’nh-ca.nh o.c d 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ˆ `an tu˙’. 0 v`a 1, trong d¯´o mˆo˜i cˆo.t biˆe˙’u diˆ˜en mˆo.t ca.nh cu˙’a G v`a mˆo˜i h`ang biˆe˙’u diˆ˜en mˆo.t d¯ı˙’nh cu˙’a G; ngo`ai ra, nˆe´u ca.nh ek liˆen thuˆo.c `an tu˙’. cu˙’a cˆo.t k bˇa` ng khˆong ngoa.i tr` hai d¯ı˙’nh vi v`a vj th`ı tˆa´t ca˙’ c´ac phˆ 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.............................................................................e.......1.............................................................................b.... •................ ......• ...... .... .. ...... ...... ...... ...... .... ...... ...... ...... ...... ...... ... e4................... .. ... ... ... .. ...... . ...... ...... .... ...... ...... ...... ...... ... ...... ...... ... ...... ........... ..... .. ........ . . . .... .......... ... ... ... e3 ... ...... ...... .. ...... ... ......... . ........ ... .. ....... .. ....... ... .... ... ........ ... . ........ e2 .. ....... .. ....... .. .. ... ... ... ..... ...... .. . ....... ........ .... . ...... ...... .. • .......................................................................................................................................................................... • d e5 c 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 u.c bˇa` ng −2. c´o d¯i.nh th´ - `ˆo thi. vˆo hu.´o.ng G = (V, E) go.i l`a hai phˆ D `an 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 http://www.ebook.edu.vn
a..... •.................................... ....... ........... .. ....... .... .. •b ... ..... ....... ....... ..... ... ... ..... ......... . . . .............. ......... ... ... ..... ....... ...... .. ... ... ..... ....... ....... ..... ... ..... ....... ........ ..... ... ... ..... ..... ....... ....... ............. ........ . ... ... ... ..... .. . .......... . ... .. ..... ... ... ....... ... ..... ..... ............. ....... ......... ... ... . .. . ......... ... ... . . . ..... ....... . . ... ............ ... ..... ..... .... ... .. .. .. ..... . ...... ...... . ....... .... ... ... .. ..... .... ....... . ... ......... .... ....... .... . .. .......... .... . • ....... . . • .. ....... . .. . .. . ........ • c d e - `ˆo thi. hai phˆ H`ınh 1.5: D `an K2,3 . V´ı du. 1.2.4 Dˆ˜e kiˆe˙’m tra d¯`oˆ thi. K2,3 trong H`ınh 1.5 l`a hai phˆ `an. Mˆe.nh d`e 1.2.5 Ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-ca.nh cu˙’ a d¯`ˆo thi. vˆo hu.´o.ng G = (V, E) l`a total ¯ˆ unimodular nˆe´u v`a chı˙’ nˆe´u G l`a d¯`ˆo thi. hai phˆ `an. Ch´ u.ng minh. (1) Nˆe´u d¯`oˆ thi. l`a hai phˆ u.ng minh theo quy na.p rˇa` ng ung ta c´o thˆe˙’ ch´ `an, th`ı ch´ mo.i ma trˆa.n vuˆong con B cu˙’a ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-ca.nh c´o d¯i.nh th´ u.c det(B) = 0, 1 hoˇa.c −1. D - iˆ . . ´ng v´o.i c´ac ma ´ng v´o i c´ac ma trˆa.n vuˆong con cˆa´p 1; gia˙’ su˙’ khˇa˙’ng d¯.inh d¯u `eu n`ay d¯u trˆa.n vuˆong con cˆa´p (k − 1). X´et ma trˆa.n vuˆong con B cˆa´p k. u.a d¯u Nˆe´u mˆo˜i cˆo.t B j cu˙’a B ch´ `an tu˙’. bˇ`a ng 1 th`ı ´ng hai phˆ X X Bi = Bi , i∈I1 i∈I2 trong d¯o´ I1 v`a I2 l`a c´ac tˆa.p chı˙’ sˆo´ tu.o.ng u ´.ng hai phˆan hoa.ch cu˙’a tˆa.p c´ac d¯ı˙’nh V v`a Bi l`a vector h`ang cu˙’a B. C´ac vector h`ang phu. thuˆo.c tuyˆe´n t´ınh, nˆen det(B) = 0. Nˆe´u, ngu.o..c la.i, tˆ `on ta.i cˆo.t c´o d¯u `an tu˙’. bˇ`a ng 1, chˇa˙’ng ha.n bij = 1, k´ ´ng mˆo.t phˆ y hiˆe.u C . . l`a ma trˆa.n nhˆa.n d¯u o. c t`. ` u B bˇa ng c´ach xo´a h`ang i v`a cˆo.t j. Th`ı det(B) = ± det(C) (= 0, 1 hoˇa.c − 1 theo quy na.p). (2) Mˇa.t kh´ac, dˆ˜e d`ang ch´ u.ng minh rˇ`a ng ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-ca.nh cu˙’a d¯`ˆo thi. l`a mˆo.t chu u.c l`a sˆo´ ca.nh trˆen chu tr`ınh l`a le˙’-xem Phˆ tr`ınh d¯oˆ. d`ai le˙’ (t´ `an 1.3) c´o d¯.inh th´ u.c bˇ`a ng ±2. Do d¯o´ G khˆong ch´ u.a chu tr`ınh d¯oˆ. d`ai le˙’ v`a v`ı vˆa.y n´o l`a hai phˆ`an theo bˆo˙’ d¯`ˆe sau. / Bˆ o˙’ d ¯ˆ - `ˆo thi. vˆo hu.´o.ng G l`a hai phˆ `e 1.2.6 D u.a chu tr`ınh c´o d¯ˆo. `an nˆe´u v`a chı˙’ nˆe´u G khˆong ch´ d`ai le˙’ . u.ng minh. D Ch´ - iˆ `an. Do V d¯u.o..c phˆan hoa.ch th`anh V1 v`a V2 : `eu kiˆe.n cˆ V = V2 ∪ V2 , V1 ∩ V2 = ∅. 16 http://www.ebook.edu.vn
Gia˙’ thiˆe´t tˆ `on ta.i mˆo.t chu tr`ınh c´o d¯ˆo. d`ai le˙’ µ = {vi1 , vi2 , . . . , viq , vi1 } v`a khˆong mˆa´t t´ınh tˆo˙’ng qu´at, lˆa´y vi1 ∈ V1 . Do G l`a hai phˆ `an, nˆen hai d¯ı˙’nh liˆen tiˆe´p trˆen chu tr`ınh µ pha˙’i c´o mˆo.t d¯ı˙’nh thuˆo.c V1 v`a d¯ı˙’nh kia thuˆo.c V2 . Do d¯o´ vi2 ∈ V2 , vi3 ∈ V1 , . . . , v`a tˆo˙’ng qu´at, vik ∈ V1 nˆe´u k le˙’ v`a vik ∈ V2 nˆe´u k chˇa˜n. M`a chu tr`ınh µ c´o d¯ˆo. d`ai le˙’ nˆen viq ∈ V1 v`a bo˙’.i vˆa.y vi1 ∈ V2 . D `eu n`ay mˆau thuˆa˜n v´o.i V1 ∩ V2 = ∅. - iˆ D `eu kiˆe.n d¯u˙’. Khˆong mˆa´t t´ınh tˆo˙’ng qu´at gia˙’ thiˆe´t d¯`oˆ thi. G liˆen thˆong. Gia˙’ su˙’. khˆong tˆ - iˆ `on ta.i chu tr`ınh c´o d¯oˆ. d`ai le˙’. y, chˇa˙’ng ha.n vi v`a g´an nh˜an cho n´o l`a “ + ”. Sau d¯o´ lˇa.p la.i c´ac ph´ep Cho.n d¯ı˙’nh bˆa´t k` to´an sau: Cho.n d¯ı˙’nh d¯a˜ d¯u.o..c g´an nh˜an vj v`a g´an nh˜an ngu.o..c v´o.i nh˜an cu˙’a vj cho tˆa´t ca˙’ c´ac `e v´o.i d¯ı˙’nh vj . d¯ı˙’nh kˆ Tiˆe´p tu.c qu´a tr`ınh n`ay cho d¯ˆe´n khi xa˙’y ra mˆo.t trong hai tru.`o.ng ho..p: (a) Tˆa´t ca˙’ c´ac d¯ı˙’nh d¯˜a d¯u.o..c g´an nh˜an v`a hai d¯ı˙’nh bˆa´t k` `e nhau c´o nh˜an kh´ac nhau (mˆo.t y kˆ ´ ´ mang dˆa u + v`a mˆo.t mang dˆa u −); hoˇa.c `on ta.i d¯ı˙’nh, chˇa˙’ng ha.n vjk , d¯u.o..c g´an hai nh˜an kh´ac nhau. (b) Tˆ Trong Tru.`o.ng ho..p (a), d¯aˇ. t V1 l`a tˆa.p tˆa´t ca˙’ c´ac d¯ı˙’nh d¯u.o..c g´an nh˜an “+” v`a V2 l`a tˆa.p tˆa´t ca˙’ c´ac d¯ı˙’nh d¯u.o..c g´an nh˜an “−”. Do tˆa´t ca˙’ c´ac ca.nh liˆen thuˆo.c gi˜ u.a c´ac cˇa.p d¯ı˙’nh c´o nh˜an kh´ac nhau nˆen d¯`oˆ thi. G l`a hai phˆ `an. Trong Tru.`o.ng ho..p (b), d¯ı˙’nh vjk d¯u.o..c g´an nh˜an “+” do.c theo mˆo.t dˆay chuyˆ `en µ1 n`ao . . . d¯o´, v´o i c´ac d¯ı˙’nh d¯u o. c g´an nh˜an “+” v`a “−” xen k˜e nhau xuˆa´t ph´at t` . u vi v`a kˆe´t th´uc ta.i vjk . Tu o ng tu. , d¯ı˙’nh vjk d¯u o. c g´an nh˜an “−” do.c theo mˆo.t dˆay chuyˆen µ2 n`ao d¯´o, v´o.i c´ac . . . . . ` d¯ı˙’nh d¯u.o..c g´an nh˜an “+” v`a “−” xen k˜e nhau xuˆa´t ph´at t` u. vi v`a kˆe´t th´uc ta.i vjk . Nhu.ng nhu. thˆe´ chu tr`ınh d¯i do.c theo µ1 t` u. d¯ı˙’nh vi d¯ˆe´n d¯ı˙’nh vjk sau d¯o´ d¯i ngu.o..c la.i do.c theo µ2 vˆ`e la.i vi c´o d¯ˆo. d`ai le˙’. D `eu n`ay mˆau thuˆa˜n v´o.i gia˙’ thiˆe´t, v`a do d¯´o khˆong thˆe˙’ xa˙’y ra Tru.`o.ng - iˆ ho..p (b). D - i.nh l´y d¯u.o..c ch´ u.ng minh. / 1.2.3 Ma trˆ `e hay ma trˆ a.n kˆ a.n liˆ en thuˆ ¯ı˙’nh-d o.c d ¯ı˙’nh Gia˙’ su˙’. G = (V, E) l`a d¯`oˆ thi. sao cho c´o nhiˆ `eu nhˆa´t mˆo.t cung liˆen thuˆo.c hai d¯ı˙’nh bˆa´t k` y vi `e hay ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-d¯ı˙’nh l`a ma trˆa.n vuˆong A = (aij ) cˆa´p n × n v`a vj . Ma trˆa.n kˆ 17 http://www.ebook.edu.vn
v´o.i c´ac phˆ `an tu˙’. 0 hoˇa.c 1: ( 1 nˆe´u (vi , vj ) ∈ E, aij := 0 nˆe´u ngu.o..c la.i. Trong tru.`o.ng ho..p d¯`oˆ thi. vˆo hu.´o.ng, ma trˆa.n kˆ `e cu˙’a d¯o.n d¯`oˆ thi. c˜ ung c´o thˆe˙’ d¯u.o..c d¯.inh ngh˜ıa bˇ`a ng c´ach xem mˆo˜i ca.nh (vi , vj ) tu.o.ng u´.ng hai cung (vi , vj ) v`a (vj , vi ). Trong tru.`o.ng ho..p n`ay, ma trˆa.n kˆ u.ng. `e l`a d¯oˆ´i x´ 1.2.4 C´ e˙’u diˆ ac biˆ ˜ e n cu˙’a d`o thi. ¯ˆ - ˆe˙’ mˆo ta˙’ mˆo.t d¯`ˆo thi., ta c´o thˆe˙’ su˙’. du.ng mˆo.t sˆo´ c´ach biˆe˙’u diˆ˜en kh´ac nhau. V´o.i quan d¯iˆe˙’m D lˆa.p tr`ınh, n´oi chung c´ac biˆe˙’u diˆ˜en n`ay khˆong tu.o.ng d¯u.o.ng theo kh´ıa ca.nh hiˆe.u qua˙’ cu˙’a thuˆa.t to´an. C´o hai c´ach biˆe˙’u diˆ˜en ch´ınh: Th´u. nhˆa´t, su˙’. du.ng ma trˆa.n kˆ `e hoˇa.c c´ac dˆa˜n xuˆa´t cu˙’a . . u hai, su˙’ du.ng ma trˆa.n liˆen thuˆo.c hoˇa.c c´ac dˆa˜n xuˆa´t cu˙’a n´o. n´o; th´ Su˙’. du.ng ma trˆ `e a.n kˆ Ch´ ung ta biˆe´t rˇ`a ng c´ac ma trˆa.n kˆ `e cho ph´ep miˆeu ta˙’ hoˇa.c c´ac 1-d¯`ˆo thi. d¯.inh hu.´o.ng, hoˇa.c c´ac d¯o.n d¯`oˆ thi. vˆo hu.´o.ng. V´o.i c´ach biˆe˙’u diˆ˜en d¯`oˆ thi. qua ma trˆa.n kˆ `e, ta thˆa´y sˆo´ lu.o..ng thˆong tin, gˆ`om c´ac bit 0 v`a 1, cˆ `an lu.u tr˜ u. l`a n2 . C´ac bit c´o thˆe˙’ d¯u.o..c kˆe´t ho..p trong c´ac t` u.. K´ y hiˆe.u w l`a d¯oˆ. d`ai cu˙’a t` . u (t´ . u c l`a sˆo´ c´ac bit trong mˆo.t t` . u m´ay t´ınh). Khi d¯´o mˆo˜i h`ang cu˙’a ma `e c´o thˆe˙’ d¯u.o..c viˆe´t nhu. mˆo.t d˜ay n bit trong dn/we t` trˆa.n kˆ u. 1 . Do d¯o´ sˆo´ c´ac t`u. d¯ˆe˙’ lu.u tr˜ u. ma trˆa.n kˆ `e l`a ndn/we. Ma trˆa.n kˆ`e cu˙’a d¯`oˆ thi. vˆo hu.´o.ng l`a d¯oˆ´i x´ u.ng, nˆen ta chı˙’ cˆ `an lu.u tr˜ u. nu˙’.a tam gi´ac trˆen `an n(n − 1)/2 bit. Tuy nhiˆen, v´o.i c´ach lu.u tr˜ cu˙’a n´o, v`a do d¯o´ chı˙’ cˆ u. n`ay, s˜e tˇang d¯ˆo. ph´ u.c . ta.p v`a th`o i gian t´ınh to´an trong mˆo.t sˆo´ b`ai to´an. Trong tru.`o.ng ho..p c´ac ma trˆa.n thu.a (m ¿ n2 v´o.i d¯`oˆ thi. c´o hu.´o.ng; m ¿ 12 n(n + 1) d¯ˆo´i v´o.i d¯`ˆo thi. vˆo hu.´o.ng) c´ach biˆ˜eu diˆ˜en n`ay l`a l˜ang ph´ı. Do d¯o´ ta s˜e t`ım c´ach biˆe˙’u diˆ˜en chı˙’ c´ac phˆ`an tu˙’. kh´ac khˆong. V`ı mu.c d¯´ıch n`ay ta s˜e su˙’. du.ng mˆo.t ma˙’ng danh s´ach kˆ `e cho d¯`oˆ thi. c´o hu.´o.ng. D - `ˆo thi. c´o . . . . . hu ´o ng d¯u o. c biˆe˙’u diˆ˜en bo˙’ i mˆo.t ma˙’ng c´ac con tro˙’ V out[1], V out[2], . . . , V out[n], trong d¯o´ mˆo˜i con tro˙’ tu.o.ng u ´.ng v´o.i mˆo.t d¯ı˙’nh trong d¯`ˆo thi. c´o hu.´o.ng. Mˆo˜i phˆ `an tu˙’. cu˙’a ma˙’ng V out[i] chı˙’ d¯ˆe´n mˆo.t n´ut d¯`aˆu lu.u tr˜ u. mu.c d˜ u. liˆe.u cu˙’a n´ ut tu.o.ng u ´.ng d¯ı˙’nh vi v`a ch´ u.a mˆo.t con tro˙’ 1 y hiˆe.u dxe l`a sˆo´ nguyˆen nho˙’ nhˆa´t khˆong b´e ho.n x. K´ 18 http://www.ebook.edu.vn
`e (d¯ı˙’nh d¯u.o..c nˆo´i v´o.i vi theo hu.´o.ng t` chı˙’ d¯ˆe´n mˆo.t danh s´ach liˆen kˆe´t cu˙’a c´ac d¯ı˙’nh kˆ u. vi ra). Mˆo˜i n´ . . `e c´o hai tru `o ng: ut kˆ 1. Tru.`o.ng sˆo´ nguyˆen: lu.u tr˜ u. sˆo´ hiˆe.u cu˙’a d¯ı˙’nh kˆ `e; v`a 2. Tru.`o.ng liˆen kˆe´t chı˙’ d¯ˆe´n n´ ut kˆe´ tiˆe´p trong danh s´ach kˆ `e n`ay. v1 v2 .. .• .................................................................................• . .. ... ..... .. .. ... ........ ... ....... .. .... .... .... .... .. ..... ..... ... ... .. ..... ..... ... ... ... ..... ..... ... ... ..... ... ...... ... . .. . . ..... ....... .. . .... ... ... . . . . ......... .............. ... ... ... ... . . . ..... ..... . .... . . . . . . ..... .. ... ... ... . . ..... ..... ... .... . . ..... . . .. ... . . . ..... . . .... . . ... . . . ..... ... ... ... . ..... . ... . . . . . . ..... ................................... v6 • . ..... . ..... ..... ..... ....... ... . ... ......... . ... .... . ..... . ..... . . . • ...... ...... ........... .. ... ............... ..................................... ..... ..... ..... ..... ... ... ... ... ... ... ... . . . .... ... ....... .... .... ....... ......... ... ... v3 .... ...... ... ... ..... ... ....... ..... ..... ..... ... ... ... ... .............. ...... ......... . . ... ... . .... ... . .... ........ ... ... ................. ............ ..... ... .. ......... .. ..... . ..... ....... ..... .... ..... ..... ..... ... ... . . . .. . ......... . . . . . ........ ... .. . ..... .. ......... ... .. ......... ..... ... ....... ..... .. .............. ... .. ..... ............ • ............. • .. v5 v4 H`ınh 1.6: `e V out[] cu˙’a d¯`ˆo thi. c´o hu.´o.ng trong H`ınh 1.6 d¯u.o..c C´ach biˆe˙’u diˆ˜en ma˙’ng danh s´ach kˆ cho tu.o.ng u ´.ng trong H`ınh 1.7 (gia˙’ su˙’. c´ac mu.c d˜ u. liˆe.u tu.o.ng u ´.ng c´ac d¯ı˙’nh theo th´ u. tu.. l`a A, B, C, D, E, F ). ut . d¯`ˆau N´ .. .. . .... ... ... V out[1] .................................. A ... .. ... • ............................................... v4 .. ... ... • ............................................... v5 .. ... ... •............................................... NULL .. .. .. ..... ..... ..... •............................................... v1 •............................................... v3 ... ... ... V out[2].................................. B .. ... ... .. ... ... .. ... ... •............................................... NULL .. .. ... ... V out[3].................................. C .. ... .... •............................................... v3 .. ... .... •............................................... NULL . . .... .... .... V out[4]................................. D ... .. .... .. •................................................. v2 ... .. .... .. •................................................. v3 ... .. .... .. •................................................. NULL .. .. .. ... ... ... V out[5]................................... E .. ... ... •................................................ v3 .. ... ... •................................................ v6 .. ... ... •................................................ NULL . . . .... .... V out[6].................................. F ... .. ... •............................................... v1 ... .. ... •............................................... NULL .. .. `e V out[] tu.o.ng u H`ınh 1.7: Danh s´ach kˆ ´.ng d¯`oˆ thi. trong H`ınh 1.6. Thay v`ı con tro˙’ chı˙’ d¯ˆe´n mˆo.t danh s´ach c´ac d¯ı˙’nh t` u. vi d¯i ra trong V out[i], ta tro˙’ d¯ˆe´n danh s´ach c´ac d¯ı˙’nh d¯i d¯ˆe´n vi v`a do d¯o´ c´o thˆe˙’ lu.u tr˜ u. d¯`oˆ thi. thˆong qua ma˙’ng c´ac danh s´ach 19 http://www.ebook.edu.vn
`e V in[] cu˙’a d¯`oˆ thi. c´o hu.´o.ng trong H`ınh `e V in[i]. H`ınh 1.8 minh ho.a ma˙’ng c´ac danh s´ach kˆ kˆ 1.6. - ˆe˙’ y D ´ rˇ`a ng, c´ac sˆo´ trong n´ `e cu˙’a V out[] (tu.o.ng u ut kˆ ´.ng, V in[]) l`a nh˜ u.ng chı˙’ sˆo´ cˆo.t (tu.o.ng u ´.ng, h`ang) trong ma trˆa.n kˆ `e cu˙’a d¯`oˆ thi. m`a o˙’. d¯´o sˆo´ 1 xuˆa´t hiˆe.n. Ngo`ai ra, trong . . . . . tru `o ng ho. p d¯`ˆo thi. vˆo hu ´o ng, hai danh s´ach kˆ `e n`ay l`a tr` ung nhau. u.c l`a nˆe´u mˆo˜i cung hoˇa.c ca.nh e ∈ E c´o mˆo.t tro.ng lu.o..ng w(e), Khi d¯`oˆ thi. c´o tro.ng sˆo´, t´ . `an mo˙’ rˆo.ng cˆa´u tr´ ta chı˙’ cˆ uc cu˙’a mˆo˜i n´ ut trong danh s´ach kˆ `e bˇa` ng c´ach thˆem mˆo.t tru.`o.ng lu.u tr˜u. tro.ng lu.o..ng cu˙’a cung. `e cu˙’a d¯`ˆo thi. c´o hu.´o.ng c´o thˆe˙’ d¯u.o..c c`ai d¯aˇ. t trong ngˆon C´ach biˆe˙’u diˆ˜en bˇa` ng danh s´ach kˆ ng˜u lˆa.p tr`ınh C v´o i c´ac khai b´ao trong thu. viˆe.n Graph.h (xem Phu. lu.c A). D . . - ˆe˙’ xˆay du..ng ma˙’ng c´ac danh s´ach kˆ `e V out[] v`a V in[] cho mˆo.t d¯`ˆo thi., ta c´o thˆe˙’ su˙’. du.ng c´ac thu˙’ tu.c MakeV out() v`a MakeV in() tu.o.ng u ´.ng. ut . d¯`aˆu N´ ... ... ... ... ... ... V in[1] ................................... A .. ... ... •............................................... v2 .. ... ... •............................................... v6 .. ... ... •................................................. NULL .. .. ... ... V in[2] .................................. B .. ... .... •............................................... v4 .. ... .... •............................................... NULL . . .... .... .... .... .... V in[3] .................................. C ... .. ... ... •............................................... v2 ... .. ... ... •............................................... v3 ... .. ... ... •................................................. v4 ... .. ... ... •............................................... v5 ... .. ... ... •............................................... NULL .. .. ... ... V in[4] .................................. D .. ... ... •............................................... v1 .. ... ... •............................................... NULL . . ..... ..... V in[5] .................................. E ... .. ... •................................................. v1 ... .. ... •................................................. NULL ... ... ... ... ... ... V in[6] ................................... F .. ... ... •................................................. v5 .. ... ... •................................................. NULL . . `e V in[] tu.o.ng u H`ınh 1.8: Danh s´ach kˆ ´.ng d¯`oˆ thi. trong H`ınh 1.6. Su˙’. du.ng c´ ac ma trˆ a.n liˆ en thuˆ ¯ı˙’nh-cung hoˇ o.c d ¯ı˙’nh-ca.nh a.c d Ma trˆa.n liˆen thuˆo.c d¯ı˙’nh-cung hoˇa.c d¯ı˙’nh-ca.nh cho ph´ep ch´ung ta mˆo ta˙’ d¯`ˆay d¯u˙’ cˆa´u tr´ uc cu˙’a mˆo.t d¯a d¯`oˆ thi. khˆong c´o khuyˆen. Tuy nhiˆen, do chı˙’ c´o hai phˆ . `an tu˙’ kh´ac khˆong trong mˆo˜i ˙ ’ ˙’ ˜ . . . cˆo.t, nˆen c´o thˆe biˆeu diˆen thˆong tin o˙’ da.ng th´ıch ho. p ho n. Ch´ ung ta d¯.inh ngh˜ıa hai ma˙’ng tuyˆe´n t´ınh α[] v`a β[] chiˆ `eu m trong d¯o´ v´o.i mˆo˜i cung hoˇa.c ca.nh ek , k = 1, 2, . . . , m, c´ac gi´a tri. α[k] v`a β[k] l`a c´ac chı˙’ sˆo´ cu˙’a c´ac d¯ı˙’nh m`a ek liˆen 20 http://www.ebook.edu.vn