Giáo trình đồ thị và các thuật toán

Tham khảo sách giáo trình đồ thị và các thuật toán, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình đồ thị và các thuật toán Giáo trìnhĐồ thị và các thuật toánMuc luc ..L`.i n´i d` u o o ¯ˆ a 71 Dai cu.o.ng vˆ d` thi -. ` ¯ˆ . eo 9 -. 1.1 Dinh ngh˜ v` c´c kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . ıa a a ae 9 . D` thi c´ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o 1.1.1 o 9 -ˆ . aa D` thi v` ´nh xa d a tri . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 o .¯ 10 . D` thi vˆ hu.´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -ˆ . o o 1.1.3 o 10 1.1.4 C´c d inh ngh˜ ch´ . . . . . . . . . . . . . . . . . . . . . . . . . . . a ¯. ıa ınh 11 Ma trˆn biˆ’u diˆn d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ˜ ¯ˆ . 1.2 a e eo 13 . o ¯˙ ’ 1.2.1 Ma trˆn liˆn thuˆc d ınh-cung . . . . . . . . . . . . . . . . . . . . . . ae 13 . . o ¯˙ ’ 1.2.2 Ma trˆn liˆn thuˆc d ınh-canh . . . . . . . . . . . . . . . . . . . . . . ae 15 . . . a` o ¯˙ ¯˙ ’ ’ 1.2.3 Ma trˆn kˆ hay ma trˆn liˆn thuˆc d ınh-d ınh . . . . . . . . . . . . . .e ae 17 . . C´c biˆ’u diˆn cua d` thi . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ˜ ˙ ¯o . ’ˆ 1.2.4 a e e 18 1.3 T´ liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ınh e o 23 ` 1.3.1 Dˆy chuyˆn v` chu tr` . . . . . . . . . . . . . . . . . . . . . . . . . a ea ınh 23 Du.`.ng d i v` mach . . . . . . . . . . . . . . . . . . . . . . . . . . . . -o 1.3.2 ¯a. 24 1.3.3 T´ liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ınh e o 24 http://www.ebook.edu.vn 1 ` 1.3.4 Cˆu, k −liˆn thˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . . a e o 28 -ˆ . e D` thi liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5 o o 31 . 1.4 Pham vi v` liˆn thˆng manh . . . . . . . . . . . . . . . . . . . . . . . . . . . ae o 33 . . 1.4.1 Ma trˆn pham vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 33 . . ` 1.4.2 T` c´c th`nh phˆn liˆn thˆng manh . . . . . . . . . . . . . . . . . . ım a a ae o 36 . Co. so. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ’ 1.4.3 39 -a ˙ ’ Dˇng cˆ u cua c´c d` thi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˙ a ¯ˆ . ’ 1.5 a o 41 ˙ ’ ´ 1.5.1 1−d ˇng cˆ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¯a a 42 ˙ ’ ´ 1.5.2 2−d ˇng cˆ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¯a a ...