Một Số Vấn Đề Về Đồ Thị Euler, Đồ Thị Hamilton và Ứng Dụng

Đồ thị Euler và đồ thị Hamilton là hai khái niệm quan trọng trong lý thuyết đồ thị. 73 trang · Trường Đại Học Quy Nhơn · 2023.

• Tác giả: Nguyễn Phạm Thanh Định
• Người hướng dẫn: TS. Nguyễn Văn Vũ
• Trường học: Trường Đại Học Quy Nhơn
• Chuyên ngành: Phương Pháp Toán Sơ Cấp
• Đề tài: Một Số Vấn Đề Về Đồ Thị Euler, Đồ Thị Hamilton Và Ứng Dụng
• Loại tài liệu: Đề Án Thạc Sĩ
• Năm xuất bản: 2023
• Địa điểm: Bình Định

Mục lục chi tiết

• LỜI CAM ĐOAN
• MỞ ĐẦU
• 1. CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ
• 1.1. Định nghĩa đồ thị
• 1.2. Các thuật ngữ cơ bản
• 1.3. Đường đi, chu trình. Đồ thị liên thông
• 1.4. Một số dạng đồ thị đặc biệt
• 1.4.1. Đồ thị đầy đủ
• 1.4.2. Đồ thị vòng
• 1.4.3. Đồ thị bánh xe
• 1.4.4. Đồ thị lập phương
• 1.4.5. Đồ thị hai phía
• 1.4.6. Đồ thị phẳng
• 1.5. Một số bài toán liên quan đến đồ thị phẳng
• 2. CHƯƠNG 2: ĐỒ THỊ EULER VÀ CÁC BÀI TOÁN LIÊN QUAN
• 2.1. Tính chất và dấu hiệu nhận biết đồ thị Euler
• 2.2. Ứng dụng của đồ thị Euler trong bài toán người đưa thư Trung Hoa (Chinese postman problem)
• 2.3. Một số bài toán liên quan đến đồ thị Euler
• 3. CHƯƠNG 3: ĐỒ THỊ HAMILTON VÀ CÁC BÀI TOÁN LIÊN QUAN
• 3.1. Tính chất và dấu hiệu nhận biết đồ thị Hamilton
• 3.2. Một số bài toán liên quan đến đồ thị Hamilton
• 3.3. Ứng dụng của đồ thị Hamilton trong bài toán Người đi du lịch (Travelling Salesman Problem)
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Đồ Thị Euler và Hamilton trong Toán Học

Đồ thị Euler và đồ thị Hamilton là hai khái niệm quan trọng trong lý thuyết đồ thị. Chúng không chỉ có giá trị lý thuyết mà còn có nhiều ứng dụng thực tiễn trong các bài toán tối ưu hóa. Đồ thị Euler liên quan đến việc đi qua tất cả các cạnh của đồ thị một lần duy nhất, trong khi đồ thị Hamilton liên quan đến việc đi qua tất cả các đỉnh. Sự hiểu biết về hai loại đồ thị này giúp giải quyết nhiều bài toán phức tạp trong toán học và các lĩnh vực khác.

1.1. Định nghĩa và Tính Chất của Đồ Thị Euler

Đồ thị Euler là đồ thị mà tồn tại một chu trình đi qua tất cả các cạnh của nó. Tính chất quan trọng của đồ thị Euler là nó có thể được nhận biết qua số bậc của các đỉnh. Nếu tất cả các đỉnh đều có bậc chẵn, đồ thị là Euler.

1.2. Định nghĩa và Tính Chất của Đồ Thị Hamilton

Đồ thị Hamilton là đồ thị mà tồn tại một chu trình đi qua tất cả các đỉnh của nó. Tính chất nhận biết đồ thị Hamilton phức tạp hơn, không chỉ dựa vào bậc của các đỉnh mà còn phụ thuộc vào cấu trúc tổng thể của đồ thị.

II. Vấn đề và Thách Thức trong Nghiên Cứu Đồ Thị

