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

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 chuyên đề này, chúng ta sẽ bắt đầu làm quen với những khái niệm cơ bản nhất của lí thuyết đồ thị.

1. Định nghĩa đồ thị

Một đồ thị G = (V, E) bao gồm một tập hợp hữu hạn các đỉnh V và một tập hợp các cạnh E, trong đó mỗi cạnh nối hai đỉnh trong V.

• Đỉnh (Vertex): Đại diện cho một đối tượng.
• Cạnh (Edge): Đại diện cho mối quan hệ giữa hai đối tượng.

2. Các loại đồ thị

Có nhiều loại đồ thị khác nhau, tùy thuộc vào tính chất của các cạnh:

• Đồ thị vô hướng (Undirected Graph): Các 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ác cạnh có hướng, tức là mối quan hệ giữa hai đỉnh không nhất thiết là tương đương.
• Đồ thị đa đồ thị (Multigraph): Cho phép có nhiều cạnh nối giữa hai đỉnh.
• Đồ thị đơn (Simple Graph): Không có cạnh lặp và không có vòng lặp (cạnh nối một đỉnh với chính 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.
• 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ụ về ma trận kề:

Trong ví dụ trên, đồ thị có 3 đỉnh A, B, C. Cạnh nối A và B, cạnh nối B và C.

4. Các khái niệm liên quan

• Bậc của đỉnh (Degree of a Vertex): Số lượng cạnh nối 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.
• Liên thông (Connectivity): Một đồ thị được gọi là liên thông nếu có một đường đi giữa bất kỳ hai đỉnh nào trong đồ thị.

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 lưới giao thông: Mô hình hóa các tuyến đường và các điểm giao thông.
• Khoa học máy tính: Thiết kế thuật toán, phân tích dữ liệu.
• 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ị. Trong các chuyên đề tiếp theo, chúng ta sẽ đi sâu hơn vào các khái niệm và ứng dụng của lí thuyết đồ thị.