Bài 1. Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton

Bài 1. Một vài yếu tố của Lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton - Toán 11 Cánh Diều

Lí thuyết đồ thị là một nhánh quan trọng của toán học rời rạc, có ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học máy tính, kỹ thuật, kinh tế và xã hội. Bài học này sẽ cung cấp cho các em những kiến thức nền tảng về lí thuyết đồ thị, giúp các em hiểu rõ hơn về cấu trúc và tính chất của các đồ thị.

1. Đồ thị - Định nghĩa và các khái niệm cơ bản

Một đồ thị (graph) G = (V, E) bao gồm một tập hợp hữu hạn các đỉnh (vertices) V và một tập hợp các cạnh (edges) E, trong đó mỗi cạnh nối hai đỉnh.

• Đỉnh (vertex): Đại diện cho một đối tượng trong bài toán.
• Cạnh (edge): Đại diện cho mối quan hệ giữa hai đối tượng.
• Đồ thị vô hướng (undirected graph): Cạnh không có hướng, tức là có thể đi từ đỉnh A đến đỉnh B và ngược lại.
• Đồ thị có hướng (directed graph): Cạnh có hướng, tức là chỉ có thể đi từ đỉnh A đến đỉnh B theo một chiều nhất định.
• Bậc của đỉnh (degree of a vertex): Số lượng cạnh kề với đỉnh đó.
• Đồ thị liên thông (connected graph): Có đường đi giữa bất kỳ hai đỉnh nào trong đồ thị.

2. Đường đi Euler và Đường đi Hamilton

Đây là hai loại đường đi đặc biệt trong đồ thị:

• Đường đi Euler (Eulerian path): Là một đường đi đi qua tất cả các cạnh của đồ thị đúng một lần. Một đồ thị có đường đi Euler khi và chỉ khi nó có tối đa hai đỉnh bậc lẻ.
• Đường đi Hamilton (Hamiltonian path): Là một đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần. Việc tìm đường đi Hamilton là một bài toán khó trong lí thuyết đồ thị.

3. Ví dụ minh họa

Xét đồ thị G có các đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đây là một đồ thị vô hướng có 4 đỉnh và 4 cạnh.

Trong đồ thị này, mỗi đỉnh đều có bậc 2, do đó đồ thị có đường đi Euler. Một đường đi Euler có thể là A-B-C-D-A.

Xét đồ thị G' có các đỉnh A, B, C, D và các cạnh AB, BC, CD, DA, AC. Đồ thị này có đường đi Hamilton A-B-C-D-A hoặc A-C-B-D-A.

4. Ứng dụng của Lí thuyết đồ thị

Lí thuyết đồ thị có nhiều ứng dụng thực tế, ví dụ:

• Mạng lưới giao thông: Mô hình hóa các tuyến đường, các giao lộ và các phương tiện giao thông.
• Mạng xã hội: Mô hình hóa các mối quan hệ giữa các người dùng.
• Lập lịch trình: Tìm cách tối ưu hóa lịch trình làm việc, lịch trình học tập.
• Thiết kế mạch điện: Mô hình hóa các linh kiện và các kết nối trong mạch điện.

5. Bài tập vận dụng

Hãy xác định xem đồ thị sau có đường đi Euler hay đường đi Hamilton:

(Vẽ một đồ thị đơn giản ở đây)

Giải bài tập 1, 2, 3 trang 10 sách giáo khoa Toán 11 Cánh Diều Chuyên đề II.

Hy vọng bài học này đã cung cấp cho các em những kiến thức cơ bản và hữu ích về Lí thuyết đồ thị. Chúc các em học tập tốt!