Chuyên đề 2: Làm quen với một vài khái niệm của lí thuyết đồ thị

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 đượ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ị 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.

Ví dụ: Một đồ thị có 4 đỉnh {A, B, C, D} và các cạnh {(A, B), (B, C), (C, D), (D, A)}.

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

1. Đồ thị vô hướng (Undirected Graph): Các cạnh không có hướng, tức là cạnh (A, B) tương đương với cạnh (B, A).
2. Đồ thị có hướng (Directed Graph): Các cạnh có hướng, tức là cạnh (A, B) khác với cạnh (B, A). Cạnh (A, B) biểu thị một đường đi từ A đến B.
3. Đồ thị đa đồ thị (Multigraph): Cho phép nhiều cạnh nối giữa hai đỉnh.
4. Đồ 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. Các khái niệm liên quan

3.1 Bậc của Đỉnh

Bậc của một đỉnh là số lượng cạnh nối với đỉnh đó. Trong đồ thị vô hướng, bậc của đỉnh A được ký hiệu là deg(A). Trong đồ thị có hướng, có bậc vào (in-degree) và bậc ra (out-degree).

3.2 Đường đi và Chu trình

Một đường đi (path) là một dãy các đỉnh liên tiếp nhau bởi các cạnh. Một chu trình (cycle) là một đường đi bắt đầu và kết thúc tại cùng một đỉnh.

3.3 Đồ thị Liên thông

Một đồ thị được gọi là liên thông nếu giữa bất kỳ hai đỉnh nào cũng có ít nhất một đường đi.

4. 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 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ó.

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:

• 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 các tuyến đường và các điểm dừng.
• Sinh học: Mô hình hóa các tương tác giữa các gen và protein.

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

Để củng cố kiến thức, các em hãy thực hành giải các bài tập sau:

1. Vẽ một đồ thị vô hướng có 5 đỉnh và 6 cạnh.
2. Xác định bậc của mỗi đỉnh trong đồ thị vừa vẽ.
3. Tìm một đường đi từ đỉnh A đến đỉnh E trong đồ thị.

Hy vọng chuyên đề này sẽ giúp các em hiểu rõ hơn về những khái niệm cơ bản của Lí thuyết Đồ thị. Chúc các em học tập tốt!