ly thuyet do thi

© Được viết bởi CaolacVC. Blog https://caolacvc.blogspot.com

LÝ THUYẾT ĐỒ THỊ - CHUYÊN ĐỀ TOÁN 11 KẾT NỐI TRI THỨC

1. Các Khái Niệm Cơ Bản

Đồ thị (Graph): Là một cặp $G = (V, E)$, trong đó:

• $V$ là tập hợp các đỉnh (vertices), $V \ne \emptyset$.
• $E$ là tập hợp các cạnh (edges), mỗi cạnh nối hai đỉnh thuộc $V$.

Bậc của đỉnh (Degree): Bậc của đỉnh $v$ trong đồ thị $G$, kí hiệu $deg(v)$, là số cạnh liên thuộc với $v$ (số cạnh nhận $v$ làm đầu mút).

Định lý bắt tay: Tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị đó.

$$ \sum_{v \in V} deg(v) = 2|E| $$

Hệ quả: Trong mọi đồ thị, số đỉnh bậc lẻ luôn là một số chẵn.

Ví dụ 1: Cho đồ thị $G$ có 5 đỉnh. Biết bậc của các đỉnh lần lượt là 2, 3, 2, 4, 3. Tính số cạnh của đồ thị $G$.

Lời giải:

Theo định lý bắt tay, tổng bậc của các đỉnh bằng 2 lần số cạnh ($2|E|$).

Tổng bậc = $2 + 3 + 2 + 4 + 3 = 14$.

Suy ra $2|E| = 14 \Rightarrow |E| = 7$.

Vậy đồ thị có 7 cạnh.

2. Đường Đi và Chu Trình

• Đường đi (Path): Là một dãy các đỉnh và cạnh nối tiếp nhau: $v_0, e_1, v_1, ..., e_k, v_k$. (Thường viết gọn là $v_0 v_1 ... v_k$).
• Chu trình (Cycle): Là một đường đi khép kín (đỉnh đầu trùng đỉnh cuối: $v_0 = v_k$) và có ít nhất 3 cạnh.
• Đồ thị liên thông: Đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kì luôn có ít nhất một đường đi nối chúng.

3. Đồ Thị Euler

Chu trình Euler: Là chu trình đi qua mỗi cạnh của đồ thị đúng một lần.

Đường đi Euler: Là đường đi qua mỗi cạnh của đồ thị đúng một lần.

Đồ thị Euler: Là đồ thị có chứa chu trình Euler.

Điều kiện tồn tại: Cho đồ thị liên thông $G$.

• $G$ có chu trình Euler $\Leftrightarrow$ Mọi đỉnh của $G$ đều có bậc chẵn.
• $G$ có đường đi Euler (nhưng không có chu trình Euler) $\Leftrightarrow$ $G$ có đúng 2 đỉnh bậc lẻ.

Ví dụ 2: Trong các đồ thị sau, đồ thị nào vẽ được bằng một nét liền (không nhấc bút, không tô lại cạnh đã vẽ)?

a) Đồ thị $K_4$ (Đồ thị đầy đủ 4 đỉnh).

b) Hình ngôi sao 5 cánh.

Lời giải:

Vẽ được bằng một nét liền tương đương với việc đồ thị có đường đi Euler hoặc chu trình Euler.

a) $K_4$ có 4 đỉnh, mỗi đỉnh nối với 3 đỉnh còn lại nên bậc của mỗi đỉnh đều là 3 (bậc lẻ).

Số đỉnh bậc lẻ là 4 > 2 $\Rightarrow$ Không có đường đi Euler. $\Rightarrow$ Không vẽ được bằng một nét.

---

b) Hình ngôi sao 5 cánh có 5 đỉnh ở ngoài và 5 giao điểm ở trong (nếu coi giao điểm là đỉnh). Tuy nhiên, xét ngôi sao đơn giản (chỉ có 5 đỉnh, các cạnh cắt nhau không tạo đỉnh mới): Mỗi đỉnh có bậc 2. Tất cả đỉnh bậc chẵn $\Rightarrow$ Có chu trình Euler. $\Rightarrow$ Vẽ được bằng một nét.

4. Đồ Thị Hamilton

Chu trình Hamilton: Là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần (trừ đỉnh đầu trùng đỉnh cuối).

Đường đi Hamilton: Là đường đi qua mỗi đỉnh của đồ thị đúng một lần.

Lưu ý: Chưa có điều kiện cần và đủ đơn giản để kiểm tra đồ thị có chu trình Hamilton hay không. Tuy nhiên, có một số định lý điều kiện đủ (như Định lý Dirac, Định lý Ore).

5. Bài Tập Tự Luyện

Bài 1: Có 7 người trong một bữa tiệc. Chứng minh rằng luôn tồn tại 2 người có cùng số người quen trong bữa tiệc đó (giả sử quan hệ quen biết là hai chiều).

Lời giải:

Xem mỗi người là một đỉnh của đồ thị, quan hệ quen biết là cạnh nối 2 đỉnh.

Số người quen của một người chính là bậc của đỉnh đó.

