Xem mẫu

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN
KHOA CÔNG NGHỆ THÔNG TIN

ĐỀ CƯƠNG
TOÁN RỜI RẠC
Trình độ đào tạo : Đại học
Hệ đào tạo

: Chính quy/Liên thông

Mở đầu
Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại.
Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế
kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sỹ Lenhard Eurler. Chính ông là người đã
sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg.
Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng
hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện.
Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức
phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định hai
máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình
đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các
bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông.
Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa biểu, và
phân bố tần số cho các trạm phát thanh và truyền hình.
Bộ môn Công nghệ Phần mềm
Khoa Công nghệ Thông tin
Trường Đại học Sư phạm Kỹ thuật Hưng Yên

Trang 2

Mục lục
Bài 1
Các khái niệm cơ bản của Lý thuyết đồ thị ................................................................. 7
1.1. Định nghĩa cơ bản về đồ thị............................................................................................. 7
1.2. Đường đi - chu trình - Đồ thị liên thông .......................................................................... 9
1.3. Phân loại đồ thị .............................................................................................................. 13
1.3.1. Đồ thị vô hướng liên thông ..................................................................................... 13
1.3.2. Đồ thị có hướng liên thông ..................................................................................... 14
1.4. Một số loại đồ thị đặc biệt ............................................................................................. 15
Bài 2
Biểu diễn đồ thị trên máy tính ................................................................................... 20
2.1. Một số phương pháp biểu diễn đồ thị trên máy tính...................................................... 20
2.2.1. Ma trận kề - Ma trận trọng số ................................................................................. 20
2.2.2. Danh sách cạnh (cung) ........................................................................................... 22
2.2.3. Danh sách kề........................................................................................................... 22
Bài 3
Đồ thị Euler ................................................................................................................ 24
3.1. Định nghĩa ..................................................................................................................... 24
3.2. Các ví dụ ........................................................................................................................ 24
3.3. Định lý Euler và thuật toán Flor .................................................................................... 25
Bài 4
Đồ thị Hamilton ......................................................................................................... 28
4.1 Định nghĩa ...................................................................................................................... 29
4.2. Định lý và thuật toán liệt kê tất cả các chu trình Hamilton ........................................... 29
Bài 5
Thảo luận cài đặt đồ thị, các thuật toán liệt kê chu trình Euler và Hamilton. ............ 33
5.1. Cài đặt biểu diễn đồ thị trên máy tính ........................................................................... 33
5.2. Cài đặt thuật toán liệt kê chu trình Euler ....................................................................... 33
5.3. Cài đặt thuật toán liệt kê chu trình Hamilton................................................................. 35
5.4. Thảo luận các bài tập trong giáo trình bài tập ............................................................... 35
Bài 6
Thuật toán tìm kiếm trên đồ thị và ứng dụng............................................................. 36
6.1. Duyệt đồ thị theo chiều rộng (BFS)............................................................................... 36
6.2. Duyệt đồ thị theo chiều sâu (DFS) ................................................................................ 39
6.3. Thảo luận ....................................................................................................................... 42
Bài 7
Cây và cây khung ....................................................................................................... 45
7.1. Cây và cây khung .......................................................................................................... 45
7.1.1. Cây .......................................................................................................................... 45
7.1.2. Cây khung của đồ thị .............................................................................................. 46
7.2. Bài toán cây khung nhỏ nhất ......................................................................................... 48
7.3 Xây dựng tập các chu trình cơ bản của đồ thị ................................................................ 49
7.4. Thuật toán Prim ............................................................................................................. 51
7.5 Thuật toán Kruskal ......................................................................................................... 54
Bài 8
Thảo luận về cài đặt thuật toán tìm cây khung nhỏ nhất trên đồ thị .......................... 57
8.1. Cài đặt xây dựng tập các chu trình cơ bản của đồ thị .................................................... 57
8.2. Cài đặt thuật toán Prim .................................................................................................. 59
8.3. Cài đặt thuật toán Kruskal ............................................................................................. 60
8.4. Một số thuật toán xây dựng cây khung(*) ..................................................................... 61
Bài 9
Bài toán tìm đường đi ngắn nhất ................................................................................ 63
9.1. Các khái niệm mở đầu ................................................................................................... 63
9.2. Đường đi ngắn nhất xuất phát từ một đỉnh. Thuật toán ford-Bellman .......................... 64
9.3. Trường hợp ma trận trọng số không âm. Thuật toán Dijkstra ....................................... 66
Bài 10 Bài toán tìm đường đi ngắn nhất (tiếp) ...................................................................... 69
10.1 Đường đi trong đồ thị không có chu trình .................................................................... 69

