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 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 được sử dụng để mô hình hóa các mối quan hệ giữa các đối tượng. Trong toán học, đồ thị bao gồm các đỉnh (vertices) và các cạnh (edges) nối các đỉnh này lại với nhau.

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

• Đỉ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 đỉnh.
• Đồ 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).
• Đồ thị đơn (Simple Graph): Không có đa cạnh và vòng lặp.
• Đồ thị đa (Multigraph): Có thể có đa cạnh giữa hai đỉnh.
• Đồ thị có vòng lặp (Graph with Loops): Có cạnh nối một đỉnh với chính nó.

2. 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ó.

Ví dụ: Xét đồ thị vô hướng G có 4 đỉnh {A, B, C, D} và các cạnh {AB, BC, CD, DA}.

Ma trận kề của G:

3. Đường đi và chu trình trong đồ thị

Đường đi (Path): Một dãy các đỉnh liên tiếp nhau bằng 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.

Đường đi đơn (Simple Path): Một đường đi không lặp lại bất kỳ đỉnh nào.

Chu trình đơn (Simple Cycle): Một chu trình không lặp lại bất kỳ đỉnh nào (ngoại trừ đỉnh bắt đầu và kết thúc).

4. Các loại đồ thị đặc biệt

• Đồ thị đầy đủ (Complete Graph): Mọi cặp đỉnh đều được nối với nhau bằng một cạnh.
• Đồ thị hai phân (Bipartite Graph): Các đỉnh có thể được chia thành hai tập hợp 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): Một đồ thị liên thông không có chu trình.

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

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

• Mạng xã hội: Mô hình hóa các mối quan hệ giữa người dùng.
• Mạng máy tính: Mô hình hóa cấu trúc mạng.
• Giao thông vận tải: Mô hình hóa các tuyến đường và các điểm dừng.
• Lập kế hoạch: Tìm đường đi ngắn nhất hoặc hiệu quả nhất.

Hy vọng chuyên đề này sẽ giúp bạn hiểu rõ hơn về lí thuyết đồ thị và ứng dụng của nó trong toán học và các lĩnh vực khác. Hãy luyện tập thêm nhiều bài tập để củng cố kiến thức nhé!