Luận văn Một số vấn đề ứng dụng của đồ thị trong tin học

MỤC LỤC

Nội dung Trang

Lời nói đầu . 1

Giới thiệu đề tài . 2

Mục lục . 5

Chương 1 MỘT SỐ VẤN ĐỀ CƠ BẢN CỦA ĐỒ THỊ

9

I. CÁC ĐỊNH NGHĨA ĐỒ THỊ. 9

1. Định nghĩa đồ thị. 9

2. Đồ thị đơn . 10

3. Đa đồ thị . 10

4. Giả đồ thị. 10

II. CÁC LOẠI ĐỒ THỊ . 11

1. Đồ thị vô hướng . 11

2. Đồ thị có hướng . 11

3. Đồ thị hỗn hợp . 11

III. MỘT SỐ KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN CỦA ĐỒ . THỊ 11

1. Bậc đồ thị . 11

1.1 Bậc đồ thị vô hướng . 11

1.2 Bậc đồ thị có hướng . 12

2. Đường đi và chu trình . 13

2.1 Đường đi . 13

2.2 Chu trình . 13

3. Đồ thị liên thông . 14

4. Đồ thị con và đồ thị bộ phận . 15

IV. CÁC DẠNG BIỂU DIỄN CỦA ĐỒ THỊ . 15

1. Biểu diễn hình học của đồ thị . 15

2. Sự đẳng cấu . 16

3. Một số đồ thị đặc biệt . 17

3.1 Đồ thị đều . 17

3.2 Đồ thị đầy đủ . 17

3.3 Đồ thị bánh xe . 17

3.4 Một vài ứng dụng của đồ thị đặc biệt . 18

4. Biểu diễn đồ thị trên máy tính . 19

4.1 Biểu diễn bằng ma trận kề . 19

4.2 Danh sách cạnh (cung) . 22

4.3 Danh sách kề . 22

Chương 2 SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐỒ THỊ . 24

I. SỐ ỔN ĐỊNH TRONG, SỐ ỔN ĐỊNH NGOÀI, NHÂN ĐỒ THỊ . 24

1. Số ổn định trong . 24

2. Số ổn định ngoài . 24

3. Nhân đồ thị . 24

4. Các thuật toán tìm các tập ổn định trong cực đại, ổn định ngoài cực tiểu. 25

4.1 Thuật toán tìm số ổn định trong . 25

4.2 Thuật toán tìm số ổn định ngoài. 25

5. Ứng dụng đồ thị trong lập trình chơi cờ Ca rô. 26

II. TÔ MÀU ĐỒ THỊ . 29

1. Sắc số đồ thị . 29

2. Tô màu đồ thị phẳng. 31

2.1 Đồ thị phẳng. 31

2.2 Định lý 5 màu (Kempe - Heawood). 31

2.3 Bài toán 4 màu (Appel - Haken). 32

3. Ví dụ ứng dụng . 32

Chương 3 CHU TRÌNH, ĐƯỜNG ĐI EULER VÀ . HAMILTON TRONG ĐỒ THỊ 35

I. CHU TRÌNH VÀ ĐƯỜNG ĐI EULER . 35

1. Chu trình Euler . . 35

1.1 Định nghĩa . 35

1.2 Thuật toán tìm chu trình Euler . 37

2. Đường đi Euler . 38

2.1 Định nghĩa . 38

2.2 Thuật toán tìm đường Euler . 38

II. CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON . 39

1. Chu trình Hamilton . 39

2. Đường Hamilton . 40

3. Thuật toán liệt kê tất cả các chu trình Hamilton . 41

Chương 4 ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ . 42

I. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ KHÔNG CÓ TRỌNG SỐ . 42

1. Định nghĩa . 42

2. Thuật toán . 42

II. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ CÓ TRỌNG SỐ . 43

1. Các khái niệm . . . 43

2. Thuật toán tìm đường đi ngắn nhất cho đồ thị có trọng số . 44

2.1 Cơ sở thuật toán tìm đường đi ngắn nhất . 44

2.2 Thuật toán Dijkstra . 45

2.3 Thuật toán Ford - Bellman . 45

2.4 Thuật toán Floyd . 47

III. CÁC ỨNG DỤNG . 47

1. Ứng dụng trong truyền tin. 47

2. Ứng dụng trong việc lập lịch thi công của một công trình . 50

IV. CHƯƠNG TRÌNH MÔ TẢ THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI NGẮN NHẤT 53

Chương 5 MỘT SỐ VẤN ĐỀ VỀ CÂY . 56

I. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN . 56

1. Định nghĩa . 56

2. Một số khái niệm cơ bản . 57

3. Cây m phân . 58

4. Các ứng dụng . 58

4.1 Mã tiền tố . 58

4.2 Cây biểu diễn biểu thức . 61

4.3 Cây quyết định . 62

4.4 Cây sắp xếp và tìm kiếm . 63

4.4.1 Sắp xếp chèn với tìm kiếm nhị phân . 63

4.4.2 Thuật toán sắp xếp hoà nhập . 65

4.4.3 Thuật toán sắp xếp nhanh . 68

II. CÂY BAO TRÙM . 70

1. Định nghĩa và các tính chất . 70

2. Các thuật toán tìm cây bao trùm . 71

2.1 Thuật toán theo lý thuyết . 71

2.2 Thuật toán tìm kiếm ưu tiên chiều sâu và chiều rộng . 71

2.2.1 Kỹ thuật quay lui . 72

2.2.2 Thuật toán tìm kiếm theo chiều sâu . 72

2.2.3 Thuật toán tìm kiếm theo chiều rộng . 73

2.3 Chương trình thể hiện cho các thuật toán . 73

2.3.1 Chương trình Pascal về thuật toán quay lui . 73

2.3.2 Chương trình cho thuật toán tìm kiếm chiều sâu và chiều rộng 74

3. Cây bao trùm bé nhất . 76

3.1 Định nghĩa . 76

3.2 Thuật toán tìm cây bao trùm bé nhất . 76

3.2.1 Thuật toán Kruskal . 76

3.2.2 Thuật toán Prim . 77

3.2.3 Chương trình thể hiện thuật toán . 78

3.3 Ứng dụng cho bài toán kết nối hệ thống mạng . 81

4. Cây bao trùm lớn nhất . 81

4.1 Định nghĩa . 81

4.2 Thuật toán tìm cây bao trùm lớn nhất . 81

Kết luận . 83

Tài liệu tham khảo . 84