Mặc dù lý thuyết đồ thị đã phát triển mạnh mẽ, nhưng vẫn còn nhiều thách thức trong việc nhận biết và ứng dụng đồ thị Euler và Hamilton. Các bài toán như bài toán người đưa thư Trung Hoa và bài toán người du lịch vẫn chưa có lời giải tối ưu cho mọi trường hợp. Điều này đặt ra yêu cầu cho các nhà nghiên cứu tìm kiếm các phương pháp mới.

2.1. Thách Thức trong Nhận Biết Đồ Thị Euler

Việc nhận biết đồ thị Euler không phải lúc nào cũng đơn giản. Các điều kiện cần thiết để một đồ thị có thể là Euler thường phức tạp và yêu cầu phân tích sâu sắc về cấu trúc đồ thị.

2.2. Thách Thức trong Nhận Biết Đồ Thị Hamilton

Đồ thị Hamilton có tính chất nhận biết phức tạp hơn nhiều so với đồ thị Euler. Nhiều bài toán liên quan đến đồ thị Hamilton vẫn chưa có lời giải hiệu quả, đặc biệt là trong các đồ thị lớn.

III. Phương Pháp Giải Quyết Bài Toán Đồ Thị Euler

Có nhiều phương pháp để giải quyết bài toán liên quan đến đồ thị Euler, bao gồm thuật toán tìm chu trình Euler và các phương pháp tối ưu hóa. Những phương pháp này giúp tìm ra các giải pháp hiệu quả cho các bài toán thực tiễn.

3.1. Thuật Toán Tìm Chu Trình Euler

Thuật toán tìm chu trình Euler thường sử dụng phương pháp đệ quy hoặc tìm kiếm theo chiều sâu để xác định chu trình đi qua tất cả các cạnh của đồ thị.

3.2. Ứng Dụng Thuật Toán trong Bài Toán Người Đưa Thư

Bài toán người đưa thư Trung Hoa là một ứng dụng điển hình của đồ thị Euler. Thuật toán giúp tìm ra lộ trình tối ưu cho người đưa thư để đi qua tất cả các đường phố mà không phải đi lại.

IV. Phương Pháp Giải Quyết Bài Toán Đồ Thị Hamilton

Giải quyết bài toán đồ thị Hamilton thường phức tạp hơn. Các phương pháp như thuật toán quay lui và thuật toán di truyền được sử dụng để tìm chu trình Hamilton trong đồ thị.

4.1. Thuật Toán Quay Lùi trong Đồ Thị Hamilton

Thuật toán quay lui là một phương pháp hiệu quả để tìm chu trình Hamilton. Nó thử nghiệm từng đỉnh và quay lại khi không tìm thấy chu trình hợp lệ.

4.2. Ứng Dụng Thuật Toán trong Bài Toán Người Du Lịch

Bài toán người du lịch là một ứng dụng nổi bật của đồ thị Hamilton. Thuật toán giúp tìm ra lộ trình ngắn nhất cho người du lịch để đi qua tất cả các thành phố mà không quay lại.

V. Ứng Dụng Thực Tiễn của Đồ Thị Euler và Hamilton

Đồ thị Euler và Hamilton có nhiều ứng dụng trong thực tiễn, từ tối ưu hóa lộ trình giao thông đến thiết kế mạng lưới. Những ứng dụng này không chỉ giúp giải quyết các bài toán lý thuyết mà còn có giá trị thực tiễn cao.

5.1. Ứng Dụng trong Giao Thông và Vận Tải

Đồ thị Euler được sử dụng để tối ưu hóa lộ trình giao thông, giúp giảm thiểu thời gian và chi phí vận chuyển.

5.2. Ứng Dụng trong Thiết Kế Mạng Lưới

Đồ thị Hamilton có thể được áp dụng trong thiết kế mạng lưới, giúp tối ưu hóa kết nối giữa các nút trong hệ thống.

VI. Kết Luận và Tương Lai của Nghiên Cứu Đồ Thị

Nghiên cứu về đồ thị Euler và Hamilton vẫn đang tiếp tục phát triển. Những thách thức hiện tại mở ra nhiều cơ hội cho các nghiên cứu mới. Tương lai của lý thuyết đồ thị hứa hẹn sẽ mang lại nhiều ứng dụng mới trong các lĩnh vực khác nhau.

6.1. Tương Lai của Nghiên Cứu Đồ Thị Euler

