Chuyên đề 2. Lí thuyết đồ thị

Chuyên đề 2: Lí thuyết đồ thị - Toán 11 Chân trời sáng tạo

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. Trong chương trình Toán 11 Chân trời sáng tạo, chuyên đề này giúp học sinh làm quen với các khái niệm cơ bản về đồ thị, các loại đồ thị, và các bài toán liên quan.

1. Khái niệm cơ bản về đồ thị

Đồ thị là một cấu trúc toán học bao gồm tập hợp các đỉnh (vertices) và tập hợp các cạnh (edges) nối giữa các đỉnh. Đỉnh biểu diễn các đối tượng, còn cạnh biểu diễn mối quan hệ giữa các đối tượng đó.

• Đỉnh (Vertex): Điểm đại diện cho một đối tượng.
• Cạnh (Edge): Đường nối giữa hai đỉnh, biểu diễn 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à mối quan hệ giữa hai đỉnh là tương đương.
• Đồ thị có hướng (Directed Graph): Cạnh có hướng, tức là mối quan hệ giữa hai đỉnh là không đối xứng.
• Độ bậc của đỉnh (Degree of a Vertex): Số lượng cạnh kề với một đỉnh.

2. Các loại đồ thị thường gặp

Có nhiều loại đồ thị khác nhau, mỗi loại có đặc điểm và ứng dụng riêng:

• Đồ thị đầy đủ (Complete Graph): Mỗi đỉnh được nối với tất cả các đỉnh còn lại.
• Đồ thị hai phân (Bipartite Graph): Tập hợp các đỉnh có thể được chia thành hai tập hợp rời nhau sao cho mọi cạnh đều nối một đỉnh từ tập hợp này với một đỉnh từ tập hợp kia.
• Đồ thị cây (Tree): Đồ thị liên thông không chứa chu trình.
• Đồ thị đường đi (Path Graph): Một chuỗi các đỉnh liên tiếp nhau.
• Đồ thị chu trình (Cycle Graph): Một chuỗi các đỉnh liên tiếp nhau tạo thành một vòng kín.

3. Biểu diễn đồ thị

Có hai cách phổ biến để biểu diễn đồ thị:

• Ma trận kề (Adjacency Matrix): Một ma trận vuông, trong đó phần tử a_ij bằng 1 nếu có cạnh nối giữa đỉnh i và đỉnh j, và bằng 0 nếu không có.
• Danh sách kề (Adjacency List): Mỗi đỉnh được liên kết với một danh sách các đỉnh kề với nó.

4. Bài toán về đồ thị

Có nhiều bài toán liên quan đến đồ thị, ví dụ:

• Bài toán đường đi ngắn nhất (Shortest Path Problem): Tìm đường đi ngắn nhất giữa hai đỉnh cho trước.
• Bài toán cây khung nhỏ nhất (Minimum Spanning Tree Problem): Tìm cây khung có tổng trọng số cạnh nhỏ nhất.
• Bài toán duyệt đồ thị (Graph Traversal): Duyệt tất cả các đỉnh của đồ thị theo một thứ tự nhất định.

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

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

• Mạng xã hội: Biểu diễn mối quan hệ giữa các người dùng.
• Mạng máy tính: Biểu diễn cấu trúc mạng.
• Giao thông vận tải: Biểu diễn mạng lưới đường xá.
• Lập kế hoạch: Tìm đường đi tối ưu.

6. Bài tập ví dụ minh họa

Bài tập 1: Cho đồ thị G có 5 đỉnh A, B, C, D, E và các cạnh AB, AC, BD, CE, DE. Hãy vẽ đồ thị G và xác định độ bậc của mỗi đỉnh.

Bài tập 2: Cho đồ thị G có ma trận kề sau:

Hãy vẽ đồ thị G và xác định các cạnh của đồ thị.

Kết luận: Chuyên đề 2 về Lí thuyết đồ thị trong chương trình Toán 11 Chân trời sáng tạo là nền tảng quan trọng để hiểu và giải quyết các bài toán thực tế. Việc nắm vững các khái niệm cơ bản, các loại đồ thị, và các bài toán liên quan sẽ giúp bạn tự tin hơn trong học tập và nghiên cứu.