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 quan trọng 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 đồ 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.

• Đỉnh (vertex): Là các điểm đại diện cho các đối tượng trong bài toán.
• Cạnh (edge): Là đường nối giữa hai đỉnh, biểu thị 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à cạnh nối đỉnh A và đỉnh B cũng nối đỉnh B và đỉnh A.
• Đồ thị có hướng (directed graph): Các cạnh có hướng, tức là cạnh nối đỉnh A đến đỉnh B không nhất thiết nối đỉnh B đến đỉnh A. Cạnh này đượ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ị là số lượng cạnh kề với đỉnh đó. Trong đồ thị vô hướng, bậc của đỉnh là số 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ố cung kết thúc tại đỉnh đó.
• Bậc ra (out-degree): Số cung bắt đầu từ đỉnh đó.

4. Ví dụ minh họa

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

• Bậc của đỉnh A là 2 (nối với B và C).
• Bậc của đỉnh B là 2 (nối với A và C).
• Bậc của đỉnh C là 3 (nối với A, B và D).
• Bậc của đỉnh D là 1 (nối với C).

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

Lí thuyết đồ thị có rất nhiều ứng dụng trong các lĩnh vực khác nhau, bao gồm:

• Khoa học máy tính: Mô hình hóa mạng máy tính, thuật toán tìm đường đi ngắn nhất, phân tích mạng xã hội.
• Kỹ thuật: Thiết kế mạch điện, phân tích mạng lưới giao thông.
• Sinh học: Nghiên cứu tương tác giữa các protein, phân tích hệ gen.
• Xã hội học: Phân tích mạng lưới quan hệ xã hội.

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ị. Hãy luyện tập thêm các bài tập để hiểu sâu hơn về chủ đề này. Chúc các em học tốt!