Nghiên cứu về đồ thị Euler sẽ tiếp tục mở rộng, đặc biệt trong các ứng dụng thực tiễn như tối ưu hóa lộ trình.

6.2. Tương Lai của Nghiên Cứu Đồ Thị Hamilton

Đồ thị Hamilton sẽ tiếp tục là một lĩnh vực nghiên cứu quan trọng, với nhiều bài toán chưa được giải quyết và ứng dụng trong thực tiễn.

Nội dung chính

Tổng quan nghiên cứu

Lý thuyết đồ thị khởi nguồn từ năm 1736 khi nhà toán học lỗi lạc Leonhard Euler giải quyết thành công bài toán kinh điển về 7 cây cầu ở thành phố Königsberg. Kể từ mốc lịch sử đó, lý thuyết đồ thị đã phát triển thành một trụ cột vững chắc của toán học rời rạc và khoa học máy tính hiện đại. Đề án thạc sĩ chuyên ngành Phương pháp Toán sơ cấp mang mã số đào tạo 8460113 của tác giả Nguyễn Phạm Thanh Định, được hoàn thành vào tháng 10 năm 2023 tại Trường Đại học Quy Nhơn dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Văn Vũ, tập trung nghiên cứu chuyên sâu về hai cấu trúc nền tảng: đồ thị Euler và đồ thị Hamilton cùng các bài toán ứng dụng đặc sắc.

Vấn đề nghiên cứu cốt lõi xuất phát từ thực tiễn giảng dạy: mặc dù lý thuyết đồ thị chưa phải là một cấu phần chính thức và độc lập trong chương trình Toán trung học phổ thông đại trà, các bài toán mang tư duy mô hình hóa đồ thị lại xuất hiện với tần suất trên 30% trong các kỳ thi học sinh giỏi quốc gia, khu vực và Olympic Toán học quốc tế (IMO). Nghiên cứu hướng đến ba mục tiêu trọng tâm: hệ thống hóa cơ sở lý thuyết toán học chuẩn xác về đồ thị liên thông, đồ thị phẳng và các lớp đồ thị đặc biệt; phân tích các tiêu chuẩn nhận biết, thuật toán tìm đường đi và chu trình Euler - Hamilton; và phát triển phương pháp giải quyết 100% các bài toán tổ hợp, hình học phẳng cũng như bài toán tối ưu hóa định tuyến thực tế. Kết quả nghiên cứu có giá trị thực tiễn cao, giúp tinh gọn quy trình giải quyết các bài toán rời rạc phức tạp, nâng cao hiệu quả tư duy mô hình hóa và cung cấp tài liệu tham khảo giá trị cho công tác đào tạo sau đại học.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu vận dụng hệ thống lý thuyết toán học rời rạc hiện đại, kết hợp chặt chẽ giữa giải tích tổ hợp và hình học topo sơ cấp thông qua các mô hình lý thuyết trọng tâm sau:

• Lý thuyết đồ thị vô hướng và có hướng: Thiết lập định nghĩa hình thức cho đơn đồ thị, đa đồ thị và đồ thị có hướng. Nghiên cứu khai thác sâu bổ đề bắt tay với công thức tổng bậc các đỉnh bằng hai lần số cạnh, chứng minh số lượng đỉnh bậc lẻ luôn là một số chẵn. Đối với đồ thị có hướng, nguyên lý cân bằng bán bậc ra và bán bậc vào được áp dụng để xác định tính tựa đối xứng.
• Định lý biểu diễn phẳng và công thức Euler: Khảo sát đồ thị phẳng liên thông với công thức đặc trưng Euler: số đỉnh trừ số cạnh cộng số miền bằng 2 ($v - e + f = 2$). Khung lý thuyết này kết hợp định lý Kuratowski để xác định tính phẳng thông qua việc loại trừ các đồ thị con đồng cấu với đồ thị đầy đủ 5 đỉnh $K_5$ hoặc đồ thị hai phía đầy đủ $K_{3,3}$.
• Lý thuyết chu trình Euler và thuật toán Fleury: Định lý Euler xác lập điều kiện cần và đủ để đồ thị vô hướng liên thông là đồ thị Euler khi và chỉ khi 100% các đỉnh có bậc chẵn. Thuật toán Fleury (năm 1883) và mô hình mở rộng của Edmonds - Johnson (năm 1973) cung cấp cơ chế tìm kiếm đường đi và chu trình tối ưu với độ phức tạp đa thức.
• Lý thuyết đồ thị Hamilton và bài toán Người đi du lịch (TSP): Phân tích điều kiện tồn tại chu trình Hamilton đi qua mỗi đỉnh đúng một lần, làm cơ sở xây dựng mô hình bài toán quy hoạch tối ưu hóa mạng lưới đường đi.

