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 4 ˆ CAY Mo˙’. d`au ¯ˆ Cˆay l`a trong nh˜ kh´ai quan nhˆa´t cu˙’a l´ y thuyˆe´t d¯`oˆ thi., v`a thu.` xuˆa´t trong nh˜ l˜anh vuc ´ıt c´o liˆen quan d¯ˆe´n d¯`ˆo thi Trong n`ay, tru.´ hˆe´t s˜e nghiˆen c´ cˆay Huffman v`a nh˜ u ´.ng cu˙’a n´o trong n´en d˜ u. . Kˆe´ tiˆe´p ch´ ung ta x´et tr`ınh b`ay c´ac to´an t`ım cˆay bao tr` um, cˆay bao tr` . . ˙’ ´ ˙’ ` . . ´ . um c´o lu o. ng nho nhˆa t khi c´ac cua d¯ˆo thi. d¯u o. c gˇan v´o i c´ac chi ph´ı ( ). Cˆay bao tr` um nho˙’ nhˆa´t cu˙’a d¯`ˆo thi. c´o nhiˆ `eu u´.ng trong nh˜ tru.` hop c´ac d¯u.` dˆa˜n (ˆo´ng dˆa˜n ga, dˆay dˆa˜n trong d¯, ) d¯ su˙’. d¯ˆe˙’ nˆo´i n d¯iˆe˙’m v´ nhau theo c´ach tˆo´t nhˆa´t: tˆo˙’ng khoa˙’ng c´ach cu˙’a c´ac d¯u.` dˆa˜n l`a nho˙’ nhˆa´t. Nˆe´u n d¯iˆe˙’m d¯ nˆo´i v´ nhau trˆen phˇa˙’ng, ta c´o thˆe˙’ biˆe˙’u diˆ˜en bo˙’.i d¯`oˆ thi. d¯`ˆay d¯u˙’ trong d¯o´ c´ac chi ph´ı l`a khoa˙’ng c´ach gi˜ hai d¯iˆe˙’m u ´.ng. Khi d¯´o cˆay bao tr` um v´ . . . lu o. ng nho˙’ nhˆa´t s˜e cho 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˙’ ch´ı xˆay dung d¯ v´ ch´ı ph´ı re˙’ v`a x´ac d¯ 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¯ d¯`ˆe o˙’. phˆ `an cuˆo´i . - .inh ngh˜ıa C´ac d¯ ngh˜ıa sau cu˙’a cˆay (vˆo hu.´) l`a d¯: D - `ˆo thi. liˆen thˆong c´o n d¯ı˙’nh v`a (n − 1) . 1. D - `ˆo thi. liˆen thˆong khˆong c´o chu tr`ınh. 2. D - `ˆo thi. m`a d¯ı˙’nh d¯ nˆo´i v´ nhau bo˙’.i v`a chı˙’ dˆay chuyˆ 3. D `en so. cˆa´p. - `ˆo thi. liˆen thˆong v`a khi .