Trang 3

10.2 Đường đi ngắn nhất giữa tất cả các cặp đỉnh ............................................................... 73
10.3 Cài đặt thuật toán Dijkstra ........................................................................................... 75
Bài 11 Bài toán luồng cực đại trong mạng ........................................................................... 76
11.1. Mạng - Luồng trong mạng .......................................................................................... 76
11.2. Bài toán luồng cực đại ................................................................................................ 77
11.3. Lát cắt. đường tăng luồng. Định lý ford_fulkerson .................................................... 77
11.4. Thuật toán tìm luồng cực đại ...................................................................................... 80
Bài 12
Lý thuyết đồ thị và ứng dụng ................................................................................. 90
12.1. Các bài toán liên quan tới đồ thị ................................................................................. 90
12.1.1 Các bài toán liên quan tới bậc của đồ thị .............................................................. 90
12.1.2 Các bài toán liên quan đến tính liên thông của đồ thị ........................................... 92
12.1.3 Các bài toán liên quan tới chu trình ...................................................................... 93
12.1.4 Các bài toán có liên quan đến đường đi và chu trình Hamilton ........................... 94
12.1.5 Các bài toán liên quan đến đồ thị tô màu .............................................................. 99
12.1.6 Bài toán về cây .................................................................................................... 108
12.1.7 Bài toán về ghép cặp ........................................................................................... 109
12.1.8 Đồ thị Euler ......................................................................................................... 109
12.1.9 Các bài toán có tính tổng hợp ............................................................................. 110
12.2 Sự liên hệ giữa các tập đặc biệt trên đồ thị với các bài toán trên bàn cờ ................... 112
12.3 Duyệt rộng trên mảng hai chiều ................................................................................. 116
Bài 13
Một số ứng dụng trong đồ thị .............................................................................. 118
13.1 Bài toán đám cưới vùng quê ..................................................................................... 118
13.2 Bài toán về hệ thống đại diện chung .......................................................................... 119
13.3 Bài toán tối ưu rời rạc ................................................................................................ 119
Bài toán phân nhóm sinh hoạt ........................................................................................ 120
Bài toán lập lịch cho hội nghị ........................................................................................ 120
13.4 Một số bài toán liên quan đến việc tổ chức mạng vận chuyển bưu chính. ................ 121
Mô hình định tuyến mạng đường thư cấp 1 ................................................................... 121
Bài toán lập kế hoạch vận chuyển bưu gửi .................................................................... 122
Mô hình mạng đường thư trong thành phố .................................................................... 124
TÀI LIỆU THAM KHẢO...................................................................................................... 127

Trang 4