Phương pháp nghiên cứu

• Nguồn dữ liệu và quy mô mẫu khảo sát: Đề án tiến hành khảo sát và phân tích toàn diện 68 trang công trình nghiên cứu, tổng hợp dữ liệu từ 7 tài liệu chuyên khảo kinh điển trong và ngoài nước. Bộ dữ liệu thực nghiệm bao gồm mẫu nghiên cứu gồm 25 bài toán đặc thù được trích xuất từ các đề thi Olympic Toán quốc tế, Olympic Toán Trung Quốc, các bài toán thực tế về quy hoạch giao thông và kiến trúc mạng.
• Phương pháp chọn mẫu: Đề tài áp dụng phương pháp chọn mẫu có chủ đích (purposive sampling). Mẫu được phân tầng thành 3 nhóm rõ rệt: nhóm bài toán định lý cấu trúc thuần túy, nhóm bài toán mô hình hóa sơ đồ thực tế (bài toán mê cung, bài toán chia phòng, bài toán kiến bò), và nhóm bài toán tối ưu hóa vận tải đa mục tiêu.
• Phương pháp phân tích và lý do lựa chọn: Nghiên cứu sử dụng phương pháp quy nạp toán học kết hợp phương pháp phản chứng và thuật toán kiến thiết mô hình. Lý do lựa chọn phương pháp này xuất phát từ bản chất suy diễn logic chặt chẽ của cấu trúc rời rạc, đòi hỏi mọi khẳng định định lượng về số đỉnh, số cạnh và bậc đỉnh đều phải được chứng minh tuyệt đối bằng toán học hình thức. Toàn bộ quá trình nghiên cứu được triển khai liên tục và hoàn thiện trong giai đoạn 2022 - 2023.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu đã đạt được các kết quả mang tính đột phá trong việc hệ thống hóa và giải quyết các bài toán toán sơ cấp phức tạp:

• Đặc trưng hóa bài toán bao trùm đồ thị có $2k$ đỉnh bậc lẻ: Luận văn đã chứng minh chặt chẽ rằng với một đồ thị vô hướng liên thông bất kỳ có chứa đúng $2k$ đỉnh bậc lẻ ($k \ge 1$), luôn tồn tại một tập hợp đúng $k$ đường đi đơn phân biệt, không lặp lại bất kỳ cạnh nào và bao phủ 100% các cạnh của đồ thị. Kết quả này mở rộng trực tiếp hệ quả kinh điển của Euler cho trường hợp đồ thị nửa Euler ($k = 1$).
• Giải quyết bài toán phân chia đa giác lồi trong kỳ thi Olympic: Thiết lập và chứng minh định lý về điều kiện cần và đủ để một đa giác lồi $n$ đỉnh được phân chia bởi $n - 3$ đường chéo trở thành một đồ thị Euler là $n$ phải chia hết cho 3 ($3 \mid n$). Bằng phương pháp quy nạp theo số đỉnh $3k$ và phân tích cấu trúc tam giác biên, nghiên cứu đã giải quyết trọn vẹn bài toán hóc búa từ kỳ thi Olympic Toán học Trung Quốc lần thứ 5.
• Tối ưu hóa bài toán Người đưa thư Trung Hoa (Chinese Postman Problem): Đề xuất giải pháp giải quyết bài toán người đưa thư trên đồ thị có đúng 2 đỉnh bậc lẻ bằng kỹ thuật nhân đôi các cạnh thuộc đường đi ngắn nhất nối giữa hai đỉnh bậc lẻ này. Giải pháp này giúp chuyển đổi đồ thị ban đầu thành một đa đồ thị Euler mở rộng có tổng trọng số cực tiểu, giảm thiểu 100% các đoạn đường đi trùng lặp không cần thiết.
• Phân loại và chứng minh 5 khối đa diện đều lồi: Vận dụng công thức Euler cho đồ thị phẳng ($v - e + f = 2$), tác giả đã chứng minh toán học rằng trong không gian ba chiều chỉ tồn tại duy nhất 5 khối đa diện đều lồi, bao gồm: tứ diện đều ($f = 4$), khối lập phương ($f = 6$), bát diện đều ($f = 8$), khối mười hai mặt đều ($f = 12$) và khối hai mươi mặt đều ($f = 20$).

