Đồ thị và các thuật toán – Chương 4: Cây

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

Thêm vào BST

Báo xấu

29
lượt xem 3
download

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

Chương 4 cung cấp cho người học kiến thức cơ bản về cây. Nội dung trình bày cụ thể trong chương này gồm có: Cây Huffman, cây bao trùm, cây bao trùm tối thiểu, bài toán Steiner. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

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 4: Cây

Chu.o.ng 4 ˆ CAY 4.1 Mo˙’. d`au ¯ˆ Cˆay l`a mˆo.t trong nh˜ u.ng kh´ai niˆe.m quan tro.ng nhˆa´t cu˙’a l´ y thuyˆe´t d¯`oˆ thi., v`a thu.`o.ng xuˆa´t hiˆe.n trong nh˜ u.ng l˜anh vu..c ´ıt c´o liˆen quan d¯ˆe´n d¯`ˆo thi.. Trong chu.o.ng n`ay, tru.´o.c hˆe´t s˜e nghiˆen c´ u.u cˆay Huffman v`a nh˜ u.ng u ´.ng du.ng cu˙’a n´o trong viˆe.c n´en d˜ u. liˆe.u. Kˆe´ tiˆe´p ch´ ung ta x´et tr`ınh b`ay c´ac thuˆa.t to´an t`ım cˆay bao tr` um, cˆay bao tr` . . ˙’ ´ ˙’ ` . . ´ . um c´o tro.ng lu o. ng nho nhˆa t khi c´ac ca.nh cua d¯ˆo thi. d¯u o. c gˇan v´o i c´ac chi ph´ı (tro.ng lu.o..ng). Cˆay bao tr` um nho˙’ nhˆa´t cu˙’a d¯`ˆo thi. c´o nhiˆ `eu u´.ng du.ng trong nh˜ u.ng tru.`o.ng ho..p c´ac d¯u.`o.ng dˆa˜n (ˆo´ng dˆa˜n ga, dˆay dˆa˜n trong ma.ng d¯iˆe.n, v.v) d¯u.o..c su˙’. du.ng d¯ˆe˙’ nˆo´i n d¯iˆe˙’m v´o.i nhau theo c´ach tˆo´t nhˆa´t: tˆo˙’ng khoa˙’ng c´ach cu˙’a c´ac d¯u.`o.ng dˆa˜n l`a nho˙’ nhˆa´t. Nˆe´u n d¯iˆe˙’m d¯u.o..c nˆo´i v´o.i nhau trˆen mˆo.t mˇa.t phˇa˙’ng, ta c´o thˆe˙’ biˆe˙’u diˆ˜en bo˙’.i mˆo.t d¯`oˆ thi. d¯`ˆay d¯u˙’ trong d¯o´ c´ac chi ph´ı ca.nh l`a khoa˙’ng c´ach gi˜ u.a hai d¯iˆe˙’m tu.o.ng u ´.ng. Khi d¯´o cˆay bao tr` um v´o.i tro.ng . . . lu o. ng nho˙’ nhˆa´t s˜e cho ma.ng giao thˆong v´o i chi ph´ı ´ıt nhˆa´t. Nˆe´u c´o thˆe˙’ nˆo´i thˆem ngo`ai n d¯iˆe˙’m cho ph´ep, ta c´o thˆe˙’ thˆa.m ch´ı xˆay du..ng d¯u.o..c ma.ng v´o.i ch´ı ph´ı re˙’ ho.n v`a x´ac d¯i.nh n´o ch´ınh l`a gia˙’i quyˆe´t b`ai to´an Steiner. B`ai to´an sau n`ay s˜e d¯u.o..c d¯`ˆe cˆa.p o˙’. phˆ `an cuˆo´i chu.o.ng. - .inh ngh˜ıa 4.1.1 C´ac d¯i.nh ngh˜ıa sau cu˙’a cˆay (vˆo hu.´o.ng) l`a tu.o.ng d¯u.o.ng: D - `ˆo thi. liˆen thˆong c´o n d¯ı˙’nh v`a (n − 1) ca.nh. 1. D - `ˆo thi. liˆen thˆong khˆong c´o chu tr`ınh. 2. D - `ˆo thi. m`a mo.i cˇa.p d¯ı˙’nh d¯u.o..c nˆo´i v´o.i nhau bo˙’.i mˆo.t v`a chı˙’ mˆo.t dˆay chuyˆ 3. D `en so. cˆa´p. - `ˆo thi. liˆen thˆong v`a khi b´o.t mˆo.t ca.nh bˆa´t k` 4. D y th`ı mˆa´t t´ınh liˆen thˆong. 99 http://www.ebook.edu.vn
H`ınh 4.1 minh ho.a cˆay c´o ba˙’y d¯ı˙’nh v`a s´au ca.nh. v2 • ... ..... ..... ..... ........ .... ..... ..... ..... ..... .... ........ • v3 ..... ..... . ..... ..... ... ..... . ........ . . ..... ..... ..... ..... ..... ..... ..... ..... v1 •............ ... ......... ... ......... v4 • ......... . .... ......... ... ....... ....... ... ....... ... ... ....... ... ..... ..... ....... . . ..... ....... ... ... ....... .... ..... • v5 ... . ..... ... ... ... .. • ........ . . .... ... ... ... ... v6 ... ... • v7... `e cˆay. H`ınh 4.1: Mˆo.t v´ı du. vˆ Kh´ai niˆe.m vˆ `e cˆay nhu. mˆo.t thu..c thˆe˙’ cu˙’a to´an ho.c d¯u.o..c d¯u.a ra lˆ `an d¯`ˆau tiˆen bo˙’.i Kirchhoff [37] khi liˆen hˆe. v´o.i d¯.inh ngh˜ıa c´ac ma.ch co. ba˙’n d¯u.o..c su˙’. du.ng trong phˆan t´ıch c´ac ma.ng d¯iˆe.n. Khoa˙’ng 10 nˇam sau d¯o´, mˆo.t c´ach d¯oˆ. c lˆa.p, Cayley [11] d¯a˜ ph´at hiˆe.n la.i c´ac cˆay v`a nh˜u.ng t´ıch chˆa´t cu˙’a n´o khi nghiˆen c´ u.u c´ac t´ınh chˆa´t ho´a ho.c cu˙’a c´ac chˆa´t d¯`oˆng phˆan cu˙’a hydrocarbon. Cˆay c´o gˆo´c (c`on go.i l`a cˆay gia pha˙’) d¯u.o..c d¯.inh ngh˜ıa tu.o.ng tu.. nhu. sau: - i.nh ngh˜ıa 4.1.2 Cˆay c´o gˆo´c T l`a d¯`oˆ thi. c´o hu.´o.ng khˆong ma.ch m`a mo.i d¯ı˙’nh, ngoa.i tr` D u. mˆo.t d¯ı˙’nh (chˇa˙’ng ha.n v1 ), c´o bˆa.c trong bˇa` ng mˆo.t: bˆa.c trong cu˙’a d¯ı˙’nh v1 (go.i l`a gˆo´c cu˙’a cˆay) bˇa` ng khˆong; n´oi c´ach kh´ac, mo.i d¯ı˙’nh v ∈ T tˆ `on ta.i duy nhˆa´t mˆo.t d¯u.`o.ng d¯i t` u. gˆo´c d¯ˆe´n v. H`ınh 4.2 minh ho.a mˆo.t d¯`oˆ thi. l`a cˆay c´o gˆo´c v´o.i d¯ı˙’nh v1 l`a gˆo´c. T` u. d¯.inh ngh˜ıa suy ra rˇa` ng cˆay c´o gˆo´c n d¯ı˙’nh c´o (n − 1) cung v`a l`a d¯`ˆo thi. liˆen thˆong (khi bo˙’ qua hu.´o.ng trˆen c´ac cung). Cˆ`an ch´uy ´ rˇa` ng, c´o thˆe˙’ d¯.inh hu.´o.ng trˆen mˆo.t cˆay (vˆo hu.´o.ng) sao cho d¯`oˆ thi. thu d¯u.o..c l`a cˆay c´o gˆo´c: Ta chı˙’ cˆ`an cho.n mˆo.t d¯ı˙’nh tu` yy´, chˇa˙’ng ha.n v1 , l`am gˆo´c v`a d¯.inh hu.´o.ng c´ac cung theo dˆay chuyˆ `en t`u v1 d¯ˆe´n c´ac d¯ı˙’nh treo. Ngu.o..c la.i, nˆe´u bo˙’ qua c´ac hu.´o.ng trˆen cˆay . c´o gˆo´c ta thu d¯u.o..c mˆo.t cˆay. Cˆay gia pha˙’ m`a trong d¯o´ mˆo˜i ngu.`o.i d¯a`n ˆong biˆe˙’u thi. mˆo.t d¯ı˙’nh v`a c´ac cung d¯u.o..c v˜e t`u c´ac cha d¯ˆe´n c´ac con cu˙’a ho. l`a mˆo.t v´ı du. quen thuˆo.c cu˙’a cˆay c´o gˆo´c, gˆo´c cu˙’a cˆay l`a ngu.`o.i . d¯`aˆu tiˆen trong d`ong ho. m`a c´o thˆe˙’ x´ac d¯.inh d¯u.o..c. 100 http://www.ebook.edu.vn
v1 ..... • ...... ..... ......... ..... ......... ..... ..... ..... ..... ..... . ... ..... ...... ..... . . . . . ....... .............. .. .... . ..... ..... .. ..... ..... . ..... ..... .... ..... v2 ......... . ...... . .... v3 ..... ..... ..... ..... .. .. .. .. •.... ......... ... ....... ...... • ... .... ......... ..... ......... . ...... ............ . ... ........ ..... ... .... ........... ...... ..... ...... ..... ..... ..... . .... . ...... . ..... ..... ...... v6 ...... ...... ..... ..... ..... •. .. . .. • .. • . .. . ... ....... . .... ........ • ..... v4 v5 ..... ... . ........ . . ..... . ...... .. . ......... ..... v7 v8 ..... .... ..... ..... ..... ..... • . .... .... ........ ... ....... • ..... ..... . . ... ....... ....... ..... . .. . ......... ..... v9 ..... v10 ..... ..... ..... ..... ..... • .. . .. .. ......... ... ...... . . • ..... ..... . .. ........ . . . ... . ..... .. . ........... ..... v11 ..... ..... ..... ..... ..... ..... • ..... . • ..... v12 v13 `e cˆay c´o gˆo´c. H`ınh 4.2: Mˆo.t v´ı du. vˆ 4.2 Cˆ ay Huffman Tiˆe´n tr`ınh g´an d˜ay c´ac bit cho c´ac k´ `an n`ay ch´ y hiˆe.u go.i l`a m˜a ho´a. Trong phˆ ung ta mˆo.t ta˙’ ´ mˆo.t thuˆa.t to´an m˜a ho´a rˆa t quen thuˆo.c-thuˆa.t to´an m˜a ho´a Huffman. 4.2.1 C´ ac bˆ o. m˜ o´t” a “tˆ Khi ta n´oi vˆ `e m˜a ho´a c´o ngh˜ıa l`a g´an d˜ay c´ac bit cho c´ac phˆ `an tu˙’. cu˙’a mˆo.t ba˙’ng ch˜ u. c´ai. Tˆa.p c´ac chuˆo˜i nhi. phˆan go.i l`a bˆo. m˜a v`a c´ac phˆ `an tu˙’. cu˙’a ch´ung go.i l`a t` u. m˜a. Mˆo.t ba˙’ng ch˜ . . u c´ai l`a mˆo.t tˆa.p ho. p c´ac k´ y hiˆe.u, go.i l`a c´ac k´ . y tu. . Chˇa˙’ng ha.n, ba˙’ng ch˜ u. c´ai su˙’. du.ng trong hˆ `au hˆe´t c´ac s´ach (tiˆe´ng Anh) gˆ `om 26 k´ y tu.. thu.`o.ng, 26 k´ y tu.. hoa, v`a c´ac dˆa´u ngˇa´t cˆau . (nhu dˆa´u phˆa˙’y). M˜a ASCII (viˆe´t tˇa´t cu˙’a c´ac ch˜ . u c´ai d¯`ˆau tiˆen cu˙’a chuˆo˜i American Standard Code for Information Interchange cu˙’a k´ . y tu. A l`a 01000001, cu˙’a k´ y tu.. a l`a 01100001 v`a k´ y . tu. , l`a 0011010. Ch´ uy ` ´ ˙’. ˙ ’ ´ rˇa ng trong m˜a ASCII sˆo c´ac bit su du.ng d¯ˆe biˆeu diˆen c´ac k´ ˙ ’ ˜ . y tu. l`a bˇa` ng nhau. M˜a nhu. vˆa.y go.i l`a m˜a c´o d¯ˆo. d`ai cˆo´ d¯.inh. Nˆe´u ta muˆo´n gia˙’m sˆo´ c´ac bit d¯`oi ho˙’i d¯ˆe˙’ biˆe˙’u diˆ˜en c´ac thˆong b´ao kh´ac nhau, ta cˆ `an c´ac chuˆo˜i bit biˆe˙’u diˆ˜en k´ y tu.. c´o d¯oˆ. d`ai (n´oi chung) khˆong bˇa` ng nhau. Nˆe´u biˆe˙’u diˆ˜en c´ac bit d`ai ho n cho c´ac k´ . y tu. thu.`o.ng xuyˆen xuˆa´t . hiˆe.n v`a ngu.o..c la.i, ch´ ung ta c´o thˆe˙’, vˆ`e trung b`ınh, gia˙’m sˆo´ bit biˆe˙’u diˆ˜en c´ac k´ y hiˆe.u. Chˇa˙’ng . ha.n, m˜a Morse [31] su˙’ du.ng c´ac t` . ´ . u m˜a ngˇan ho n cho c´ac k´ y tu. xuˆa t hiˆe.n thu.`o.ng xuyˆen: . ´ m˜a cu˙’a cu˙’a a l`a ·−, cu˙’a e l`a ·, trong khi cu˙’a z l`a − − · · · · , q l`a − − ·−, j l`a · − − − . Tuy nhiˆen d¯oˆ. d`ai trung b`ınh cu˙’a m˜a khˆong pha˙’i l`a tiˆeu chuˆa˙’n quan tro.ng khi thiˆe´t kˆe´ 101 http://www.ebook.edu.vn
mˆo.t bˆo. m˜a “tˆo´t”. X´et v´ı du. sau. Gia˙’ su˙’. ba˙’ng ch˜ u. c´ai gˆ `om bˆo´n k´y tu.. a1 , a2 , a3 , a4 v´o.i c´ac . . x´ac suˆa´t xuˆa´t hiˆe.n tu o ng u. ´ ng l`a P (a1 ) = 2 , P (a2 ) = 4 , P (a3 ) = 8 , P (a4 ) = 81 . Entropy cu˙’a 1 1 1 m˜a nguˆ `on n`ay l`a 1.75 bit/k´ y hiˆe.u (xem [31] d¯ˆe˙’ c´o kh´ai niˆe.m vˆ`e entropy). X´et c´ac bˆo. m˜a ` ˙ ’ . ˙ trong nguˆon n`ay cho bo i bang sau’ y tu.. C´ac k´ M˜a C1 M˜a C2 M˜a C3 M˜a C4 a1 1 1 1 1 a2 1 0 01 10 a3 0 11 001 100 a4 01 00 000 1000 - ˆo. d`ai trung b`ınh D 1.125 1.125 1.75 1.875 - ˆo. d`ai trung b`ınh l cu˙’a mˆo˜i m˜a x´ac d¯i.nh bo˙’.i D 4 X l= P (ai )n(ai ) (bit/k´ y hiˆe.u), i=1 u. m˜a ai . trong d¯o´ n(ai ) l`a sˆo´ c´ac bit cu˙’a t` Du..a trˆen d¯oˆ. d`ai trung b`ınh, m˜a C1 l`a tˆo´t nhˆa´t. Tuy nhiˆen, c´ac m˜a cˆ `an pha˙’i c´o kha˙’ nˇang truyˆ . . . . `en thˆong tin sao cho ngu `o i nhˆa.n c´o thˆe˙’ hiˆe˙’u d¯u o. c r˜o r`ang. Hiˆe˙’n nhiˆen m˜a C1 khˆong c´o t´ınh chˆa´t n`ay: V`ı ca˙’ hai k´ y hiˆe.u a1 v`a a2 d¯`ˆeu d¯u.o..c g´an l`a 1 nˆen khi nhˆa.n d¯u.o..c . . thˆong tin l`a 1, ngu `o i nhˆa.n khˆong thˆe˙’ phˆan biˆe.t d¯´o l`a k´ y hiˆe.u a1 hay a2 . Ch´ ung ta muˆo´n mˆo˜i k´ . . y hiˆe.u d¯u o. c g´an duy nhˆa´t mˆo.t t` . u m˜a. M˜a C2 c´o c´ac k´ y tu.. d¯u.o..c g´an c´ac chuˆo˜i bit kh´ac nhau cho c´ac k´ y tu... Tuy nhiˆen, gia˙’ . . . . . . su˙’ m˜a ho´a d˜ay a2 a1 a1 d¯u o. c 011 v`a gu˙’ i d¯i chuˆo˜i bit n`ay. Ngu `o i nhˆa.n chuˆo˜i 011 c´o mˆo.t sˆo´ c´ach gia˙’i m˜a: a2 a1 a1 hoˇa.c a2 a3 . D `eu n`ay c´o ngh˜ıa l`a mˆo.t d˜ay d¯u.o..c m˜a ho´a v´o.i bˆo. m˜a C2 - iˆ . . th`ı d˜ay n`ay c´o thˆe˙’ d¯u o. c gia˙’i m˜a khˆong tr`ung v´o.i thˆong b´ao ban d¯`aˆu. N´oi chung, d¯ˆay khˆong `eu ch´ pha˙’i l`a d¯iˆ ung ta mong muˆo´n khi thiˆe´t kˆe´ c´ac bˆo. m˜a. Ch´ ung ta muˆo´n c´o t´ınh chˆa´t gia˙’i ´ m˜a duy nhˆa t; t´ . u c l`a mo.i d˜ay c´ac t` . u m˜a chı c´o duy nhˆa t mˆo.t c´ach gia˙’i m˜a. C´o thˆe˙’ ch´ ˙ ’ ´ u.ng minh c´ac m˜a C3 v`a C4 thoa˙’ m˜an t´ınh chˆa´t n`ay. Mˇa.c d` u viˆe.c kiˆe˙’m tra t´ınh duy nhˆa´t khi gia˙’i m˜a l`a kh´o, ta c´o thˆe˙’ ch´ u.ng minh t´ınh . chˆa´t n`ay cho bˆo. m˜a C3 du. a trˆen thuˆo.c t´ınh cu˙’a bˆo. m˜a: khˆong c´o t` . u m˜a n`ao trong m˜a C3 u. m˜a kh´ac. Bˆo. m˜a nhu. vˆa.y go.i l`a m˜a tiˆ `en tˆo´” cu˙’a t` l`a “tiˆ `en tˆo´. Mˆo.t c´ach d¯o.n gia˙’n d¯ˆe˙’ kiˆe˙’m tra mˆo.t bˆo. m˜a c´o pha˙’i l`a tiˆ`en tˆo´ hay khˆong ta v˜e cˆay nhi. phˆan (mˆo˜i d¯ı˙’nh c´o bˆa.c ≤ 2) tu.o.ng . . . . ´ ng v´o i bˆo. m˜a. Cˆay d¯u o. c v˜e xuˆa´t ph´at t` u u. mˆo.t n´ ut d¯o.n (n´ ut gˆo´c) v`a mˆo˜i n´ ut trong c´o bˆa.c . ngo`ai nho˙’ ho n hoˇa.c bˇ`a ng hai. Mˆo.t trong hai nh´anh con tu o ng u . . . ´ ng bit 1 v`a nh´anh c`on la.i 102 http://www.ebook.edu.vn
tu.o.ng u´.ng bit 0. D - ˆe˙’ thuˆa.t tiˆe.n, ta quy u.´o.c nh´anh con bˆen pha˙’i tu.o.ng u ´.ng 0 v`a nh´anh con . . bˆen tr´ai tu o ng u. ´ ng 1. Theo c´ach n`ay, c´ac cˆay nhi. phˆan tu o ng u . . . ´ ng c´ac m˜a C2 , C3 v`a C4 cho - . trong H`ınh 4.3. (Dˆe˙’ d¯o n gia˙’n, ta s˜e khˆong v˜e c´ac m˜ ui tˆen trong c´ac cˆay nhi. phˆan). • .. ..... ..... 1...................... . ..... ..... • .. .......... ..... ......... •.................... 1 . ..... . .. ..... ..... ..... ..... ..... 0 ..... a1 ................0 .. ...... . ..... ..... ..... ..... ..... ..... • . .......... ..... ......... • . .... . ..... • .... ....... ..... ......... • ..... ..... ..... 1 . ..... . .. . ..... ..... ..... ..... ..... ..... 0 a1 1 ..... ...... . .. .. ..... ..... 0 ..... ..... a2 0 ..... ..... ..... ..... .. ...... ..... .. ....... ..... ..... ..... ..... .... . ..... .... . ..... ..... • .. .. . ... . .. . .... • ..... ..... ..... • . ..... . .... • . ........ ..... ......... • ..... ..... ..... 1 a1 a2 0 a2 a3 0 ... ..... ..... .. . ... . . . .... . .. ..... ..... ..... 1 ..... .. .. . ...... ..... ..... 0 ..... ..... ..... ..... ..... .. .. . .... ..... ..... ......... ..... ..... ..... .... ..... .... ..... ..... . . . . ..... • . ..... • ..... . • . ..... • ... • ..... a3 a4 a3 a4 a4 M˜a C2 M˜a C3 M˜a C4 H`ınh 4.3: Ch´uy´ rˇ`a ng ngo`ai n´ ut gˆo´c, cˆay nhi. phˆan c´o hai loa.i n´ ut: c´ac n´ ut l´a c´o bˆa.c ngo`ai bˇa` ng khˆong; v`a c´ac n´ ut trong c´o bˆa.c ngo`ai kh´ac khˆong. Trong bˆo. m˜a tiˆ u. m˜a chı˙’ tu.o.ng `en tˆo´, c´ac t` ´.ng c´ac n´ u ut l´a. M˜a C4 khˆong pha˙’i l`a m˜a tiˆ `en tˆo´ do tˆ`on ta.i t`u. m˜a tu.o.ng u ´.ng n´ ut trong. . . . ut l´a cho ta biˆe˙’u diˆ˜en chuˆo˜i bit tu o ng u u gˆo´c d¯ˆe´n c´ac n´ Duyˆe.t cˆay t` . ´ ng k´ y hiˆe.u. Mˆo˜i nh´anh d¯o´ng g´op mˆo.t bit v`ao t` u. m˜a cu˙’a n´o: bit 1 cho nh´anh tr´ai v`a bit 0 cho nh´anh pha˙’i. M˜a tiˆ`en tˆo´ luˆon luˆon d¯u.o..c gia˙’i m˜a duy nhˆa´t nhu.ng ngu.o..c la.i khˆong d¯u ´ng (chˇa˙’ng ha.n m˜a C4 ). Tuy nhiˆen c´o thˆe˙’ ch´ u ng minh rˇa` ng bˆo. m˜a c´o thˆe˙’ gia˙’i m˜a duy nhˆa´t tu.o.ng d¯u.o.ng . v´o.i m˜a tiˆ `en tˆo´ theo ngh˜ıa: sˆo´ trung b`ınh c´ac bit biˆe˙’u diˆ˜en c´ac k´ y hiˆe.u bˇ`a ng nhau. 4.2.2 M˜ a Huffman `en tˆo´ v`a tˆo´i u.u v´o.i c´ac x´ac xuˆa´t cho tru.´o.c. Phu.o.ng ph´ap xˆay du..ng M˜a Huffman l`a m˜a tiˆ . m˜a Huffman du. a trˆen hai quan s´at sau: 1. Trong mˆo.t bˆo. m˜a tˆo´t u.u, c´ac k´ y hiˆe.u xuˆa´t hiˆe.n thu.`o.ng xuyˆen (c´o x´ac suˆa´t hay tˆ `an sˆo´ ´ . xuˆa t hiˆe.n l´o n) s˜e c´o c´ac t`. ´ . u m˜a ngˇan ho n c´ac k´ ´ y hiˆe.u ´ıt xuˆa t hiˆe.n. 2. Trong mˆo.t bˆo. m˜a tˆo´t u.u, hai k´ u. m˜a c` y hiˆe.u xuˆa´t hiˆe.n ´ıt nhˆa´t s˜e c´o c´ac t` ung d¯oˆ. d`ai. - ˆe˙’ xˆay du..ng m˜a Huffman, ch´ D ung ta c´o thˆe˙’ biˆe˙’u diˆ˜en qua cˆay nhi. phˆan m`a c´ac n´ ut l´a . . tu o ng u . ´ ng c´ac k´ y hiˆe.u. Duyˆe.t cˆay nhi. phˆan s˜e cho ta c´ac t` . u. u m˜a cu˙’a bˆo. m˜a: xuˆa´t ph´at t` 103 http://www.ebook.edu.vn
ut gˆo´c v`a d¯i d¯ˆe´n c´ac n´ n´ u. m˜a mˆo˜i lˆ ut l´a, thˆem bit 1 v`ao t` `an qua nh´anh tr´ai v`a bit 0 mˆo˜i lˆ `an . qua nh´anh pha˙’i. V´o i cˆay trong H`ınh 4.4, ta c´o biˆe˙’u diˆ˜en c´ac k´ . y tu. qua c´ac t` . . u m˜a nhu sau: y tu.. K´ M˜a ho´a A 1 O 00 R 010 S 0110 T 0111 •... ..... ..... ..... ......... 1..................... ..... ..... 0 ..... ..... ....... ..... .... ..... • ... .. . • ..... ..... ......... ..... ........ A 1 ..... ..... .. ... ..... ..... 0 ..... ..... ......... ..... ..... ... . ...... • .. .. . ..... . . .... ........ ..... • ..... .. 1 ..... ... ..... ... . ..... . . 0 ..... ..... O ..... ..... ..... ..... ..... . ... . .. .. . • ........ ... ....... ..... • ..... . 1 . ..... . .. . . ... . .. . ..... ....... 0 ..... R ..... ..... ..... ..... ..... •..... • ..... .. T S H`ınh 4.4: - ˆe˙’ gia˙’i m˜a mˆo.t chuˆo˜i bit, ch´ D ung ta bˇa´t d¯`aˆu t`u. gˆo´c v`a di chuyˆe˙’n do.c theo cˆay cho d¯ˆe´n khi gˇa.p k´ y tu. : d¯i theo nh´anh tr´ai nˆe´u d¯´o l`a bit 1, ngu.o..c la.i d¯i theo nh´anh pha˙’i. Chˇa˙’ng . ha.n, chuˆo˜i bit 01010111 . . tu o ng u . ´ ng t` u RAT. V´o i mˆo.t cˆay x´ac d¯.inh m˜a Huffman nhu. H`ınh 4.4, chuˆo˜i bit bˆa´t k` . . y d¯u.o..c gia˙’i m˜a duy nhˆa´t mˇa.c d` u c´ac k´y tu.. tu.o.ng u ´.ng v´o.i nh˜ u.ng chuˆo˜i bit c´o d¯ˆo. d`ai thay d¯oˆ˙’i. Huffman d¯a˜ chı˙’ ra thuˆa.t to´an xˆay du..ng m˜a Huffman t` u. ba˙’ng c´ac tˆ `an sˆo´ xuˆa´t hiˆe.n cu˙’a c´ac k´ . . y tu. nhu sau: Thuˆ a.t to´ ay du..ng m˜ an xˆ a Huffman X´et chuˆo˜i cˆ u. n k´ `an m˜a ho´a s t` y tu.. v´o.i n ≥ 2. 1. Xˆay du..ng d˜ay tˆ y tu.. trong chuˆo˜i s. `an sˆo´ fi , i = 1, 2, . . . , n, xuˆa´t hiˆe.n cu˙’a c´ac k´ 104 http://www.ebook.edu.vn
2. Nˆe´u n = 2 (gia˙’ su˙’. f1 ≤ f2 ), xuˆa´t cˆay nhu. trong H`ınh 4.5 v`a d` u.ng. • ... ..... ..... ..... ......... ..... ..... . ...... . ..... 1 . . . ... . . ...... . . ..... ..... ..... ..... ..... 0 . ... . ..... .. . ..... .. ..... ..... ..... .. .... . ..... .. •..... • ..... f1 f2 H`ınh 4.5: 3. Gia˙’ su˙’. f v`a f 0 l`a hai tˆ `an sˆo´ nho˙’ nhˆa´t v`a f ≤ f 0 . Ta.o mˆo.t danh s´ach tˆ`an sˆo´ m´o.i bˇ`a ng c´ach thay f v`a f 0 bo˙’.i f + f 0 . Go.i thuˆa.t to´an n`ay su˙’. du.ng danh s´ach tˆ `an sˆo´ m´o.i d¯ˆe˙’ ta.o cˆay T 0 . Thay d¯ı˙’nh d¯u.o..c g´an nh˜an f + f 0 d¯ˆe˙’ nhˆa.n d¯u.o..c cˆay T trong H`ınh 4.6. Xuˆa´t T. • ...... ..... ......... ..... ..... ..... ..... . ...... ..... 1 . . ... . . ...... . . ..... ..... ..... .....0 ..... . .... ..... .. .. ..... .. .... . ..... .. .... . ..... ..... • .. ..... • ... f f0 H`ınh 4.6: `an sˆo´ V´ı du. 4.2.1 Cho ba˙’ng tˆ y tu.. K´ `an sˆo´ tˆ A 2 B 3 C 7 D 8 E 12 Khi d¯o´ cˆay Huffman tu.o.ng u ´.ng cho trong H`ınh 4.7. 4.3 Cˆ ay bao tr` um Ch´ung ta d¯a˜ nghiˆen c´ u.u riˆeng biˆe.t c´ac t´ınh chˆa´t cu˙’a mˆo.t cˆay, trong mu.c n`ay ch´ ung ta s˜e nghiˆen c´ u u cˆay khi gˇa´n n´o nhu. mˆo.t d¯`oˆ thi. con cu˙’a mˆo.t d¯`oˆ thi. kh´ac. Ch´ . ung ta biˆe´t rˇ`a ng cho d¯`ˆo thi. c´o m ca.nh, c´o thˆe˙’ xˆay du..ng d¯u.o..c 2m d¯`oˆ thi. con kh´ac nhau; r˜o r`ang l`a trong sˆo´ 105 http://www.ebook.edu.vn
• ....... .... ........ ..... ..... ..... ..... .. ...... . ..... ... . ..... .. . ..... ... ..... 1 . ... . .. . ... . . . .... . .. ..... ..... .....0 ..... . ... ..... ... .... ..... ....... ..... .. ..... ..... ..... .. ..... ..... ... ..... .... ... ... ... ....... .. . ....... . . • ..... • ... ......... ..... ......... ..... ..... ..... . 1 ..... .. ..... ..... ..... 0 1 ..... ..... . ..... ..... ..... ..... ..... 0 .. ....... ..... . . ........ ..... ..... .... ..... .... . ... . . .. . . . ...... . . .... ........ • • .. .... • ... ... ..... • .. 1 . ..... . .. . . ... . .. ..... ...... . ...... ..... 0 7 8 12 ..... ..... ..... • ..... .... ..... ..... • C D E 2 3 A B H`ınh 4.7: d¯o´ c´o mˆo.t v`ai d¯`ˆo thi. con l`a mˆo.t cˆay. Ch´ ung ta quan tˆam d¯ˆe´n mˆo.t loa.i cˆay d¯aˇ. c biˆe.t: “cˆay bao tr` um”. Kh´ai niˆe.m cˆay bao tr` um lˆan d¯`aˆu tiˆen d¯u.o..c su˙’. du.ng v`a ph´at triˆe˙’n l´ ` y thuyˆe´t vˆ `e . cˆay bo˙’ i nh`a vˆa.t l´ . . -u y ngu `o i D . . ´ c Kirchoff nˇam 1847. Kirchoff d¯a˜ su˙’ du.ng cˆay bao tr` um nhˇa` m . . ˙ ’ . . gia˙’i hˆe. c´ac phu o ng tr`ınh tuyˆe´n t´ınh d¯ˆe x´ac d¯.inh cu `o ng d¯oˆ. d`ong d¯iˆe.n trong mˆo˜i nh´anh v`a xung quanh ma.ch cu˙’a mˆo.t ma.ng d¯iˆe.n. - `ˆo thi. trong H`ınh 4.8(a) c´o cˆay bao tr` V´ı du. 4.3.1 D um trong H`ınh 4.8(b). b e b e • ................................................................................................. .... ..... ..... ........ ... .. .... . • • ..... .... ........................................................................................... • ..... ..... ..... .... ..... ...... ..... .... ... ..... ..... ..... ...... ... ..... ..... .. ...... . .... . .... .... ..... .... ... ..... .. . . .. .. .. ... ..... . ..... ..... ...... . . .... ... . ...... . .... . .. ... ... .... .. . . . ..... .... . .... ... . .. ... ..... a• . .............................................................................................................. ..... ..... . .. . . .. . . ..... .. ..... •c ... ... ... a• .................................................................................................... ..... ..... •c ..... ..... ..... .. . .. ..... ..... ..... ..... . ... . ...... ... ..... ..... ..... ... .. ..... ... ..... ..... ..... ...... ...... ... ..... ..... ..... .... ..... ..... ..... ... . . .. ..... ... ..... ..... ..... .. . ...... ... ..... ..... ..... ... . ..... ..... ..... ... . .. ....... .... ..... ..... ..... ..... .. ... . ..... ..... ........................................................................................................... • • • ..... • ..... d f d f (a) (b) H`ınh 4.8: - i.nh ngh˜ıa 4.3.2 Cˆay T d¯u.o..c go.i l`a cˆay bao tr` D um cu˙’a d¯`oˆ thi. liˆen thˆong G nˆe´u T l`a d¯`oˆ . u a tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a G. thi. con cu˙’a G v`a T ch´ - i.nh l´ D y 4.3.3 D - `ˆo thi. G = (V, E) c´o d¯`ˆo thi. bˆo. phˆa.n l`a mˆo.t cˆay nˆe´u v`a chı˙’ nˆe´u G liˆen thˆong. N´oi c´ach kh´ac, cho tru.´o.c mˆo.t d¯`ˆo thi. liˆen thˆong v`a c´o n d¯ı˙’nh, bao gi`o. ta c˜ ung c´o thˆe˙’ ˙ ’ . . bo˙’ d¯i mˆo.t sˆo´ ca.nh cu˙’ a G d¯ˆe d¯u o. c mˆo.t cˆay ch´. u a tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’ a G (cˆay c´o n d¯ı˙’nh). 106 http://www.ebook.edu.vn
Ch´ u.ng minh. D - iˆ `an. Nˆe´u G liˆen thˆong th`ı ta thu˙’. t`ım xem c´o ca.nh n`ao m`a khi x´oa `eu kiˆe.n cˆ d¯i khˆong l`am cho d¯`ˆo thi. mˆa´t t´ınh liˆen thˆong khˆong. Nˆe´u khˆong c´o mˆo.t ca.nh n`ao nhu. vˆa.y th`ı G l`a mˆo.t cˆay; nˆe´u c´o mˆo.t ca.nh nhu. vˆa.y th`ı x´oa n´o d¯i, v`a ta la.i d¯i t`ım mˆo.t ca.nh m´o.i d¯ˆe˙’ x´oa... Cho t´o.i khi khˆong thˆe˙’ x´oa mˆo.t ca.nh n`ao d¯u.o..c n˜ u.a th`ı ta c´o mˆo.t cˆay m`a tˆa.p ho..p c´ac ´ng bˇa` ng V. d¯ı˙’nh cu˙’a n´o d¯u D `eu kiˆe.n d¯u˙’. Gia˙’ su˙’. a, b l`a hai d¯ı˙’nh trong G v`a do d¯o´ thuˆo.c cˆay bao tr` - iˆ um T cu˙’a G. Khi `on ta.i dˆay chuyˆ d¯o´ tˆ `en µ trong T t` u. a d¯ˆe´n b. Suy ra µ c˜ ung thuˆo.c G. Vˆa.y G liˆen thˆong. / Ch´ ung ta s˜e su˙’. du.ng thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu rˆo.ng d¯ˆe˙’ xˆay du..ng cˆay bao tr` um cu˙’a d¯`ˆo thi. liˆen thˆong. 4.3.1 Thuˆ a.t to´ e´m theo chiˆ an t`ım kiˆ `eu rˆ o.ng x´ ac d ¯i.nh cˆ ay bao tr` um Trong thuˆa.t to´an n`ay, S k´ y hiˆe.u l`a mˆo.t d˜ay. - `ˆo thi. liˆen thˆong G := (V, E) v´o.i c´ac d¯ı˙’nh d¯u.o..c d¯´anh sˆo´ th´ Nhˆa.p: D u. tu.. v1 , v 2 , . . . , v n . Xuˆa´t: Cˆay bao tr` um T. 1. [Kho˙’.i ta.o] D - ˇa.t S := [v1 ] v`a T l`a d¯`ˆo thi. gˆ `om d¯ı˙’nh v1 v`a khˆong c´o ca.nh. K´ y hiˆe.u v1 l`a ´ d¯ı˙’nh gˆoc. 2. [Thˆem ca.nh] V´o.i mˆo˜i x ∈ S, theo th´u. tu.., thˆem ca.nh (x, y) ∈ E v`a d¯ı˙’nh y (theo th´ u. . . tu. ) v`ao T nˆe´u T ∪ (x, y) khˆong ta.o th`anh chu tr`ınh. Nˆe´u khˆong c´o ca.nh nhu vˆa.y, d`u.ng. T l`a cˆay bao tr` um. 3. [Cˆa.p nhˆa.t S] Thay S bo˙’.i con (trong T ) cu˙’a S theo th´ u. tu... Chuyˆe˙’n sang Bu.´o.c 2. D- ˆe˙’ t`ım cˆay bao tr` um cu˙’a d¯`oˆ thi. liˆen thˆong ta c`on c´o thˆe˙’ d` ung thuˆa.t to´an t`ım kiˆe´m ` . theo chiˆeu sˆau (c`on go.i l`a quay lui) nhu sau: 4.3.2 Thuˆ a.t to´ e´m theo chiˆ an t`ım kiˆ `eu sˆ au x´ ac d ¯i.nh cˆ ay bao tr` um - `ˆo thi. liˆen thˆong G := (V, E) v´o.i c´ac d¯ı˙’nh d¯u.o..c d¯´anh sˆo´ th´ Nhˆa.p: D u. tu.. v1 , v 2 , . . . , v n . Xuˆa´t: Cˆay bao tr` um T. 107 http://www.ebook.edu.vn
1. [Kho˙’.i ta.o] D - ˇa.t w := v1 v`a T l`a d¯`ˆo thi. gˆ `om d¯ı˙’nh v1 v`a khˆong c´o ca.nh. K´ y hiˆe.u v1 l`a d¯ı˙’nh gˆo´c. 2. [Thˆem ca.nh] Cho.n ca.nh (w, vk ) v´o.i chı˙’ sˆo´ k nho˙’ nhˆa´t sao cho viˆe.c thˆem ca.nh n`ay v`ao T khˆong ta.o ra chu tr`ınh. Nˆe´u khˆong tˆ `on ta.i, chuyˆe˙’n sang Bu.´o.c 3. Ngu.o..c la.i, thˆem ca.nh (w, vk ) v`a d¯ı˙’nh vk v`ao T ; d¯aˇ. t w := vk v`a chuyˆe˙’n sang Bu.´o.c 2. 3. [Kˆe´t th´ uc?] Nˆe´u w = v1 , thuˆa.t to´an d` u.ng, T l`a cˆay bao tr` um. 4. [Quay lui] D- ˇa.t x l`a cha cu˙’a w (trong T ); g´an w := x v`a chuyˆe˙’n sang Bu.´o.c 2. V´ı du. 4.3.4 D - `ˆo thi. trong H`ınh 4.9(a) c´o c´ac cˆay bao tr` um, H`ınh 4.9(b) v`a 4.9(c), d¯u.o..c xˆay du..ng theo c´ac thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu sˆau tu.o.ng u `eu rˆo.ng v`a chiˆ ´.ng. a a a • ......... ..... ........ • ......... ..... ........ •..... .... ..... ..... ..... ..... ..... ....... ..... ....... ..... . ..... . ..... ..... ..... ..... ..... ..... ..... .... . ..... .... .... ..... .. .. ..... .... . . .......................................................................... . .. .. ..... ..... •c . b• .. . ... ............. ... .... ....... . . . ........... . .... .... ......... b• .. . .... ............ ... .... ....... . . ...... •c ..... ........ ... ..... b• ................................................................... •c .... .. ... ... .. . .. ...... ..... ..... ... ........ ..... .... ........ . .... .. ...... .... ........ ..... . ...... . . ..... ....... . . ..... .. . . ... ... ..... ...... .. ..... . ..... . ... ..... ..... ..... ........ .. .... ..... ... .. .... ..... ... .... ..... . ... . . . ... ...... ..... .... ..... ... ..... .... ... ..... . . . ... ..... d• • •f d• • •f d• • •f . . ..... ......... ... ........ . ... ..... ..... ..... ... . ..... ..... .... ..... . ..... ....... . . . ..... .... .... ..... ...... ..... ..... . .. ... ..... . .... ..... ..... .. ..... ..... ..... ..... ... ....... . .. . .. e ... . .... ..... ....... ..... .... ........ . . . . . . ...... . ... . ... ... ... e ... ... ... ..... ..... ..... . .... . ..... e . ..... . ..... ..... ... ..... ..... .... .... ..... .. .... ..... .. .... .... ... ..... ... ... ..... ........ .... ............ ... ... ..... ..... ..... • ............................................................................ ..... ..... • ..... .. ...... • ..... • .. • ..................................................................... • .. ..... ..... ..... ..... i ..... ..... ..... ..... .... j .... ..... i ..... ..... ..... j i .. ..... .....j ..... ..... ..... ..... ..... ........ ..... .... ..... .... • ....... • .. • ..... k k k (a) (b) (c) - `ˆo thi. G. (b) Cˆay bao tr` H`ınh 4.9: (a) D um sinh bo˙’.i thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu rˆo.ng. (c) Cˆay bao tr` . um sinh bo˙’ i thuˆa.t to´an t`ım kiˆe´m theo chiˆ`eu sˆau. 4.3.3 T`ım cˆ um du..a trˆ ay bao tr` e´n t´ınh en hai ma˙’ ng tuyˆ - ˆe˙’ c`ai d¯ˇa.t c´ac thuˆa.t to´an t`ım kiˆe´m theo chiˆ D `eu rˆo.ng v`a chiˆ`eu sˆau trˆen d¯`oˆ thi. liˆen thˆong G t`ım cˆay bao tr` um T ta c´o thˆe˙’ d` ung cˆa´u tr´ uc d˜ . u liˆe.u ma trˆa.n kˆ`e hay ca˙’i biˆen, ma˙’ng c´ac danh s´ach kˆe Vout []. Tuy nhiˆen, trong tru `o ng ho. p d¯oˆ thi. d¯u o. c biˆeu diˆ˜en bo˙’.i hai ma˙’ng tuyˆe´n t´ınh ` . . . ` . . ˙’ α v`a β th`ı c´ach tiˆe´p cˆa.n sau s˜e hiˆe.u qua˙’ ho.n. Ngo`ai ra, phu.o.ng ph´ap sau n`ay c˜ ung cho ta mˆo.t “r` . u ng” (tˆa.p c´ac cˆay bao tr` um) ch´ . . . . u a (n − p) ca.nh trong tru `o ng ho. p d¯`oˆ thi. c´o p > 1 ` ˙ ’ th`anh phˆan liˆen thˆong. Hiˆen nhiˆen, v´o i nh˜ . u.ng thuˆa.t to´an xˆay du..ng cˆay bao tr` um ta c´o thˆe˙’ kiˆe˙’m tra d¯`oˆ thi. c´o liˆen thˆong hay khˆong, v`a nˆe´u n´o khˆong liˆen thˆong th`ı c´o thˆe˙’ x´ac d¯.inh c´ac th`anh phˆ `an liˆen thˆong. Nˆe´u mˇa.t kh´ac, d¯`oˆ thi. c´o tro.ng sˆo´ th`ı ch´ ung ta c´o thˆe˙’ t`ım cˆay bao tr` . . um c´o tˆo˙’ng tro.ng lu o. ng nho˙’ nhˆa´t (xem Phˆ . `an 4.4). Ho n n˜ . u a ch´ ung ta c˜ ung c´o thˆe˙’ xˆay . . du. ng hˆe. c´ac chu tr`ınh d¯oˆ. c lˆa.p du. a trˆen cˆay bao tr` . um cu˙’a d¯`oˆ thi. nhu trong Phˆ `an 4.3.4. 108 http://www.ebook.edu.vn
X´et d¯`ˆo thi. vˆo hu.´o.ng G khˆong c´o khuyˆen n d¯ı˙’nh v`a m ca.nh. C´ac d¯ı˙’nh d¯u.o..c g´an nh˜an v1 , v2 , . . . , vn , v`a d¯`oˆ thi. x´ac d¯.inh bo˙’.i hai ma˙’ng tuyˆe´n t´ınh α, β, trong d¯´o αi v`a βi , i = 1, 2, . . . , m, l`a c´ac d¯ı˙’nh d¯u.o..c liˆen thuˆo.c bo˙’.i ca.nh ei . Mˆo˜i bu.´o.c lˇa.p cu˙’a thuˆa.t to´an, mˆo.t ca.nh m´o.i d¯u.o..c d¯u.a v`ao kiˆe˙’m tra d¯ˆe˙’ x´ac d¯.inh c´ac d¯ı˙’nh cu˙’a ca.nh d¯o´ c´o xuˆa´t hiˆe.n trong cˆay n`ao d¯´o (d¯˜a d¯u.o..c thiˆe´t lˆa.p o˙’. bu.´o.c tru.´o.c; bu.´o.c . d¯`aˆu tiˆen ch´ung ta chu.a c´o cˆay bao tr` um n`ao). O˙’ bu.´o.c th´ u. i, 1 ≤ i ≤ m, khi kiˆe˙’m tra ca.nh (αi , βi ) c´o nˇam tru.`o.ng ho..p xa˙’y ra: 1. Nˆe´u ca˙’ hai d¯ı˙’nh khˆong nˇ`a m trong bˆa´t c´ u. mˆo.t cˆay n`ao d¯a˜ d¯u.o..c xˆay du..ng o˙’. (i − 1) . . . . . . bu ´o c tru ´o c, khi d¯o´ c´ac d¯ı˙’nh αi , βi d¯u o. c g´an sˆo´ th`anh phˆ `an liˆen thˆong l`a sˆo´ c, sau d¯o´ . tˇang c lˆen mˆo.t d¯o n vi.. 2. Nˆe´u αi thuˆo.c cˆay Tj c`on βi thuˆo.c cˆay Tk (j, k = 1, . . . , c v`a j < k), ca.nh th´ u. i d¯u.o..c su˙’. du.ng d¯ˆe˙’ nˆo´i hai cˆay n`ay; do d¯´o, mo.i d¯ı˙’nh trong cˆay Tk d¯u.o..c g´an l`a sˆo´ th`anh phˆ `an ˙ ’ ˙ ’ liˆen thˆong cua Tj . Gi´a tri. c giam mˆo.t d¯o n vi... ung v´o.i mˆo.t sˆo´ ca.nh kh´ac ung nˇ`a m trong mˆo.t cˆay, th`ı ca.nh (αi , βi ) c` 3. Nˆe´u ca˙’ hai d¯ı˙’nh c` . cu˙’a cˆay s˜e ta.o th`anh mˆo.t chu tr`ınh v`a do d¯o´ khˆong xu˙’ l´ y tru.`o.ng ho..p n`ay. 4. Nˆe´u d¯ı˙’nh αi thuˆo.c cˆay Tj c`on βi khˆong thuˆo.c cˆay n`ao, khi d¯´o ca.nh (αi , βi ) d¯u.o..c thˆem v`ao cˆay Tj bˇ`a ng c´ach g´an sˆo´ th`anh phˆ `an liˆen thˆong cu˙’a Tj cho d¯ı˙’nh βi . 5. Nˆe´u d¯ı˙’nh βi thuˆo.c cˆay Tk c`on αi khˆong thuˆo.c cˆay n`ao, khi d¯o´ ca.nh (αi , βi ) d¯u.o..c thˆem v`ao cˆay Tk bˇ`a ng c´ach g´an sˆo´ th`anh phˆ `an liˆen thˆong cu˙’a Tk cho d¯ı˙’nh αi . - ˆe˙’ thu..c hiˆe.n viˆe.c kiˆe˙’m tra c´ac d¯ı˙’nh cuˆo´i cu˙’a mˆo.t ca.nh d¯u.o..c kha˙’o s´at c´o xuˆa´t hiˆe.n D trong cˆay n`ao khˆong, ch´ ung ta xˆay du..ng mˆo.t ma˙’ng tuyˆe´n t´ınh n phˆ `an tu˙’. Vertex[]. Khi mˆo.t ca.nh (vi , vj ) nˇa` m trong cˆay th´ . u c th`ı c´ac phˆ . `an tu˙’ th´u i v`a j cu˙’a ma˙’ng n`ay d¯u.o..c d¯aˇ. t l`a c. . Trong c´ac qu´a tr`ınh xu˙’. l´ y kˆe´ sau, khi mˆo.t ca.nh kh´ac (αi , βi ) d¯u.o..c d¯u.a v`ao kiˆe˙’m tra, ch´ung ta chı˙’ cˆ `an tu˙’. th´ `an kiˆe˙’m tra c´ac phˆ u. αi v`a βi trong ma˙’ng Vertex[] c´o kh´ac 0 khˆong. Phˆ`an tu˙’. th´ u. q trong ma˙’ng Vertex[] bˇa` ng 0 chı˙’ ra rˇ`a ng d¯ı˙’nh th´ u. q n`ay khˆong nˇa` m trong bˆa´t u. cˆay n`ao. Kˆe´t th´ c´ uc chu.o.ng tr`ınh, ma˙’ng Vertex[] cho ch´ ung ta biˆe´t c´ac th`anh phˆ `an liˆen thˆong cu˙’a d¯`oˆ thi. G. Nhˆa.n x´et rˇa` ng, cˆay khˆong chı˙’ d¯u.o..c mˆo ta˙’ bo˙’.i tˆa.p c´ac d¯ı˙’nh. Bo˙’.i vˆa.y, ch´ ung ta cˆ `an c´o ˙ ’ ˙’ ´ mˆo.t mang c´ac ca.nh d¯ˆe xuˆa t d˜ . - ˙ ’ ´ u liˆe.u. Dˇa.t mang n`ay l`a Edge[]. Nˆeu ca.nh th´ . ` u i nˇa m trong u. c, ta c´o Edge[k] = c; ngu.o..c la.i, n´o d¯u.o..c d¯ˇa.t bˇ`a ng 0. Tˆa´t ca˙’ c´ac phˆ cˆay th´ `an tu˙’. 0 trong ma˙’ng n`ay tu.o.ng u ´.ng v´o.i c´ac khuyˆen cˆo lˆa.p (t´ u.c l`a c´ac ca.nh khˆong nˇ`a m trong bˆa´t c´ u. cˆay bao tr`um hay r` . u ng n`ao). Ma˙’ng n`ay c` . ung v´o i c´ac ma˙’ng α v`a β, x´ac d¯.inh duy nhˆa´t cˆay bao tr`um (hoˇa.c r`. . . . u ng) d¯u o. c sinh bo˙’ i thuˆa.t to´an n`ay. 109 http://www.ebook.edu.vn
Trong thuˆa.t to´an n`ay, v`ong lˇa.p ch´ınh thu..c hiˆe.n m lˆ `an. Th`o.i gian d¯`oi ho˙’i d¯ˆe˙’ kiˆe˙’m tra c´ac d¯ı˙’nh c´o xuˆa´t hiˆe.n trong cˆay hay khˆong l`a hˇa` ng sˆo´-khˆong phu. thuˆo.c v`ao n v`a m. Do d¯o´ th`o.i gian thu..c hiˆe.n thuˆa.t to´an tı˙’ lˆe. v´o.i m1 . Trong tru.`o.ng ho..p m À n, ta c´o thˆe˙’ gia˙’m th`o.i gian thu..c hiˆe.n bˇ`a ng c´ach lu.u tr˜ u. mˆo.t biˆe´n d¯ˆe´m sˆo´ c´ac ca.nh d¯u.o..c d¯aˇ. t v`ao cˆay. Khi biˆe´n . . n`ay d¯a.t gi´a tri. (n − 1) chu o ng tr`ınh s˜e kˆe´t th´ uc (nˆe´u d¯`ˆo thi. liˆen thˆong; tr´ai la.i ta cˆ `an kiˆe˙’m tra mo.i ca.nh). um du..a trˆen hai ma˙’ng tuyˆe´n t´ınh α[] Thu˙’ tu.c sau minh ho.a thuˆa.t to´an t`ım cˆay bao tr` v`a β[] : void SpaningTree() { byte i, j, Tempt, Count = 0; byte Vertex[MaxVertices], Edge[MaxEdges]; for (j = 1; j
Edge[i] = Vertex[alpha[i]]; Vertex[beta[i]] = Vertex[alpha[i]]; } else if (Vertex[alpha[i]] != Vertex[beta[i]]) { Edge[i] = Vertex[alpha[i]]; Tempt = Vertex[beta[i]]; for (j = 1; j
4.3.4 Thuˆ a.t to´ a´t ca˙’ c´ an t`ım tˆ ac cˆ ay bao tr` um `e co. ba˙’n c´o thˆe˙’ d¯u.a vˆ Viˆe.c phˆan t´ıch c´ac ma.ch d¯iˆe.n vˆ `e b`ai to´an t`ım tˆa´t ca˙’ c´ac cˆay bao tr` um cu˙’a d¯`oˆ thi. (xem [19]). Do tˆ `am quan tro.ng cu˙’a n´o, c´o nhiˆ `eu thuˆa.t to´an kh´ac nhau gia˙’i quyˆe´t b`ai to´an n`ay. Mˆo.t trong nh˜ u ng phu o ng ph´ap l`a ho´an d¯oˆ˙’i c´ac chu tr`ınh nhu. sau: Xuˆa´t ph´at . . . t` . u mˆo.t cˆay bao tr` um T n`ao d¯´o. V´o.i mˆo˜i ca.nh khˆong nˇa` m trˆen cˆay T, khi thˆem v`ao cˆay n`ay s˜e ta.o ra duy nhˆa´t mˆo.t chu tr`ınh. X´oa bo˙’ mˆo.t ca.nh bˆa´t k` y trong chu tr`ınh n`ay s˜e cho ta mˆo.t cˆay bao tr` um m´o.i. Do sˆo´ c´ac cˆay bao tr` um l`a rˆa´t l´o.n thˆa.m ch´ı ca˙’ v´o.i nh˜ u.ng d¯`oˆ thi. nho˙’, t´ınh hiˆe.u qua˙’ cu˙’a nh˜ u.ng thuˆa.t to´an gia˙’i quyˆe´t b`ai to´an rˆa´t quan tro.ng (xem [14]). Mˆo.t tˆo˙’ng quan cu˙’a c´ac . . phu o ng ph´ap n`ay l`a mˆo.t luˆa.n ´an tiˆe´n s˜ı cu˙’a Chase [12]. Chase d¯˜a chı˙’ ra rˇ`a ng thuˆa.t to´an d¯u.a ra bo˙’.i Minty c´o hiˆe.u qua˙’ nhˆa´t: liˆen tiˆe´p thu go.n d¯`ˆo thi. bˇ`a ng c´ac ph´ep to´an xo´a mˆo.t ca.nh v`a ho..p nhˆa´t c´ac d¯ı˙’nh d¯`aˆu cuˆo´i cu˙’a n´o. T` u. c´ac cˆay bao tr` um cu˙’a c´ac d¯`oˆ thi. thu go.n . (m`a nho˙’ ho n rˆa´t nhiˆ . . . `eu) ta c´o thˆe˙’ du. ng d¯u o. c tˆa´t ca˙’ c´ac cˆay bao tr` um cu˙’a d¯`ˆo thi. ban d¯`ˆau. -Dˆe˙’ ba˙’o d¯a˙’m thuˆa.t to´an kˆe´t th´ uc, c´ac d¯oˆ thi. c´o k´ıch thu ´o c du ´o i mˆo.t ngu.˜o.ng cho tru.´o.c s˜e ` . . . . . . khˆong d¯u o. c thu go.n thˆem; thay v`ao d¯´o l`a c´ac cˆay bao tr` um cu˙’a ch´ ung d¯u.o..c suy ra. 4.3.5 e. co. so˙’. cu˙’a c´ Hˆ ac chu tr`ınh d ¯ˆo.c lˆ a.p Nhˇa´c la.i rˇa` ng chu sˆo´ cu˙’a d¯`oˆ thi. vˆo hu.´o.ng G c´o n d¯ı˙’nh, m ca.nh, p th`anh phˆ `an liˆen thˆong bˇa ng c(G) = m − n + p−ch´ınh l`a sˆo cu. c d¯a.i c´ac chu tr`ınh d¯oˆ. c lˆa.p. Phˆan du ´o.i d¯ˆay ta xˆay ` ´ . ` . du..ng thuˆa.t to´an t`ım hˆe. co. so˙’. cu˙’a c´ac chu tr`ınh d¯oˆ. c lˆa.p du..a trˆen cˆay bao tr`um cu˙’a d¯`ˆo thi.. Khˆong gia˙’m tˆo ng qu´at, c´o thˆe gia˙’ thiˆe´t d¯`oˆ thi. G liˆen thˆong, v`ı trong tru `o ng ho..p tr´ai la.i, ˙ ’ ˙ ’ . . th`ı ta x´et t` u.ng th`anh phˆ `an liˆen thˆong. Y ´ tu.o˙’.ng o˙’. d¯ˆay l`a 1. Xˆay du..ng cˆay bao tr` um T := (V, ET ). 2. Gia˙’ su˙’. e1 , e2 , . . . , em−n+1 l`a c´ac ca.nh cu˙’a E m`a khˆong thuˆo.c cˆay T. Khi thˆem mˆo.t ca.nh y trong c´ac ca.nh n`ay, chˇa˙’ng ha.n ca.nh ek , v`ao cˆay T ta d¯u.o..c mˆo.t v`a chı˙’ mˆo.t chu bˆa´t k` tr`ınh µk . C´ac chu tr`ınh µ1 , µ2 , . . . , µm−n+1 l`a d¯ˆo.c lˆa.p v`ı mˆo˜i chu tr`ınh ch´u.a mˆo.t ca.nh khˆong thuˆo.c c´ac chu tr`ınh kia; mˇa.t kh´ac ta c´o (m − n + 1) = c(G) chu tr`ınh nhu. vˆa.y, nˆen ta d¯˜a x´ac d¯.inh d¯u.o..c hˆe. co. so˙’. cu˙’a c´ac chu tr`ınh d¯ˆo.c lˆa.p. Nhu. vˆa.y b`ai to´an d¯u.a vˆ `e t`ım c´ac chu tr`ınh µk khi thˆem ca.nh ek v`ao cˆay T. Trong khi kiˆe˙’m tra ca.nh ek = (αk , βk ) trong thuˆa.t to´an 4.3.3, nˆe´u d¯iˆ `eu kiˆe.n 3 d¯u u.c l`a ca˙’ hai d¯ı˙’nh ´ng (t´ αk v`a βk xuˆa´t hiˆe.n trong c` ung cˆay Ti ) th`ı thay cho viˆe.c loa.i bo˙’ ca.nh n`ay ch´ ung ta cˆ `an t`ım c´ac ca.nh trong Ti m`a ta.o th`anh dˆay chuyˆ `en gi˜ . u a hai d¯ı˙’nh αk v`a βk . Dˆay chuyˆ `en n`ay c` ung . . . v´o i ca.nh (αk , βk ) ta.o th`anh mˆo.t chu tr`ınh co ba˙’n. Vˆa´n d¯`ˆe ch´ınh o˙’ d¯aˆy l`a t`ım dˆay chuyˆ `en 112 http://www.ebook.edu.vn
n`ay. C´o nhiˆ `eu phu.o.ng ph´ap hiˆe.u qua˙’ gia˙’i quyˆe´t b`ai to´an, trong sˆo´ d¯´o thuˆa.t to´an cu˙’a Paton [50] l`a hiˆe.u qua˙’ nhˆa´t. Thuˆ a.t to´ e. co. so˙’. cu˙’a c´ an Paton t`ım hˆ ac chu tr`ınh d ¯ˆo.c lˆ a.p Ch´ ung ta c˜ ung s˜e kiˆe˙’m tra mˆo˜i ca.nh c´o ta.o th`anh chu tr`ınh v´o.i nh˜ u.ng ca.nh trong cˆay d¯u.o..c . . . xˆay du. ng trong qu´a tr`ınh thu. c hiˆe.n thuˆa.t to´an, nhu ng thay viˆe.c lˆa´y c´ac ca.nh theo th´ u. tu.. tu` yy ´ (nhu. trong Thuˆa.t to´an 4.3.3), ta cho.n mˆo.t d¯ı˙’nh z v`a kiˆe˙’m tra c´ac ca.nh liˆen thuˆo.c v´o.i n´o. (D u.a d¯u.o..c thˆem v`ao cˆay). D - ı˙’nh z l`a d¯ı˙’nh v` - ˆe˙’ d¯o.n gia˙’n, ta s˜e su˙’. du.ng ma trˆa.n kˆ`e A biˆe˙’u diˆ˜en d¯`oˆ thi.. K´ . . . . . . y hiˆe.u T l`a tˆa.p hiˆe.n h`anh c´ac d¯ı˙’nh trong cˆay d¯u o. c xˆay du. ng o˙’ bu ´o c n`ao d¯o´ v`a W l`a tˆa.p c´ac d¯ı˙’nh chu.a d¯u.o..c kiˆe˙’m tra (t´ u.c l`a nh˜ u.ng d¯ı˙’nh thuˆo.c T hoˇa.c khˆong nhu.ng . . . . c´o ´ıt nhˆa´t mˆo.t ca.nh liˆen thuˆo.c v´o i n´o chu a d¯u o. c kiˆe˙’m tra). Ch´ung ta kho˙’.i d¯`aˆu thuˆa.t to´an bˇ`a ng c´ach d¯aˇ. t T = {v1 } v`a W = V. D - ı˙’nh v1 s˜e l`a gˆo´c cu˙’a cˆay. Sau qu´a tr`ınh kho˙’.i ta.o, thu..c hiˆe.n c´ac bu.´o.c sau: u.ng. 1. Nˆe´u T ∩ W = ∅ thuˆa.t to´an d` 2. Nˆe´u T ∩ W 6= ∅ cho.n d¯ı˙’nh z ∈ T ∩ W. 3. Kiˆe˙’m tra z bˇ`a ng c´ach x´et mˆo˜i ca.nh liˆen thuˆo.c v´o.i n´o. Nˆe´u khˆong c´o ca.nh n`ao, khu˙’. z u. W v`a chuyˆe˙’n sang Bu.´o.c 1. t` `on ta.i ca.nh (z, p) ∈ E kiˆe˙’m tra z c´o thuˆo.c T khˆong. 4. Nˆe´u tˆ 5. Nˆe´u p ∈ T t`ım chu tr`ınh co. ba˙’n gˆ `om ca.nh (z, p) v`a mˆo.t dˆay chuyˆ `en (duy nhˆa´t) t` u. . . . z d¯ˆe´n p trong cˆay d¯ang d¯u o. c xˆay du. ng. Xo´a ca.nh (z, p) kho˙’i d¯`oˆ thi. v`a chuyˆe˙’n sang Bu.´o.c 3. 6. Nˆe´u p ∈ / T thˆem ca.nh (z, p) v`ao cˆay v`a d¯ı˙’nh p v`ao T. Xo´a ca.nh (z, p) kho˙’i d¯`oˆ thi. v`a chuyˆen sang Bu.´o.c 3. ˙ ’ Nhu. d¯a˜ d¯`ˆe cˆa.p, vˆa´n d¯`ˆe co. ba˙’n l`a Bu.´o.c 5. Ch´ u. z d¯ˆe´n p `en t` ung ta pha˙’i t`ım dˆay chuyˆ . . nhu thˆe´ n`ao? Thu˙’ tu.c sau s˜e tra˙’ l`o i cˆau ho˙’i n`ay. Ch´ ung ta su˙’. du.ng mˆo.t ngˆan xˆe´p (stack) T W = T ∩ W d¯ˆe˙’ lu.u tr˜ u. c´ac d¯ı˙’nh trong cˆay . . . . nhu ng chu a d¯u o. c kiˆe˙’m tra. D . . - ı˙’nh d¯u o. c thˆem gˆ`an d¯aˆy nhˆa´t v`ao cˆay s˜e d¯u.o..c ch`en v`ao d¯`aˆu `an mˆo.t d¯ı˙’nh d¯u.o..c kiˆe˙’m tra d¯u.o..c lˆa´y ra kho˙’i t` ngˆan xˆe´p. Mˆo˜i lˆ u. d¯ı˙’nh cu˙’a ngˆan xˆe´p. Ta su˙’. du.ng thˆem hai ma˙’ng tuyˆe´n t´ınh d¯ˆo. d`ai n : ma˙’ng l[j] l`a khoa˙’ng c´ach t` u. gˆo´c v1 d¯ˆe´n d¯ı˙’nh vj trong cˆay bao tr` um; v`a Pred[j] l`a d¯ı˙’nh vi sao cho ca.nh (vi , vj ) l`a mˆo.t ca.nh trong cˆay v´o.i `an gˆo´c ho.n vj . N´oi c´ach kh´ac, Pred[j] l`a d¯ı˙’nh liˆ vi gˆ `en tru.´o.c d¯ı˙’nh vj trong dˆay chuyˆ `en t`u. 113 http://www.ebook.edu.vn
v1 d¯ˆe´n vJ . Nh˜an l[J] = −1 nˆe´u v`a chı˙’ nˆe´u d¯ı˙’nh vj khˆong thuˆo.c tˆa.p T. Kho˙’.i ta.o l[1] = 0 v`a l[j] = −1 v´o.i mo.i j = 2, 3, . . . , n. Trong Bu.´o.c 5, khi x´et d¯ı˙’nh z v`a ca.nh (z, p) d¯u.o..c t`ım thˆa´y v´o.i p ∈ T. D- ˆe˙’ x´ac d¯.inh chu tr`ınh co. ba˙’n sinh bo˙’.i ca.nh (z, p) ch´ `an theo dˆay chuyˆ ung ta lˆ `en t`u. z d¯ˆe´n p trong cˆay bˇ`a ng c´ach t`ım liˆen tiˆe´p c´ac “tiˆ `en bˆo´i” Pred[z], Pred[Prede[z]], . . . cho d¯ˆe´n khi ch´ ung ta bˇa´t gˇa.p Pred[p]-tiˆ`en bˆo´i cu˙’a p. N´oi c´ach kh´ac, nhu chı˙’ ra trong H`ınh ??, chu tr`ınh co. ba˙’n d¯u.o..c ta.o . ra l`a z, Pred[z], Pred[Pred[z]], . . . , Pred[p], p, z. `an ch´ Cˆ uy `en bˆo´i Pred[k] cu˙’a mo.i d¯ı˙’nh k ∈ T l`a mˆo.t d¯ı˙’nh m`a hoˇa.c d¯˜a d¯u.o..c ´ rˇa` ng tiˆ kiˆe˙’m tra hoˇa.c d¯ang d¯u.o..c kiˆe˙’m tra. T´ u.c l`a, nˆe´u k ∈ T ∩ W th`ı Pred[k] ∈ /W nhu.ng Pred[k] ∈ T. Thu˙’ tu.c FundamentalCircuits() minh ho.a c´ac bu.´o.c d¯a˜ tr`ınh b`ay o˙’. trˆen. Th`o.i gian thu..c hiˆe.n cu˙’a thuˆa.t to´an bi. chˇa.n trˆen bo˙’.i nν trong d¯´o gi´a tri. thu..c ν ∈ [2, 3] phu. thuˆo.c v`ao cˆa´u tr´ ung nhu. c´ach d¯a´nh nh˜an c´ac d¯ı˙’nh [50]. uc cu˙’a d¯`ˆo thi. c˜ Mˇa.c d` u d¯ˆe˙’ d¯o.n gia˙’n ch´ ung ta d¯a˜ gia˙’ su˙’. G liˆen thˆong, tuy nhiˆen thuˆa.t to´an c´o thˆe˙’ dˆ˜e d`ang ca˙’i biˆen cho tru.`o.ng ho..p tˆo˙’ng qu´at. D - `ˆau tiˆen, thuˆa.t to´an s˜e ta.o ra tˆa´t ca˙’ c´ac chu . tr`ınh co ba˙’n trong th`anh phˆ `an liˆen thˆong ch´ u.a d¯ı˙’nh xuˆa´t ph´at v1 . Sau d¯´o ta cho.n d¯ı˙’nh y m`a l[y] = −1 v`a bˇa´t d¯`aˆu v´o.i y l`a gˆo´c cu˙’a cˆay bao tr` um th´ u. hai. Thuˆa.t to´an lˇa.p la.i cho d¯ˆe´n khi tˆa´t ca˙’ c´ac d¯ı˙’nh d¯u.o..c g´an nh˜an l kh´ac −1. 4.4 Cˆ ay bao tr` um tˆ e˙’u o´i thiˆ - i.nh ngh˜ıa 4.4.1 Gia˙’ su˙’. G l`a d¯`oˆ thi. c´o tro.ng sˆo´. Cˆay bao tr` D um tˆo´i thiˆe˙’u cu˙’a G l`a mˆo.t . . . um cu˙’a G v´o i tro.ng lu o. ng nho˙’ nhˆa´t. cˆay bao tr` B`ai to´an n`ay rˆa´t hay gˇa.p trong thˆong tin liˆen la.c v`a trong c´ac ng`anh kh´ac. Chˇa˙’ng ha.n ta d¯aˇ. t cˆau ho˙’i nhu. sau: d¯ˆo. d`ai dˆay d¯iˆe.n ngˇa´n nhˆa´t cˆ`an thiˆe´t d¯ˆe˙’ nˆo´i n th`anh phˆo´ d¯a˜ d¯.inh l`a bao nhiˆeu? Khi d¯´o coi c´ac th`anh phˆo´ l`a c´ac d¯ı˙’nh cu˙’a d¯`ˆo thi. v`a w(a, b) l`a khoa˙’ng c´ach t´ınh bˇa` ng km gi˜ u.a c´ac th`anh phˆo´ a v`a b. Ma.ng dˆay d¯iˆe.n cˆ `an pha˙’i liˆen thˆong, v`a v`ı d¯oˆ. d`ai dˆay d¯iˆe.n cˆ`an ngˇa´n nhˆa´t nˆen n´o khˆong c´o chu tr`ınh: vˆa.y ma.ng d¯o´ l`a mˆo.t cˆay. O˙’. d¯ˆay ta cˆ `an ´ ˙ ’ ˙ ’ . . ` ` ` t`ım mˆo.t cˆay “tˆoi thiˆeu” c´o thˆe d¯u o. c v`a l`a mˆo.t d¯oˆ thi. bˆo. phˆa.n cu˙’a d¯ˆo thi. d¯aˆy d¯u˙’ c´o n d¯ı˙’nh. Mˆo.t u ´.ng du.ng gi´an tiˆe´p: b`ai to´an t`ım cˆay bao tr` um tˆo´i thiˆe˙’u l`a bu.´o.c trung gian trong viˆe.c t`ım l`o.i gia˙’i cu˙’a b`ai to´an ngu.`o.i du li.ch-mˆo.t b`ai to´an thu.`o.ng xuˆa´t hiˆe.n trong thu..c tˆe´. 114 http://www.ebook.edu.vn
`an ch´ Cˆ uy´ rˇa` ng, cˆay bao tr` um tˆo´i thiˆe˙’u cu˙’a d¯`oˆ thi. khˆong liˆen quan d¯ˆe´n cˆay sinh bo˙’.i tˆa´t ca˙’ c´ac dˆay chuyˆ `en ngˇa´n nhˆa´t t`u. mˆo.t d¯ı˙’nh cho tru.´o.c. Do d¯´o, d¯`ˆo thi. trong H`ınh 4.10(a), v´o.i c´ac sˆo´ trˆen c´ac ca.nh tu.o.ng u ´.ng c´ac tro.ng lu.o..ng ca.nh, cˆay sinh ra bo˙’.i d¯u.`o.ng d¯i ngˇa´n nhˆa´t t` u. d¯ı˙’nh cho tru.´o.c, chˇa˙’ng ha.n v1 , trong H`ınh 4.10(b); ngu.o..c la.i, cˆay bao tr` um tˆo´i thiˆe˙’u cho trong H`ınh 4.10(c). v1 v1 v1 .• .......... .• .......... •....... .... .. ..... .... ... ..... . ..... .. ..... ..... ..... .. ..... ... ..... .... ..... ..... ..... .... .... ..... ... ..... 5..................... ... .. ... ..... ..... 5 ..... ..... .. ...... ..... ..... ... ... ... ..... ..... ..... ..... ... .. ... ........ .. . ..... . 3 . . . . . . . ..... ..... ..... ..... ..... .... ..... ..... ... ... ... ..... ..... ..... ..... ... ... ... . . .. . ... . . . . ..... ..... .. ...... . ... ..... ..... ... ... . . ... ... . . ..... ..... ..... ... v4 • ......... . . . 3 • 3. . . . . ................................................................................................................................................. .. . . . . ..... • v2 .... v4 • ..... ..... .... • ... ... . ..... • v2 ..... ..... v4 • • ... .......................................................................................................................................... • v2 ..... ..... ..... ..... ..... ..... v5 . . . . .... . ....... ....... ..... .. v5 ..... .. ....... ..... v5 . ..... ..... ..... ..... . .. .... .. ..... .... .... ..... .... ..... ..... ..... ..... ..... ... ..... ..... ..... ..... ..... ..... 5 ... ... ..... . .. . ..... ..... ..... ..... . .... ... . ..... . .. ..... ..... 5 ..... ..... ..... ..... ... ......... ... .. ..... .... 3 .... ..... ..... . ..... ..... .... ..... ..... ... ..... ..... . .. ..... .. ..... ..... . .... • ........ • ..... • ..... v3 v3 v3 (a) (b) (c) H`ınh 4.10: (a) D- `ˆo thi. G. (b) Cˆay sinh bo˙’.i d¯u.`o.ng d¯i ngˇa´n nhˆa´t xuˆa´t ph´at t` u. v1 . (c) Cˆay bao um nho˙’ nhˆa´t. tr` T`ım cˆay bao tr` um tˆo´i thiˆe˙’u l`a mˆo.t trong nh˜ u.ng b`ai to´an cu˙’a l´ y thuyˆe´t d¯`oˆ thi. c´o thˆe˙’ gia˙’i quyˆe´t triˆe.t d¯ˆe˙’. Do d¯o´, d¯aˇ. t Ti v`a Tj l`a hai cˆay con d¯u o. c ta.o ra trong qu´a tr`ınh xˆay du..ng . . cˆay bao tr` um tˆo´i thiˆe˙’u. Nˆe´u Ti d¯u.o..c su˙’. du.ng d¯ˆe˙’ biˆe˙’u diˆ˜en tˆa.p c´ac d¯ı˙’nh cu˙’a cˆay con th`ı ∆ij c´o thˆe˙’ d¯.inh ngh˜ıa l`a khoa˙’ng c´ach ngˇa´n nhˆa´t t` u. mˆo.t d¯ı˙’nh trong Ti d¯ˆe´n mˆo.t d¯ı˙’nh trong Tj ; t´ . u c l`a ∆ij := min [ min {w(vi , vj )}], i 6= j. (4.1) vi ∈Ti vj ∈Tj u.ng minh rˇa` ng lˇa.p la.i ph´ep to´an sau s˜e cho ta cˆay bao tr` Khi d¯o´, dˆ˜e d`ang ch´ um tˆo´i thiˆe˙’u: Ph´ep to´an I. V´o.i cˆay con Ts n`ao d¯o´, t`ım cˆay con Tj ∗ sao cho ∆sj ∗ = minTj [∆sj ], v`a d¯aˇ. t (vs , vj ∗ ) l`a ca.nh tu.o.ng u ´.ng gi´a tri. ∆sj ∗ trong (4.1) d¯a.t d¯u.o..c. Khi d¯´o (vs , vj ∗ ) thuˆo.c cˆay bao tr` um tˆo´i thiˆe˙’u v`a c´o thˆe˙’ d¯u.o..c thˆem v`ao v´o.i c´ac ca.nh kh´ac trong qu´a tr`ınh lˇa.p d¯ˆe˙’ ta.o ra cˆay bao tr` um tˆo´i thiˆe˙’u. Thˆa.t vˆa.y, gia˙’ su˙’. c´ac ca.nh trong c´ac cˆay con o˙’. bu.´o.c k n`ao d¯o´ thuˆo.c cˆay bao tr` um tˆo´i ˙’ . . . thiˆeu Tm o˙’ bu ´o c cuˆo´i c` . . . . ung. Gia˙’ su˙’ ca.nh (vs , vj ∗ ) d¯u o. c cho.n nhu trˆen khˆong thuˆo.c cˆay bao 115 http://www.ebook.edu.vn
tr`um tˆo´i thiˆe˙’u Tm . Theo d¯i.nh ngh˜ıa, cˆay con Ts o˙’. bu.´o.c cuˆo´i c` ung d¯u.o..c nˆo´i v´o.i cˆay con kh´ac n`ao d¯o´ bˇa` ng ca.nh (vi , vj ) trong d¯´o vi ∈ Ts v`a vj ∈ / Ts v`a ngo`ai ra Ts pha˙’i ch´ u.a trong cˆay bao tr` um tˆo´i thiˆe˙’u Tm . Xo´a ca.nh (vi , vj ) kho˙’i cˆay Tm s˜e cho ta hai th`anh phˆ `an liˆen thˆong v`a thay n´o bo i ca.nh (vs , vj ) s˜e ta.o mˆo.t cˆay m´o i c´o tro.ng lu o. ng nho ho n tro.ng lu.o..ng cˆay ˙ ’. ∗ . . . ˙ ’ . Tm , mˆau thuˆa˜n. Vˆa.y, v´o.i nh˜ u.ng gia˙’ thiˆe´t trˆen, ta c´o thˆe˙’ thˆem ca.nh (vs , vj ∗ ) d¯ˆe˙’ ta.o th`anh cˆay (ch´ u.a trong cˆay bao tr` um tˆo´i thiˆe˙’u) o˙’. bu.´o.c k v`a tiˆe´p tu.c v´o.i bu.´o.c (k + 1). C˜ ung cˆ`an ch´uy ´ rˇ`a ng, phu o ng ph´ap trˆen khˆong phu. thuˆo.c v`ao cˆay Ts d¯u.o..c cho.n. Ho.n n˜ . . u.a, do bu.´o.c kho˙’.i ta.o (t´u.c l`a tru.´o.c khi bˆa´t c´ u. ca.nh n`ao d¯u.o..c cho.n) gia˙’ thiˆe´t l`a khˆong tˆ `on ta.i (v`a do d¯´o d¯u ´ng) nˆen lˇa.p la.i thuˆa.t to´an trˆen cuˆoi c`´ ung s˜e ta.o ra cˆay bao tr` ´ um tˆoi thiˆeu.˙ ’ Hˆ `au hˆe´t c´ac phu.o.ng ph´ap t`ım cˆay bao tr` um tˆo´i thiˆe˙’u d¯`ˆeu du..a trˆen nh˜ u.ng tru.`o.ng ho..p - `ˆau tiˆen, trong sˆo´ d¯o´ l`a phu.o.ng ph´ap cu˙’a Kruskal [39] nhu. sau. d¯aˇ. c biˆe.t cu˙’a thu˙’ tu.c trˆen. D 4.4.1 Thuˆ a.t to´ an Kruskal ´ tu.o˙’.ng cu˙’a thuˆa.t to´an Kruskal t`ım cˆay bao tr` Y um trong d¯`oˆ thi. liˆen thˆong c´o tro.ng sˆo´ G . . . `om tˆa´t ca˙’ c´ac d¯ı˙’nh cu˙’a G v`a khˆong c´o ca.nh. Ta.i mˆo˜i bu.´o.c nhu sau: Kho˙’ i ta.o v´o i d¯`oˆ thi. T gˆ lˇa.p ch´ung ta thˆem mˆo.t ca.nh c´o tro.ng lu.o..ng nho˙’ nhˆa´t lˆen cˆay T m`a khˆong ta.o th`anh chu tr`ınh trong T. Thuˆa.t to´an d` u.ng khi T c´o (n − 1) ca.nh. 1. [Kho˙’.i ta.o] Gia˙’ su˙’. T l`a d¯`oˆ thi. gˆ `om n d¯ı˙’nh v`a khˆong c´o ca.nh. u. tu.. c´ac ca.nh cu˙’a d¯`oˆ thi. G theo th´ 2. [Sˇa´p xˆe´p] Sˇa´p xˆe´p th´ u. tu.. tro.ng lu.o..ng tˇang dˆ `an. 3. [Thˆem ca.nh] Thˆem ca.nh (bˇa´t d¯`aˆu t` u. ca.nh d¯`ˆau tiˆen) trong danh s´ach c´ac ca.nh d¯u.o..c sˇa´p xˆe´p v`ao cˆay T sao cho khˆong ta.o th`anh chu tr`ınh trong T khi thˆem. (Ca.nh d¯u.o..c thˆem v`ao go.i l`a chˆa´p nhˆa.n d¯u.o..c). 4. [Kˆe´t th´ u.ng; T l`a cˆay bao tr` uc] Nˆe´u T c´o (n − 1) ca.nh th`ı thuˆa.t to´an d` um tˆo´i thiˆe˙’u. Thuˆa.t to´an n`ay thˆem v`ao cˆay T nh˜ u.ng ca.nh c´o tro.ng lu.o..ng nho˙’ nhˆa´t chˆa´p nhˆa.n d¯u.o..c ho.n l`a thˆem ca.nh gi˜ u.a mˆo.t cˆay con cu˙’a T, chˇa˙’ng ha.n Ts , v`a mˆo.t cˆay con n`ao kh´ac (nhu. chı˙’ ra trong Ph´ep to´an I). Hiˆe˙’n nhiˆen ca.nh d¯u.o..c cho.n c´o tro.ng lu.o..ng nho˙’ nhˆa´t gi˜ u.a mˆo.t cˆay con n`ao d¯´o v`a bˆa´t k` y cˆay con kh´ac, nˆen nguyˆen tˇa´c cho.n cu˙’a thuˆa.t to´an Kruskal l`a mˆo.t tru `o ng ho. p d¯aˇ. c biˆe.t cu˙’a Ph´ep to´an I. Tuy nhiˆen c´o thˆe˙’ xa˙’y ra tru.`o.ng ho..p ca.nh e d¯u.o..c . . . kiˆe˙’m tra d¯ˆe˙’ thˆem v`ao liˆen thuˆo.c gi˜ u.a hai d¯ı˙’nh cu˙’a c` ung mˆo.t cˆay con v`a do d¯o´ n´o s˜e ta.o ra mˆo.t chu tr`ınh nˆe´u thˆem v`ao; t´ u.c l`a ca.nh e l`a khˆong chˆa´p nhˆa.n d¯u.o..c. V`ı vˆa.y, trong Bu.´o.c 3, c´ac ca.nh cˆ `an d¯u.o..c kiˆe˙’m tra t´ınh chˆa´p nhˆa.n cu˙’a n´o tru.´o.c khi thˆem v`ao T. Tiˆe´n tr`ınh kiˆe˙’m tra n`ay c´o thˆe˙’ thu..c hiˆe.n hiˆe.u qua˙’ bˇ`a ng c´ach su˙’. du.ng thuˆa.t to´an xˆay du..ng cˆay bao tr` um . . du. a trˆen hai ma˙’ng tuyˆe´n t´ınh nhu d¯a˜ tr`ınh b`ay trong Phˆ `an 4.3.3. 116 http://www.ebook.edu.vn
V´ı du. 4.4.2 X´et d¯`ˆo thi. trong H`ınh 4.11(a). Sˇa´p xˆe´p c´ac ca.nh theo tro.ng lu.o..ng tˇang dˆ `an . . . (su˙’ du.ng hai ma˙’ng tuyˆe´n t´ınh α v`a β) ta d¯u o. c k 1 2 3 4 5 6 7 8 9 α c a e a c a b c d β d c f e f b d e f Tro.ng lu.o..ng 1 2 2 3 3 4 5 6 6 C´ac ca.nh (khˆong ta.o th`anh chu tr`ınh) d¯u.o..c thˆem v`ao cˆay T theo th´ u. tu.. l`a (c, d), (a, c), (e, f ), (a, e), (a, b). um nho˙’ nhˆa´t c´o tro.ng lu.o..ng 12 (H`ınh 4.11(b)). T l`a cˆay bao tr` a 4 b a 4 b •...................................................................................................................................... ....... ..... .. .. ... • •.................................................................................................................................... ....... ..... .. • .. ...... ..... . ... .. ...... ..... . .... .. ..... ..... . ... . .. . ... .. . .... . 2 ... ... 5 .... ..... ..... 2 ... 3 . . ..... . . ...... . ... . .. 1 ... ... 3 . . ... . ....... ... ... ... 1 .. . . .... . .. . ..... ... ... .. • .. .. ..... ............ . .. .. . .. . ... ... ... .......... .............. .. .... ..... . . ............ .... ..... ... ... ...... .... . ... .. .. ..... . .. ....... .. . .. ..... . . . . . ... ... . . . ... • ... .. . . .... . .. . ... . . • • ................................................................................................................................. . .... ..... . .... . ....... ....... . ... ....... . c ....... ... ....... ....... ..... . .... . .. ... d . ..... . . . ... . . .... . c d .. . ..... ............. ..... ..... .............. . .. 6 ....... ....... ....... ....... ... 3 .. .. ..... ..... ..... 6 ..... ..... ..... ..... ....... ....... ....... ..... ...... ............ .. .... . . •...........................................................................................................................................................................................• • .. ............................................................................................................................................................................... • e 2 f e 2 f (a) (b) H`ınh 4.11: Bˆ o˙’ d`e 4.4.3 Nˆe´u Kn = (V, E) l`a d¯`ˆo thi. d¯`ˆay d¯u˙’ , v`a nˆe´u tˆa´t ca˙’ c c´ac tro.ng lu.o..ng cu˙’ a c´ac ¯ˆ `on ta.i duy nhˆa´t mˆo.t cˆay bao tr` ca.nh kh´ac nhau th`ı tˆ um tˆo´i thiˆe˙’u T = (V, ET ). Ch´ u.ng minh. K´ y hiˆe.u Ek := {e1 , e2 , . . . , ek } l`a tˆa.p c´ac ca.nh d¯u.o..c thˆem v`ao cˆay T trong Thuˆa.t to´an 4.4.1 o˙’. bu.´o.c lˇa.p th´ u. k, 1 ≤ k ≤ n − 1. Hiˆe˙’n nhiˆen theo c´ach xˆay du..ng, T l`a d¯`oˆ thi. c´o (n − 1) ca.nh v`a khˆong c´o chu tr`ınh nˆen T l`a cˆay bao tr` um cu˙’a Kn . Gia˙’ su˙’. T 0 = (V, ET 0 ) l`a cˆay bao tr` um tˆo´i thiˆe˙’u, ta ch´u.ng minh ET 0 = En−1 . Thˆa.t vˆa.y, gia˙’ su˙’. ngu.o..c la.i tˆ`on ta.i chı˙’ sˆo´ k nho˙’ nhˆa´t sao cho ca.nh ek khˆong thuˆo.c ET 0 . Khi d¯´o theo t´ınh chˆa´t cu˙’a cˆay, tˆ `on ta.i tˆ `on ta.i mˆo.t v`a chı˙’ mˆo.t chu tr`ınh µ trong T 0 ∪ {ek }. Trˆen chu tr`ınh n`ay c´o mˆo.t ca.nh e0 m`a e0 ∈ / En−1 , v`ı nˆe´u ngu.o..c la.i tˆ `on ta.i mˆo.t chu tr`ınh, l`a µ, trong cˆay 117 http://www.ebook.edu.vn
T −mˆau thuˆa˜n. Nˆe´u d¯aˇ. t ET 00 := (ET 0 ∪ {ek }) \ {e0 }) th`ı d¯`ˆo thi. T 00 := (V, ET 00 ) khˆong c´o chu tr`ınh v`a c´o (n − 1) ca.nh nˆen n´o l`a mˆo.t cˆay. u.a chu tr`ınh. Suy ra Mˇa.t kh´ac Ek−1 ∪ {e0 } ⊂ ET 00 nˆen Ek−1 ∪ {e0 } khˆong ch´ w(e0 ) > w(ek ). Nhu.ng cˆay T 00 nhˆa.n d¯u.o..c t`u. cˆay T 0 bˇ`a ng c´ach thay ca.nh e0 th`anh ca.nh ek nˆen W (T 00 ) < W (T 0 ). Mˆau thuˆa˜n v`ı T 0 l`a cˆay bao tr`um tˆo´i thiˆe˙’u. / - i.nh l´ D y 4.4.4 Thuˆa.t to´an Kruskal l`a d¯u u.c l`a, kˆe´t th´ ´ng; t´ uc thuˆa.t to´an T l`a cˆay bao tr` um tˆo´i thiˆe˙’u. Ch´u.ng minh. Thˆa.t vˆa.y tru.´o.c hˆe´t ta thu xˆe´p d¯ˆe˙’ mo.i ca.nh d¯`ˆeu c´o d¯ˆo. d`ai kh´ac nhau; chˇa˙’ng ha.n nˆe´u w(e1 ) = w(e2 ) = · · · = w(es ) th`ı thu..c hiˆe.n ph´ep biˆe´n d¯oˆ˙’i: w(e1 ) = w(e1 ) + ², w(e2 ) = w(e2 ) + ²2 , .. . w(es ) = w(es ) + ²s , trong d¯o´ ² l`a sˆo´ du.o.ng d¯u˙’ b´e sao cho khˆong l`am d¯a˙’o lˆo.n th´ u. tu.. vˆ u.a tro.ng lu.o..ng `e quan hˆe. gi˜ cu˙’a c´ac ca.nh. P C˜ ung c´o thˆe˙’ thˆem c´ac ca.nh f v´o.i tro.ng lu.o..ng d¯u˙’ l´o.n w(f ) > e∈E w(e) ung thˆe´, ta c˜ v`a kh´ac nhau sao cho d¯`ˆo thi. nhˆa.n d¯u.o..c Kn = (V, E 0 ) l`a d¯`ˆay d¯u˙’. Theo Bˆo˙’ d¯`ˆe 4.4.3 tˆ `on ta.i duy nhˆa´t mˆo.t cˆay bao tr` um tˆo´i thiˆe˙’u T trong d¯`oˆ thi. Kn . Mˇa.t P kh´ac, mo.i cˆay bao tr` um cu˙’a d¯`oˆ thi. G c´o tro.ng lu o. ng khˆong vu.o..t qu´a e∈E w(e) v`a mo.i cˆay . . bao tr`um cu˙’a G c˜ ung l`a cˆay bao tr` um cu˙’a Kn . Suy ra T l`a cˆay bao tr` um tˆo´i thiˆe˙’u cu˙’a G. / ung phu.o.ng ph´ap d¯oˆ´i ngˆa˜u: loa.i dˆ Nhˆa.n x´et rˇ`a ng, c´o thˆe˙’ d` `an c´ac ca.nh c´o tro.ng lu.o..ng l´o.n nhˆa´t cu˙’a d¯`oˆ thi. m`a khˆong l`am mˆa´t t´ınh liˆen thˆong cu˙’a n´o cho d¯ˆe´n khi khˆong thˆe˙’ loa.i ca.nh d¯u.o..c n˜ u.a. - ˆo. ph´ D u.c ta.p t´ınh to´an cu˙’a thuˆa.t to´an Kruskal phu. thuˆo.c v`ao Bu.´o.c 2: d¯`oˆ thi. c´o m ca.nh cˆ `an m log2 m ph´ep to´an d¯ˆe˙’ thu..c hiˆe.n sˇa´p xˆe´p ma˙’ng theo tro.ng lu.o..ng tˇang dˆ `an. Tuy ` ˙ ’ nhiˆen, n´oi chung ta khˆong cˆan duyˆe.t to`an bˆo. mang v`ı cˆay bao tr` ´ ˙ ’ ` um tˆoi thiˆeu gˆom (n − 1) ca.nh chˆa´p nhˆa.n d¯u.o..c nˆen chı˙’ cˆ `an kiˆe˙’m tra r < m phˆ `an tu˙’. d¯`aˆu tiˆen cu˙’a ma˙’ng. Do d¯o´ ta c´o thˆe˙’ ca˙’i tiˆe´n thuˆa.t to´an n`ay d¯ˆe˙’ tˇang tˆo´c d¯oˆ. thu..c hiˆe.n (xem [14], [36]). Mˇa.c d` u c´o nh˜u.ng ca˙’i tiˆe´n, nhu.ng thuˆa.t to´an Kruskal chı˙’ th´ıch ho..p v´o.i nh˜ u.ng d¯`ˆo thi. tu.o.ng d¯ˆo´i thu.a. V´o.i nh˜ u.ng d¯`ˆo thi. kh´ac, chˇa˙’ng ha.n d¯`oˆ thi. d¯`ˆay d¯u˙’ c´o sˆo´ ca.nh m = n(n−1)/2, 118 http://www.ebook.edu.vn