Danh mục các hình vẽ
Hình 1.1 Sơ đồ mạng máy tính. .................................................................................................. 7
Hình 1.2 Sơ đồ mạng máy tính với đa kênh thoại. ..................................................................... 8
Hình 1.3 Sơ đồ mạng máy tính với kênh thoại thông báo. ......................................................... 8
Hình 1.4 Mạng máy tính với kênh thoại một chiều. ................................................................... 9
Hình 1.5 Đường đi trên đồ thị .................................................................................................. 10
Hình 1.6 Đồ thị G và H. .......................................................................................................... 11
Hình 1.7 Đồ thị liên thông mạnh G và đồ thị liên thông yếu H. .............................................. 12
Hình 1.8 Đồ thị vô hướng ......................................................................................................... 13
Hình 1.9 Đồ thị có hướng ......................................................................................................... 15
Hình 1.10 Đồ thị đầy đủ ........................................................................................................... 16
Hình 1.11 Đồ thị vòng C3, C4, C5, C6 ....................................................................................... 16
Hình 1.12 Đồ thị bánh xe W3, W4, W5, W6 .............................................................................. 16
Hình 1.13 Đồ thị lập phương Q1, Q2, Q3 .................................................................................. 17
Hình 1.14 Đồ thị hai phía ......................................................................................................... 17
Hình 1.15 Đồ thị K4 là đồ thị phẳng ......................................................................................... 18
Hình 1.16 Các miền tương ứng với biểu diễn phẳng của đồ thị ............................................... 19
Hình 2.1 Đồ thị vô hướng G và Đồ thị có hướng G1 ................................................................ 21
Hình 3.1 Mô hình 7 cây cầu ở Konigsberg............................................................................... 24
Hình 3.2 Đồ thị G1, G2, G3 ....................................................................................................... 25
Hình 3.3 Đồ thị H1, H2, H3 ....................................................................................................... 25
Hình 3.4 Minh hoạ cho chứng minh Định lý 3.1 ...................................................................... 26
Hình 4.1 Du lịch 20 thành phố ................................................................................................. 28
Hình 4.2 Đồ thị Hamilton G3, nửa Hamilton G2, và G1 ........................................................... 29
Hình 4.3 Đồ thị đấu loại D5, đấu loại liên thông mạnh D6 ....................................................... 30
Hình 4.4 Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui ................. 32
Hình 5.1 Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui ................. 35
Hình 6.1 Đồ thị vô hướng ......................................................................................................... 37
Hình 6.2 Đồ thị vô hướng ......................................................................................................... 43
Hình 7.1 Cây và rừng ............................................................................................................... 45
Hình 7.2 Đồ thị và các cây khung của nó. ................................................................................ 47
Hình 7.3 Đồ thị và cây khung nhỏ nhất. ................................................................................... 53
Hình 8.1 Hệ chu trình độc lập cho đồ thị vô hướng G ............................................................. 57
Hình 8.2 Hệ chu trình độc lập cho đồ thị có hướng G1 ............................................................ 57
Hình 8.3 Minh họa từng bước thuật toán Prim tìm cây khung nhỏ nhất .................................. 59
Hình 8.4 Minh họa từng bước thuật toán Kruskal tìm cây khung nhỏ nhất ............................. 61
Hình 11.1 Đồ thị không có chu trình. ....................................................................................... 69
Hình 11.2 Đồ thị minh hoạ PERT. ........................................................................................... 73
Hình 12.1 Mạng G và luồng f. Đồ thị có trọng số Gf tương ứng. ............................................ 79
Hình 12.2 Mạng G và minh họa từng bước thuật toán ford-Fullkerson ................................... 86
Hình 12.3 Mạng G với luồng cực đại và lát cắt hẹp nhất ......................................................... 87
Hình 12.4 Ví dụ tồi tệ đối với thuật toán ford_Fulkerson. ....................................................... 88
Hình 12.5 Tăng luồng dọc theo đường tăng. ............................................................................ 89
Hình 13.1 Kết quả thi đấu của 5 đội bóng chuyền A, B, C, B, E ............................................. 95
Hình 13.2 Sơ đồ nhà của 8 học sinh ......................................................................................... 96
Hình 13.3 10 thành phố ............................................................................................................ 96
Hình 13.4 bố trí lịch thi cho học sinh THPT với 7 môn thi trong 7 ngày ................................ 97
Hình 13.5 Vị trí nhà ở và đường nối giữa các nhà của 9 học sinh ........................................... 98
Hình 13.6 Bản đồ có 6 miền ..................................................................................................... 99
Hình 13.7 Lập lịch thi 7 môn.................................................................................................. 102
Hình 13.8 Tô màu cho đồ thị lịch thi...................................................................................... 103
Trang 5

nguon tai.lieu . vn