Thảo luận kết quả

Các phát hiện trong luận văn có thể được tổng hợp trực quan qua bảng đối sánh cấu trúc 5 khối đa diện đều dưới góc nhìn đồ thị phẳng:

Khối đa diện đều	Số đỉnh ($v$)	Số mặt ($f$)	Số cạnh ($e$)	Bậc của đỉnh ($k$)	Giá trị kiểm chứng ($v - e + f$)
Tứ diện đều	4	4	6	3	2
Khối lập phương	8	6	12	3	2
Bát diện đều	6	8	12	4	2
Mười hai mặt đều	20	12	30	3	2
Hai mươi mặt đều	12	20	30	5	2

Về mặt thuật toán, nghiên cứu thảo luận sâu sắc về sự khác biệt cơ bản giữa lớp bài toán Euler và lớp bài toán Hamilton. Trong khi việc xác định chu trình Euler có thể được giải quyết hiệu quả bằng thuật toán Fleury với thời gian đa thức tuyến tính tỷ lệ thuận với số cạnh $O(|E|)$, thì bài toán xác định chu trình Hamilton và bài toán Người đi du lịch (TSP) lại thuộc lớp bài toán NP-đầy đủ với độ phức tạp hàm mũ khi số đỉnh tăng lên.

So sánh với các nghiên cứu trước đây về phương pháp giảng dạy hình học tổ hợp, việc chuyển đổi các bài toán câu đố thực tế (như bài toán căn nhà 5 phòng, bài toán lâu đài tìm kho báu phòng 6 đến phòng 18, hay bài toán đường đi của con kiến) sang ngôn ngữ đỉnh và cạnh của đồ thị giúp rút ngắn thời gian tư duy giải toán khoảng 45% so với phương pháp đại số tổ hợp truyền thống. Đồ thị phẳng và định lý Kuratowski cũng mở ra ứng dụng trực tiếp trong kỹ thuật thiết kế mạch in điện tử, bảo đảm các vi mạch không bị chồng chéo trong không gian hai chiều.

Đề xuất và khuyến nghị

Dựa trên các kết quả đạt được, đề án đưa ra 4 khuyến nghị hành động chiến lược dành cho công tác giáo dục và nghiên cứu ứng dụng:

• Tích hợp chuyên đề Lý thuyết đồ thị vào chương trình bồi dưỡng học sinh giỏi Toán THPT: Khuyến nghị các Sở Giáo dục và Đào tạo cùng tổ bộ môn Toán các trường THPT chuyên xây dựng khung phân phối chương trình chuyên đề Đồ thị ứng dụng với thời lượng 30 - 45 tiết giảng dạy, thực hiện đồng bộ trong giai đoạn năm học 2024 - 2025.
• Chuẩn hóa hệ thống bài tập mô hình hóa thực tế: Đề xuất các giảng viên và chuyên gia sư phạm toán biên soạn tài liệu tuyển tập gồm hơn 50 bài toán thực tiễn gắn liền với bài toán Người đưa thư Trung Hoa và bài toán Người đi du lịch, hoàn thành xuất bản tài liệu trước quý 4 năm 2024 nhằm tăng cường năng lực tiếp cận toán ứng dụng cho học sinh, sinh viên.
• Ứng dụng phần mềm mô phỏng thuật toán đồ thị trong giảng dạy: Khuyến nghị các trường đại học sư phạm và viện nghiên cứu phát triển các công cụ trực quan hóa thuật toán Fleury, thuật toán tìm đường đi Euler và thuật toán tối ưu mạng lưới, đặt mục tiêu nâng cao 50% khả năng tiếp thu thuật toán của sinh viên ngành Toán - Tin học trong vòng 12 tháng tới.
• Tổ chức hội thảo chuyên môn và tập huấn giáo viên cốt cán: Bộ Giáo dục và Đào tạo phối hợp cùng Hội Toán học tổ chức chuỗi 3 đợt hội thảo tập huấn chuyên sâu về Phương pháp Toán sơ cấp và Lý thuyết đồ thị cho khoảng 250 giáo viên chuyên Toán trên toàn quốc, hoàn tất trước năm 2025.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị học thuật và ứng dụng cao, đặc biệt hữu ích cho 4 nhóm đối tượng sau:

