Chuyên đề II. Làm quen với một vài yếu tố của 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 đượ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 V các đỉnh (vertices) và một tập hợp E các cạnh (edges). 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.

Ví dụ: Một mạng xã hội có thể được mô hình hóa bằng một đồ thị, trong đó mỗi người dùng là một đỉnh và mỗi mối quan hệ bạn bè là một cạnh.

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

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

• Đồ 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à hai chiều.
• Đồ thị có hướng (Directed Graph): Các cạnh có hướng, tức là mối quan hệ giữa hai đỉnh là một chiều.
• Đồ thị đa đồ thị (Multigraph): Có thể 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ề cho đồ thị có 4 đỉnh:

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 đỉnh đó.
• Đườ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.
• Đồ thị liên thông (Connected Graph): Một đồ thị trong đó có đường đi giữa bất kỳ hai đỉnh nào.

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ệ bạn bè.
• Mạng lưới giao thông: Mô hình hóa các tuyến đường và các giao lộ.
• Mạng máy tính: Mô hình hóa các kết nối giữa các máy tính.
• Lập kế hoạch: Tìm đường đi ngắn nhất hoặc hiệu quả nhất.
• Phân tích dữ liệu: Tìm các mẫu và mối quan hệ trong dữ liệu.

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à thuật toán phức tạp hơn. Hy vọng rằng, với những kiến thức cơ bản này, các em sẽ có một nền tảng vững chắc để học tập và nghiên cứu về lí thuyết đồ thị.