Trong đồ thị 7 đỉnh, bậc của mỗi đỉnh có thể nhận các giá trị từ 0 đến 6.

Tuy nhiên, không thể đồng thời có đỉnh bậc 0 (không quen ai) và đỉnh bậc 6 (quen tất cả mọi người còn lại). Vì nếu A quen tất cả, thì ai cũng quen A, nên không có ai bậc 0.

Vậy các giá trị bậc có thể có là $\{0, 1, ..., 5\}$ hoặc $\{1, 2, ..., 6\}$. Cả hai tập đều có 6 giá trị.

Theo nguyên lý Dirichlet, có 7 đỉnh mà chỉ có 6 giá trị bậc khả dĩ $\Rightarrow$ Tồn tại ít nhất 2 đỉnh có cùng bậc.

Tức là có ít nhất 2 người có cùng số người quen.

---

Bài 2: Tìm đường đi Euler cho đồ thị có các đỉnh $\{A, B, C, D, E\}$ và các cạnh: $AB, BC, CD, DE, EA, AC, CE, EB, BD, DA$ (Đồ thị $K_5$).

Lời giải:

Đồ thị $K_5$ (đầy đủ 5 đỉnh): Mỗi đỉnh đều nối với 4 đỉnh còn lại.

Bậc của mỗi đỉnh là 4 (chẵn).

$\Rightarrow$ Đồ thị có chu trình Euler.

Một chu trình Euler ví dụ: $A \to B \to C \to D \to E \to A \to C \to E \to B \to D \to A$.

---

Bài 3: Xác định số màu tối thiểu để tô các đỉnh của đồ thị chu trình $C_5$ (5 đỉnh tạo thành vòng tròn) sao cho hai đỉnh kề nhau không cùng màu.

Lời giải:

Xét chu trình $v_1 - v_2 - v_3 - v_4 - v_5 - v_1$.

Giả sử dùng 2 màu Xanh (X) và Đỏ (Đ).

$v_1(X) \to v_2(Đ) \to v_3(X) \to v_4(Đ) \to v_5(X)$.

Khi đó $v_5$ kề $v_1$ và cả hai đều màu Xanh (vô lý).

Vậy cần ít nhất 3 màu.

Cách tô 3 màu: $v_1(1), v_2(2), v_3(1), v_4(2), v_5(3)$. (Thỏa mãn).

Vậy sắc số chi phương $\chi(C_5) = 3$.

6. Bài Toán Thực Tế

Bài toán 1 (Bài toán người đưa thư): Một người đưa thư muốn đi qua tất cả các con đường trong khu phố và quay về điểm xuất phát. Hãy mô hình hóa bài toán này bằng lý thuyết đồ thị.

Lời giải:

Coi các giao lộ (ngã ba, ngã tư) là các đỉnh.

Coi các con đường nối các giao lộ là các cạnh.

Yêu cầu "đi qua tất cả các con đường và quay về điểm xuất phát" tương ứng với việc tìm chu trình Euler trong đồ thị.

Nếu đồ thị có tất cả các đỉnh bậc chẵn, người đưa thư có thể thực hiện hành trình đi qua mỗi con đường đúng một lần.

Nếu có đỉnh bậc lẻ, người đưa thư buộc phải đi lại một số con đường.

Bài toán 2 (Lập lịch thi): Có 6 môn thi cần xếp lịch. Một số sinh viên đăng ký thi cả hai môn. Danh sách các cặp môn có chung sinh viên đăng ký là: (Toán, Lý), (Toán, Anh), (Lý, Hóa), (Hóa, Sinh), (Sinh, Sử), (Sử, Anh), (Toán, Hóa). Hỏi cần ít nhất bao nhiêu ca thi để không sinh viên nào bị trùng lịch?

Lời giải:

Mô hình hóa: Mỗi môn thi là một đỉnh. Hai đỉnh nối với nhau nếu có chung sinh viên (không thể thi cùng ca).

Bài toán trở thành: Tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau khác màu. Số màu ít nhất chính là số ca thi tối thiểu.

Các cạnh: T-L, T-A, L-H, H-Si, Si-Sử, Sử-A, T-H.

Xét đồ thị:

• T nối với L, A, H.
• H nối với L, Si, T.
• ...

Ta thấy vòng tròn: T - L - H - T tạo thành tam giác (chu trình $C_3$). Cần ít nhất 3 màu cho 3 môn này.

Thử tô màu:

• Ca 1: Toán, Sinh (Không kề nhau).
• Ca 2: Lý, Sử (Không kề nhau).
• Ca 3: Anh, Hóa (Không kề nhau).

Kiểm tra các cạnh còn lại: T-L (1-2 ok), T-A (1-3 ok), L-H (2-3 ok), H-Si (3-1 ok), Si-Sử (1-2 ok), Sử-A (2-3 ok), T-H (1-3 ok).

Vậy có thể xếp lịch trong 3 ca thi.

Nguồn: caolacvc.blogspot.com
Tác giả: Nguyễn Hoàng Thứ