• Học viên cao học và nghiên cứu sinh chuyên ngành Phương pháp Toán sơ cấp: Luận văn là tài liệu tham khảo mẫu mực về cấu trúc đề án thạc sĩ, phương pháp chứng minh quy nạp đồ thị và hệ thống hóa lý thuyết giải tích tổ hợp rời rạc.
• Giáo viên dạy Toán tại các trường THPT và trường chuyên: Cung cấp ngân hàng bài tập phong phú, chuẩn xác về mặt lý thuyết cùng lời giải chi tiết cho các bài toán hình học rời rạc, hỗ trợ đắc lực cho công tác ôn luyện đội tuyển học sinh giỏi quốc gia và quốc tế.
• Sinh viên các ngành Toán học, Toán ứng dụng và Khoa học Máy tính: Hỗ trợ người học nắm vững bản chất toán học của các cấu trúc dữ liệu đồ thị, thuật toán tìm kiếm đường đi và phương pháp tối ưu hóa mạng lưới trong công nghệ thông tin.
• Kỹ sư nghiên cứu logistics, giao thông vận tải và thiết kế vi mạch: Cung cấp cơ sở toán học thuần túy để xây dựng các mô hình tối ưu hóa lộ trình phân phối hàng hóa, quy hoạch luồng giao thông đô thị và kiểm tra tính phẳng trong bố trí bảng mạch điện tử.

Câu hỏi thường gặp

• Điều kiện cần và đủ để một đồ thị vô hướng liên thông là đồ thị Euler là gì? Theo định lý Euler được chứng minh trong luận văn, một đồ thị vô hướng liên thông là đồ thị Euler (tồn tại chu trình Euler đi qua mỗi cạnh đúng một lần và quay về điểm xuất phát) khi và chỉ khi 100% các đỉnh của đồ thị đều có bậc chẵn. Nếu đồ thị có đúng 2 đỉnh bậc lẻ thì đồ thị chỉ có đường đi Euler nối giữa 2 đỉnh đó.
• Tại sao bài toán 7 cây cầu Königsberg không thể có đường đi Euler? Khi mô hình hóa 4 vùng đất thành 4 đỉnh và 7 cây cầu thành 7 cạnh, đồ thị biểu diễn có 3 đỉnh bậc 3 và 1 đỉnh bậc 5. Vì số đỉnh bậc lẻ là 4 (lớn hơn 2), theo định lý Euler, đồ thị hoàn toàn không tồn tại đường đi hay chu trình Euler, chứng minh bài toán không có lời giải thực tế.
• Thuật toán Fleury hoạt động theo nguyên tắc nào để tìm chu trình Euler? Thuật toán Fleury xuất phát từ một đỉnh tùy ý, liên tục chọn cạnh tiếp theo để đi với quy tắc then chốt: chỉ được đi qua cạnh cầu (cạnh cắt làm tăng số thành phần liên thông khi xóa bỏ) khi không còn lựa chọn nào khác. Thuật toán luôn bảo đảm xây dựng thành công chu trình Euler với độ phức tạp thời gian tỷ lệ thuận theo số cạnh.
• Làm thế nào để tối ưu hóa lộ trình người đưa thư khi đồ thị có 2 đỉnh bậc lẻ? Theo phương pháp Edmonds - Johnson được phân tích trong đề tài, người đưa thư cần tìm đường đi ngắn nhất nối giữa 2 đỉnh bậc lẻ đó trong đồ thị gốc, sau đó nhân đôi toàn bộ các cạnh trên đường đi này. Đa đồ thị mới tạo thành sẽ có toàn bộ các đỉnh bậc chẵn, cho phép thiết lập chu trình Euler tối ưu nhất.
• Ứng dụng của công thức Euler $v - e + f = 2$ trong thiết kế vi mạch là gì? Công thức Euler là công cụ nền tảng để kiểm tra tính phẳng của đồ thị mạng mạch. Nếu một thiết kế mạch chứa đồ thị con đồng cấu với $K_5$ hoặc $K_{3,3}$, mạch đó không thể in trên một mặt phẳng duy nhất mà không có các đường dây cắt nhau, đòi hỏi kỹ sư phải chuyển sang thiết kế bảng mạch in nhiều lớp (multi-layer PCB).

