Bài 8. Một vài khái niệm cơ bản

Bài 8: Một vài khái niệm cơ bản - Chuyên đề 2: Làm quen với một vài khái niệm của lí thuyết đồ thị (Toán 11 Kết nối tri thức)

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 các đỉnh này lại với nhau.

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

Một đồ thị (graph) 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.

• V: Tập hợp các đỉnh (vertices).
• E: Tập hợp các cạnh (edges).

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à nếu có cạnh nối đỉnh A và B, thì cũng có cạnh nối đỉnh B và A.
• Đồ thị có hướng (Directed graph): Các cạnh có hướng, tức là cạnh nối từ đỉnh A đến đỉnh B khác với cạnh nối từ đỉnh B đến đỉnh A. Cạnh có hướng được gọi là cung.
• Đồ 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. Bậc của đỉnh

Bậc của một đỉnh trong đồ thị vô hướng là số lượng cạnh nối với đỉnh đó. Trong đồ thị có hướng, có hai khái niệm bậc:

• Bậc vào (In-degree): Số lượng cung kết thúc tại đỉnh đó.
• Bậc ra (Out-degree): Số lượng cung bắt đầu từ đỉnh đó.

4. Ví dụ minh họa

Xét đồ thị vô hướng G = (V, E) với V = {A, B, C, D} và E = {{A, B}, {A, C}, {B, C}, {C, D}}.

• Bậc của đỉnh A là 2.
• Bậc của đỉnh B là 2.
• Bậc của đỉnh C là 3.
• Bậc của đỉnh D là 1.

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: Mô hình hóa mạng lưới đường xá.
• Lập kế hoạch: Tìm đường đi ngắn nhất giữa hai điểm.

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

Bài 1: Vẽ một đồ thị vô hướng có 5 đỉnh và 6 cạnh. Xác định bậc của mỗi đỉnh.

Bài 2: Vẽ một đồ thị có hướng có 4 đỉnh và 5 cung. Xác định bậc vào và bậc ra của mỗi đỉnh.

Hy vọng bài học này đã giúp các em nắm vững những khái niệm cơ bản về lí thuyết đồ thị. Chúc các em học tập tốt!