Bài 8: Khái niệm cơ bản của Lí thuyết đồ thị

I. Tóm tắt lý thuyết trọng tâm

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

Một đồ thị $G = (V, E)$ bao gồm:

Tập hợp $V$ các phần tử gọi là đỉnh (vertex).
Tập hợp $E$ các cặp phần tử của $V$ gọi là cạnh (edge).
Nếu các cặp trong $E$ có thứ tự, ta có đồ thị có hướng (với các cung), ngược lại là đồ thị vô hướng.

📋 2. Bậc của đỉnh

Bậc của đỉnh $v$ trong đồ thị vô hướng (kí hiệu $deg(v)$ ) là số cạnh nối với đỉnh đó.

Đỉnh có bậc lẻ gọi là đỉnh lẻ, bậc chẵn gọi là đỉnh chẵn.
Đỉnh bậc 0 gọi là đỉnh cô lập; đỉnh bậc 1 gọi là đỉnh treo.

⚡ 3. Định lí bắt tay

Trong một đồ thị bất kì, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh của nó:

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

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

II. Các dạng toán và ví dụ minh họa

📌 Kỹ năng phân tích đồ thị

Tính số cạnh/số đỉnh: Dùng định lí bắt tay.
Kiểm tra tính tồn tại: Sử dụng hệ quả về số đỉnh bậc lẻ (nếu tổng bậc lẻ hoặc số đỉnh lẻ là số lẻ thì không tồn tại đồ thị).
Phân biệt loại đồ thị:
- Đồ thị đơn: Không có vòng, không có cạnh song song.
- Đồ thị đa: Có cạnh song song.
- Đồ thị đầy đủ $K_n$ : Mỗi cặp đỉnh đều có cạnh nối (số cạnh là $n(n-1)/2$ ).

🔍 Ví dụ 1: Tính số cạnh

Một đồ thị có 10 đỉnh, trong đó có 4 đỉnh bậc 3 và 6 đỉnh bậc 4. Hỏi đồ thị này có bao nhiêu cạnh?

💡 Xem lời giải

Áp dụng định lí bắt tay:

Tổng bậc của 10 đỉnh là: $\sum deg(v) = 4 \times 3 + 6 \times 4 = 12 + 24 = 36$ .
Số cạnh của đồ thị là: $|E| = \text{Tổng bậc} / 2 = 36 / 2 = 18$ . Vậy đồ thị có 18 cạnh.

🔍 Ví dụ 2: Kiểm tra tính tồn tại của đồ thị

Có tồn tại đồ thị nào có 7 đỉnh mà bậc của các đỉnh lần lượt là 1, 2, 3, 4, 1, 3, 5 không?

💡 Xem lời giải

Đếm số đỉnh có bậc lẻ: 1, 3, 1, 3, 5 (có 5 đỉnh bậc lẻ).
Theo hệ quả định lí bắt tay, số lượng đỉnh bậc lẻ phải là một số chẵn.
Vì 5 là số lẻ nên không tồn tại đồ thị thỏa mãn yêu cầu.

🔍 Ví dụ 3: Đồ thị đầy đủ

Trong một giải bóng đá có 8 đội tham gia, thi đấu vòng tròn một lượt (mỗi đội gặp nhau đúng một lần). Hỏi có tổng cộng bao nhiêu trận đấu?

💡 Xem lời giải

Mỗi đội bóng coi như một đỉnh của đồ thị, mỗi trận đấu là một cạnh. Vì mỗi đội gặp đúng 1 lần nên đây là đồ thị đầy đủ $K_8$ . Số cạnh (trận đấu) là: $\frac{n(n-1)}{2} = \frac{8 \times 7}{2} = 28$ . Vậy có 28 trận đấu.

III. Trắc nghiệm ôn tập

Câu 1:Số lượng các đỉnh bậc lẻ trong một đồ thị bất kì luôn là:

Câu 2:Đồ thị đầy đủ $K_5$ có bao nhiêu cạnh?

Đúng / Sai

Câu 3Xét các khẳng định sau về đồ thị đơn:

a)Đồ thị đơn có thể chứa cạnh song song.

b)Bậc lớn nhất của một đỉnh trong đồ thị đơn n đỉnh là n-1.

c)Tổng bậc lẻ chứng minh đồ thị không tồn tại.

d)Đồ thị có 3 đỉnh, tổng bậc là 6 có thể là đồ thị đơn.

Câu 4:Một đồ thị có 15 cạnh. Tổng bậc của tất cả các đỉnh là bao nhiêu?

IV. Bài tập tự luận

📝 Bài tập tự luyện

Câu 1. Cho đồ thị đơn $G$ có $n$ đỉnh ( $n \geq 2$ ). Chứng minh rằng trong đồ thị luôn có ít nhất hai đỉnh có cùng bậc.

💡 Lời giải

Trong đồ thị đơn $n$ đỉnh, bậc của mỗi đỉnh thuộc tập $\{0, 1, 2, \dots, n-1\}$ .
Nếu đồ thị có đỉnh bậc 0 thì không thể có đỉnh bậc $n-1$ (vì đỉnh bậc $n-1$ phải kề với tất cả đỉnh khác).
Vậy tập giá trị bậc chỉ có thể là $\{0, 1, \dots, n-2\}$ hoặc $\{1, 2, \dots, n-1\}$ .
Cả hai tập đều có $n-1$ giá trị. Theo nguyên lí Dirichlet, $n$ đỉnh mà chỉ có $n-1$ giá trị bậc nên ít nhất 2 đỉnh trùng bậc.

Câu 2. Vẽ đồ thị đơn có 5 đỉnh $A, B, C, D, E$ and các cạnh là: $(A,B), (B,C), (C,D), (D,E), (E,A), (A,C)$ . Tính bậc của mỗi đỉnh.

💡 Lời giải

Đỉnh A nối với: B, E, C $\Rightarrow deg(A) = 3$ .
Đỉnh B nối với: A, C $\Rightarrow deg(B) = 2$ .
Đỉnh C nối với: B, D, A $\Rightarrow deg(C) = 3$ .
Đỉnh D nối with: C, E $\Rightarrow deg(D) = 2$ .
Đỉnh E nối with: D, A $\Rightarrow deg(E) = 2$ .

Câu 3. Cho đồ thị có 6 đỉnh, bậc của các đỉnh là $k, k, k, k, k, k$ . Tìm hằng số $k$ nhỏ nhất để đồ thị chắc chắn liên thông.

💡 Lời giải

Theo định lí về tính liên thông: Nếu $deg(v) \geq \frac{n-1}{2}$ với mọi $v$ thì đồ thị liên thông. Với $n=6$ , $(n-1)/2 = 2.5$ . Vậy $k \geq 3$ .

🎯

Luyện tập trắc nghiệm

Câu hỏi ngẫu nhiên từ ngân hàng đề — kiểm tra kiến thức ngay!

🚀 Làm bài trắc nghiệm →

Miễn phí · Không giới hạn lần làm