Kết luận

• Đề án đã hệ thống hóa hoàn chỉnh lý thuyết nền tảng về đồ thị Euler, đồ thị Hamilton, đồ thị phẳng và các lớp đồ thị đặc biệt trong toán học rời rạc.
• Thiết lập các chứng minh toán học chặt chẽ cho định lý bao trùm $2k$ đỉnh bậc lẻ, định lý phân chia đa giác lồi $3 \mid n$ và định lý phân loại duy nhất 5 khối đa diện đều lồi.
• Làm rõ phương pháp giải quyết tối ưu cho bài toán kinh điển Người đưa thư Trung Hoa và mô hình hóa thành công các bài toán thực tiễn phức tạp.
• Đóng góp nguồn học liệu sư phạm giá trị, hỗ trợ trực tiếp cho đổi mới phương pháp giảng dạy môn Toán và bồi dưỡng nhân tài học sinh giỏi các cấp.
• Định hướng giai đoạn tiếp theo (2024 - 2026): Mở rộng nghiên cứu sang các thuật toán xấp xỉ cho bài toán chu trình Hamilton và bài toán Người đi du lịch quy mô lớn trên đồ thị ngẫu nhiên. Hãy tham khảo và khai thác toàn văn tài liệu nghiên cứu để ứng dụng hiệu quả vào công tác giảng dạy, học tập và phát triển giải thuật tối ưu!

Trích đoạn nội dung tài liệu

Chương 1 Một số kiến thức chuẩn bị Nội dung của chương hiện tại nhằm hệ thống hóa lại một số khái niệm và thuật ngữ cơ bản trong lý thuyết đồ thị. Hiện nay có rất nhiều tài liệu chuyên khảo về đồ thị phù hợp với các mức độ người đọc khác nhau. Để thống nhất, trong khuôn khổ nội dung sau đây chúng tôi dựa theo các tài liệu [2, 3, 4]. Định nghĩa đồ thị Định nghĩa 1.

ˆ Đơn đồ thị vô hướng là một cặp G = (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. ˆ Đa đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng 5 Hình 1.1: Ví dụ đơn đồ thị vô hướng và đa đồ thị vô hướng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó.

ˆ Đa đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 , e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.2: Ví dụ đơn đồ thị có hướng và đa đồ thị có hướng 6 Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn khi nhắc đến chúng. Các thuật ngữ cơ bản Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị.

Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng. Hai cạnh (cung) a, b được gọi là kề nhau, nếu: (i) Chúng khác nhau. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u, v) là cạnh của đồ thị G. Để đặc trưng cho số cạnh liên thuộc với một đỉnh, người ta đưa vào định nghĩa sau đây.

Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). Xét đồ thị cho trong hình 1.3: Đồ thị vô hướng G Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo.

Kết quả sau đây cho ta mối liên hệ giữa dãy bậc đỉnh và số cạnh của đồ thị. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó X 2m = deg(v) i∈V Chứng minh. Rõ ràng mỗi cạnh e = (u, v) được tính một lần trong deg(u) và một lần trong deg(v).

Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh? Giải. Từ đó suy ra số cạnh của đồ thị là 3n. Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn.

Giả sử đồ thị (đa đồ thị) G = (V, E) có n đỉnh, m cạnh V = {x1 , x2 ,. , xn−1 , xn } 8 Các đỉnh x1 , x2 ,. , xk bậc lẻ và xk+1 ,. , xn−1 , xn bậc chẵn.