Đồ thị

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

---------------

Nguyễn Thị Kim Ngân

ĐỒ THỊ

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên, năm 2015

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

---------------

Nguyễn Thị Kim Ngân

ĐỒ THỊ

Chuyên ngành: Phương pháp toán sơ cấp

Mã số: 60.46.01.13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS.TS. ĐÀM VĂN NHỈ

Thái Nguyên, năm 2015

i

Mục lục

Mở đầu 1

1 Một số khái niệm cơ bản 3

1.1 Tập hợp và quan hệ . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Tập hợp và phép toán . . . . . . . . . . . . . . . . 3

1.1.2 Quan hệ tương đương . . . . . . . . . . . . . . . . 4

1.2 Đồ thị và đường đi . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Khái niệm đồ thị . . . . . . . . . . . . . . . . . . 5

1.2.2 Đường đi và chu trình . . . . . . . . . . . . . . . 6

1.2.3 Bậc của đỉnh và tính liên thông của đồ thị . . . . . 7

1.3 Đồ thị con và sự đẳng hình . . . . . . . . . . . . . . . . . 12

1.3.1 Đồ thị con và đồ thị riêng . . . . . . . . . . . . . 12

1.3.2 Sự đẳng hình của các đồ thị . . . . . . . . . . . . 12

1.4 Một vài mô hình đồ thị . . . . . . . . . . . . . . . . . . . 13

1.4.1 Lấn tổ trong sinh học . . . . . . . . . . . . . . . . 13

1.4.2 Thi đấu vòng tròn . . . . . . . . . . . . . . . . . . 14

1.4.3 Bài toán đường đi . . . . . . . . . . . . . . . . . . 14

1.5 Chu trình Euler và chu trình Hamilton . . . . . . . . . . . 15

1.5.1 Chu trình Euler . . . . . . . . . . . . . . . . . . . 15

1.5.2 Chu trình Hamilton . . . . . . . . . . . . . . . . . 17

1.6 Tập ổn định . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6.1 Tập ổn định trong, tập ổn định ngoài . . . . . . . . 18

1.6.2 Tập nhân của đồ thị . . . . . . . . . . . . . . . . . 19

1.7 Chu số và Sắc số . . . . . . . . . . . . . . . . . . . . . . 20

1.7.1 Chu số của đồ thị . . . . . . . . . . . . . . . . . . 20

1.7.2 Sắc số của đồ thị . . . . . . . . . . . . . . . . . . 23

ii

2 Ứng dụng của lý thuyết đồ thị 25

2.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . 25

2.2 Ví dụ vận dụng . . . . . . . . . . . . . . . . . . . . . . . 26

Kết luận 38

Tài liệu tham khảo 39