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
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. Nó 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. Định nghĩa cơ bản về đồ thị
Một đồ thị G = (V, E) bao gồm:
- V: Tập hợp các đỉnh (vertices)
- E: Tập hợp các cạnh (edges). Mỗi cạnh nối hai đỉnh.
Có hai loại cạnh chính:
- Cạnh không hướng (undirected edge): Cạnh nối hai đỉnh A và B không phân biệt thứ tự, ký hiệu là {A, B} hoặc (A, B).
- Cạnh có hướng (directed edge): Cạnh nối hai đỉnh A và B có thứ tự, ký hiệu là (A, B), nghĩa là cạnh đi từ A đến B.
2. Các loại đồ thị đặc biệt
Có nhiều loại đồ thị đặc biệt, mỗi loại có những tính chất riêng:
- Đồ thị vô hướng (undirected graph): Tất cả các cạnh đều là cạnh không hướng.
- Đồ thị có hướng (directed graph): Tất cả các cạnh đều là cạnh có hướng.
- Đồ thị đơn (simple graph): Không có cạnh lặp (hai cạnh nối cùng hai đỉnh) và không có vòng lặp (cạnh nối một đỉnh với chính nó).
- Đồ thị đa (multigraph): Cho phép có cạnh lặp.
- Đồ thị hoàn chỉnh (complete graph): Mỗi đỉnh đều được nối với tất cả các đỉnh còn lại.
- Đồ thị cây (tree): Đồ thị liên thông không có chu trình.
3. Các khái niệm liên quan đến đỉnh và cạnh
Một số khái niệm quan trọng liên quan đến đỉnh và cạ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.
- Đường đi Euler (Eulerian path): Đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.
- Chu trình Euler (Eulerian cycle): Chu trình đi qua tất cả các cạnh của đồ thị đúng một lần.
- Đường đi Hamilton (Hamiltonian path): Đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.
- Chu trình Hamilton (Hamiltonian cycle): Chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần.
4. Ma trận kề và danh sách kề
Có hai cách phổ biến để biểu diễn đồ thị trong máy tính:
- Ma trận kề (adjacency matrix): Một ma trận vuông, trong đó phần tử aij bằng 1 nếu có cạnh nối đỉnh i và đỉnh j, và bằng 0 nếu không.
- 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ó.
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ế, 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: Tìm đường đi ngắn nhất giữa hai địa điểm.
- Lập kế hoạch: Tối ưu hóa lịch trình và phân bổ nguồn lực.
- Sinh học: Nghiên cứu các tương tác giữa các gen và protein.
Chuyên đề này chỉ là bước đầu làm quen với lí thuyết đồ thị. Để hiểu sâu hơn, bạn cần thực hành giải nhiều bài tập và tìm hiểu thêm về các thuật toán liên quan đến đồ thị.
