Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. để biết thêm nội dung chi tiết. | Đồ 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 vuc ´ı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.ong). 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 hop 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.oc 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.oc 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 dung d¯u.oc 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.oc 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.oc 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 .
