Giáo trình đại cương đồ thị

Trong thực tế để miêu tả một số tình huống người ta thường biểu thị qua hình ảnh, gồm các điểm (các đỉnh) biểu diễn các thực thể- và vẽ các đạon thẳng nối cặp các đỉnh biểu diễn mối quan hệ giữa chúng. Những hình như thế tường gọi là đồ thị...
Nội dung trích xuất từ tài liệu:
Giáo trình đại cương đồ thị   Giáo trìnhĐẠI CƯƠNG ĐỒ THỊMuc 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 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. . . . . . . . ...