Chuyên đề II. Làm quen với một vài yếu tố của lí thuyết đồ thị

Chuyên đề II: Làm quen với một vài yếu tố của lí thuyết đồ thị - Toán 11 Cánh Diều

1. Giới thiệu chung về Lí thuyết Đồ thị

Lí thuyết đồ thị là một nhánh của toán học rời rạc, nghiên cứu về các đồ thị. Đồ thị là một cấu trúc toán học dùng để mô hình hóa các mối quan hệ giữa các đối tượng. Nó bao gồm các đỉnh (vertices) và các cạnh (edges) nối giữa các đỉnh. Lí thuyết đồ thị có ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học máy tính, mạng máy tính, giao thông vận tải, sinh học, hóa học và nhiều lĩnh vực khác.

2. Các khái niệm cơ bản

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

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

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

1. 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 giữa đỉnh i và đỉnh j, và bằng 0 nếu không.
2. 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. Ví dụ minh họa

Xét một đồ thị vô hướng có 5 đỉnh A, B, C, D, E và các cạnh sau: (A, B), (A, C), (B, C), (B, D), (C, E).

4.1. Biểu diễn bằng ma trận kề:

4.2. Biểu diễn bằng danh sách kề:

• A: B, C
• B: A, C, D
• C: A, B, E
• D: B
• E: C

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

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

• Mạng máy tính: Mô hình hóa cấu trúc mạng, tìm đường đi ngắn nhất giữa các máy tính.
• Giao thông vận tải: Tìm đường đi ngắn nhất giữa các thành phố, tối ưu hóa lịch trình giao thông.
• Mạng xã hội: Phân tích mối quan hệ giữa các người dùng, đề xuất bạn bè.
• Sinh học: Mô hình hóa tương tác giữa các gen, protein.
• Hóa học: Biểu diễn cấu trúc phân tử.

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

Hãy vẽ một đồ thị vô hướng có 6 đỉnh và các cạnh sau: (A, B), (A, D), (B, C), (C, D), (D, E), (E, F). Sau đó, biểu diễn đồ thị này bằng ma trận kề và danh sách kề.

Chuyên đề này là nền tảng quan trọng để các em tiếp cận các kiến thức nâng cao hơn về lí thuyết đồ thị trong các chương trình học tiếp theo. Chúc các em học tập tốt!