Chuyên đề 2. Lí thuyết đồ thị

Chuyên đề 2: Lí thuyết đồ thị - Toán 11 Chân trời sáng tạo

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ị, bao gồm các đỉnh (vertices) và các cạnh (edges) kết nối các đỉnh này. Chuyên đề này trong chương trình Toán 11 Chân trời sáng tạo đóng vai trò nền tảng cho việc hiểu và giải quyết các bài toán liên quan đến mạng lưới, quan hệ và cấu trúc.

1. Định nghĩa và các khái niệm cơ bản

Một đồ thị (graph) G = (V, E) bao gồm một tập hợp các đỉnh V và một tập hợp các cạnh E. Mỗi cạnh nối hai đỉnh trong V. Đồ thị có thể là có hướng (directed graph) hoặc vô hướng (undirected graph). Trong đồ thị có hướng, các cạnh có một chiều xác định, còn trong đồ thị vô hướng, các cạnh không có chiều.

Đỉnh (vertex): Một điểm trong đồ thị.
Cạnh (edge): Một đường nối hai đỉnh.
Bậc của đỉnh: Số lượng cạnh kề với một đỉnh.
Đồ thị đầy đủ (complete graph): Một đồ thị mà mọi cặp đỉnh đều được nối với nhau bằng một cạnh.
Đồ thị hai phân (bipartite graph): Một đồ thị mà các đỉnh có thể được chia thành hai tập hợp không giao nhau, sao cho mọi cạnh đều nối một đỉnh từ tập hợp này với một đỉnh từ tập hợp kia.

2. 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 đỉnh i với đỉnh j, và bằng 0 nếu không.
Danh sách kề (adjacency list): Một danh sách, trong đó mỗi đỉnh được liên kết với một danh sách các đỉnh kề với nó.

Ví dụ, xét đồ thị vô hướng với các đỉnh A, B, C và các cạnh (A, B), (B, C).

	A	B	C
A	0	1	0
B	1	0	1
C	0	1	0

3. Đường đi và chu trì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.

Đường đi Euler (Eulerian path): Một đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.

Chu trình Euler (Eulerian cycle): Một chu trình đi qua tất cả các cạnh của đồ thị đúng một lần.

4. Các bài toán ứng dụng

Lí thuyết đồ thị có nhiều ứng dụng trong thực tế, bao gồm:

Mạng lưới giao thông: Mô hình hóa các đường phố và giao lộ để tìm đường đi ngắn nhất.
Mạng xã hội: Phân tích các mối quan hệ giữa người dùng.
Mạng máy tính: Thiết kế và quản lý mạng.
Lập lịch: Sắp xếp các công việc và tài nguyên.

5. Bài tập ví dụ

Bài tập 1: Cho đồ thị G = (V, E) với V = {A, B, C, D} và E = {(A, B), (B, C), (C, D), (D, A)}. Hãy tìm một chu trình Euler trong đồ thị này.

Bài tập 2: Cho đồ thị G = (V, E) với V = {A, B, C, D, E} và E = {(A, B), (B, C), (C, D), (D, E)}. Hãy tìm một đường đi Euler trong đồ thị này.

Hy vọng chuyên đề này đã cung cấp cho bạn những kiến thức cơ bản và hữu ích về lí thuyết đồ thị. Hãy luyện tập thêm nhiều bài tập để nắm vững kiến thức và áp dụng vào giải quyết các bài toán thực tế.