Bài 1. Một Vài Yếu Tố Của Lí Thuyết Đồ Thị. Đường Đi Euler Và Đường Đi Hamilton

Chào mừng bạn đến với bài học đầu tiên của chuyên đề Lí thuyết đồ thị trong chương trình Toán 11 Cánh Diều Chuyên đề II. Bài học này sẽ giới thiệu những khái niệm cơ bản về đồ thị, bao gồm các yếu tố cấu thành, các loại đồ thị và đặc biệt là hai khái niệm quan trọng: đường đi Euler và đường đi Hamilton.

Chúng ta sẽ cùng nhau khám phá cách xác định và xây dựng các đường đi này, cũng như ứng dụng của chúng trong giải quyết các bài toán thực tế.

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

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 cung cấp nền tảng kiến thức cơ bản để bạn có thể tiếp cận và giải quyết các bài toán liên quan đến đồ 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 đó.
Đường đi (path): Một dãy các đỉnh liên tiếp nhau bởi các cạnh.
Chu trình (cycle): Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.

2. Đường đi Euler

Một đườ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ẻ.

Định lý Euler: Một đồ thị liên thông có đường đi Euler khi và chỉ khi số đỉnh bậc lẻ của đồ thị bằng 0 hoặc 2.

Ví dụ:

Xét đồ thị G có các đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đồ thị này có một chu trình Euler: A -> B -> C -> D -> A.

3. Đường đi Hamilton

Một đườ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. Một đồ thị có đường đi Hamilton khi và chỉ khi có thể sắp xếp các đỉnh theo một thứ tự sao cho hai đỉnh liên tiếp trong thứ tự đó kề nhau trong đồ thị.

Bài toán người bán hàng du lịch (Traveling Salesman Problem - TSP): Một ứng dụng nổi tiếng của đường đi Hamilton là bài toán tìm đường đi ngắn nhất đi qua tất cả các thành phố và quay trở lại điểm xuất phát.

Ví dụ:

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ó một đường đi Hamilton: A -> B -> C -> D.

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

Mạng lưới giao thông: Mô hình hóa các tuyến đường, nút giao thông và tìm đường đi ngắn nhất.
Mạng xã hội: Phân tích mối quan hệ giữa các người dùng, tìm cộng đồng và đề xuất bạn bè.
Khoa học máy tính: Thiết kế thuật toán, phân tích dữ liệu và tối ưu hóa hiệu suất.
Kỹ thuật: Thiết kế mạch điện, phân tích mạng lưới điện và tối ưu hóa hệ thống.

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

Cho đồ thị G có 5 đỉnh A, B, C, D, E và các cạnh AB, BC, CD, DE, EA. Đồ thị này có đường đi Euler không? Tại sao?
Cho đồ thị G có 4 đỉnh A, B, C, D và các cạnh AB, BC, CD, DA, AC. Đồ thị này có đường đi Hamilton không? Tìm một đường đi Hamilton nếu có.

Kết luận

Bài học này đã giới thiệu những khái niệm cơ bản về đồ thị, đường đi Euler và đường đi Hamilton. Việc nắm vững những kiến thức này sẽ giúp bạn giải quyết các bài toán thực tế và mở rộng kiến thức trong lĩnh vực toán học rời rạc.