Mô hình đồ thị cho một số bài toán thực tế

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUY NHƠN

PHẠM QUANG THIỆU

MÔ HÌNH ĐỒ THỊ CHO MỘT SỐ BÀI

TOÁN THỰC TẾ

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

Bình Định - 2022

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC QUY NHƠN

PHẠM QUANG THIỆU

MÔ HÌNH ĐỒ THỊ CHO MỘT SỐ BÀI

TOÁN THỰC TẾ

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

Mã số : 8 46 01 13

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

Người hướng dẫn: TS. Lâm Thị Thanh Tâm

Bình Định - 2022

Lời cam đoan

Tôi xin cam đoan rằng nội dung trình bày trong luận văn "Mô hình

đồ thị cho một số bài toán thực tế" là trung thực và không trùng lặp

với đề tài khác. Tôi cũng xin cam đoan rằng các kết quả nêu trong luận

văn, tài liệu tham khảo và nội dung trích dẫn đảm bảo tính trung thực,

chính xác.

Quy Nhơn, tháng 07 năm 2022

Học viên

Phạm Quang Thiệu

Mục lục

1 Kiến thức chuẩn bị 3

1.1 Khái niệm về đồ thị . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Bậc của đỉnh đồ thị . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Đường đi, chu trình . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . . 7

1.5 Đường đi Euler - Chu trình Euler . . . . . . . . . . . . . . 8

1.6 Đường đi Hamilton - Chu trình Hamilton . . . . . . . . . . 8

1.7 Số ổn định trong, số ổn định ngoài . . . . . . . . . . . . . . 9

1.8 Nhân của đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 10

1.9 Cây và bụi . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Một số thuật toán trong đồ thị 13

2.1 Các thuật toán xây dựng cây khung của đồ thị . . . . . . . 13

2.1.1 Thuật toán tìm kiếm ưu tiên chiều sâu . . . . . . . . 13

2.1.2 Thuật toán tìm kiếm ưu tiên chiều rộng . . . . . . . 15

2.2 Thuật toán tìm cây khung bé nhất . . . . . . . . . . . . . . 16

2.2.1 Thuật toán Kruskal . . . . . . . . . . . . . . . . . . 17

2.2.2 Thuật toán Prim . . . . . . . . . . . . . . . . . . . 17

2.3 Các thuật toán tìm số ổn định trong, số ổn định ngoài, nhân

của đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

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

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

2.3.3 Thuật toán tìm nhân bé nhất (hay tất cả các nhân

của đồ thị G) . . . . . . . . . . . . . . . . . . . . . 22

2.4 Thuật toán Dịjkstra tìm đường đi ngắn nhất . . . . . . . . 27

2.5 Thuật toán Fleury tìm chu trình Euler . . . . . . . . . . . . 30

2.6 Quy tắc tìm một chu trình Hamilton . . . . . . . . . . . . . 31

3 Mô hình đồ thị cho một số bài toán thực tế 33

3.1 Quy trình giải bài toán bằng phương pháp đồ thị . . . . . . 33

3.1.1 Xây dựng đồ thị G mô tả các quan hệ . . . . . . . . 33

3.1.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý

luận trực tiếp suy ra đáp án của bài toán D . . . . . 34

3.2 Bài toán về đường đi Euler - chu trình Euler . . . . . . . . 34

3.2.1 Bài toán 7 cây cầu ở Konigsberg . . . . . . . . . . . 34

3.2.2 Bài toán vẽ bàn cờ . . . . . . . . . . . . . . . . . . 36

3.2.3 Bài toán Người đưa thư Trung Hoa . . . . . . . . . 39

3.3 Bài toán về đường đi Hamilton - chu trình Hamilton . . . . 45

3.3.1 Trò chơi “Vòng quanh thế giới” . . . . . . . . . . . . 45

3.3.2 Bài toán sắp xếp chỗ ngồi . . . . . . . . . . . . . . . 46

3.3.3 Bài toán người du lịch . . . . . . . . . . . . . . . . . 47

3.4 Bài toán về số ổn định trong, số ổn định ngoài và nhân của

đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4.1 Bài toán tổng quát(trò chơi Nim) . . . . . . . . . . . 51

3.4.2 Thuật toán chơi dựa vào nhân đồ thị . . . . . . . . . 51

3.5 Bài toán tìm cây khung bé nhất . . . . . . . . . . . . . . . 57

3.6 Bài toán về đỉnh - cạnh của đồ thị. . . . . . . . . . . . . . . 60

3.7 Bài toán về đường đi, chu trình và đồ thị liên thông . . . . 64

TÀI LIỆU THAM KHẢO 69

1

Lời nói đầu

Lý thuyết đồ thị là một trong những ngành khoa học ra đời khá sớm.

Lý thuyết đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế

phức tạp.

Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện

trong bài báo của Leonhard Euler về Bảy cây cầu ở K¨onigsberg, xuất bản

năm 1736. Bài báo này cũng được xem như một trong những kết quả topo

đầu tiên trong hình học.

Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có

thể được biểu diễn bằng đồ thị. Do đó, lý thuyết đồ thị có rất nhiều ứng

dụng trong việc giải quyết các bài toán thực tế, chẳng hạng như: Bài toán

điều khiển giao thông, bài toán lập kế hoạch, bài toán hành trình ngắn

nhất,. . . . Với mong muốn tìm hiểu ứng dụng của lý thuyết đồ thị trong

việc giải một số bài toán thực tế, tôi chọn đề tài "Mô hình đồ thị cho

một số bài toán thực tế" để nghiên cứu cho luận văn thạc sĩ của mình.

Ngoài phần mở đầu và kết luận luận văn gồm 3 chương

. Chương 1. Kiến thức chuẩn bị

Trong chương này, tôi xin trình bày các định nghĩa, định lí cơ bản của

lý thuyết thuyết đồ thị.