Chuyên đề học tập Toán 11

Giải Bài 2.20 trang 50 Chuyên đề Toán 11

Bài tập cuối chuyên đề 2   Đã kiểm chéo

Đề bài

Vẽ đồ thị G=(V,E)G = (V, E) với các đỉnh và các cạnh như sau:

V={1;2;3;4;5;6;7;8}V = \{1; 2; 3; 4; 5; 6; 7; 8\} và E={12;13;23;34;35;67;68;78}E = \{12; 13; 23; 34; 35; 67; 68; 78\}.

Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Lời giải

Vẽ đồ thị. Đồ thị G=(V,E)G=(V,E) có 88 đỉnh 1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 và 88 cạnh: 12, 13, 23, 34, 35, 67, 68, 7812,\ 13,\ 23,\ 34,\ 35,\ 67,\ 68,\ 78. Ta thấy các đỉnh 1,2,3,4,51,2,3,4,5 nối với nhau tạo thành một phần, còn các đỉnh 6,7,86,7,8 nối với nhau thành một tam giác tách biệt:

- Đỉnh 11 nối với 22 và 33.
- Đỉnh 22 nối với 11 và 33.
- Đỉnh 33 nối với 1, 2, 4, 51,\ 2,\ 4,\ 5.
- Đỉnh 44 nối với 33.
- Đỉnh 55 nối với 33.
- Các đỉnh 6, 7, 86,\ 7,\ 8 nối với nhau từng đôi một (tam giác 678678).

(Đồ thị gồm hai bộ phận rời nhau: một phần chứa các đỉnh 1,2,3,4,51,2,3,4,5 và một tam giác chứa các đỉnh 6,7,86,7,8.)

a) GG có phải là đơn đồ thị không?

Đơn đồ thị là đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh bội (không có hai cạnh cùng nối một cặp đỉnh).

Xét tập cạnh E={12,13,23,34,35,67,68,78}E=\{12,13,23,34,35,67,68,78\}:
- Mỗi cạnh đều nối hai đỉnh phân biệt nên không có khuyên.
- Không có cặp đỉnh nào được nối bởi quá một cạnh nên không có cạnh bội.

Vậy GG là một đơn đồ thị.

b) GG có phải là đồ thị đầy đủ không?

Đồ thị đầy đủ nn đỉnh là đồ thị trong đó hai đỉnh bất kì đều được nối với nhau bởi đúng một cạnh; số cạnh của nó là
(n2)=n(n−1)2.\binom{n}{2}=\dfrac{n(n-1)}{2}.
Với n=8n=8 ta có số cạnh cần có là 8⋅72=28\dfrac{8\cdot 7}{2}=28 cạnh.

Đồ thị GG chỉ có 88 cạnh <28<28, nên không thể là đồ thị đầy đủ. Hơn nữa, có thể chỉ ra ngay một cặp đỉnh không được nối với nhau, chẳng hạn đỉnh 11 và đỉnh 44 (hay đỉnh 11 và đỉnh 66) không có cạnh nối.

Vậy GG không phải là đồ thị đầy đủ.

Đáp số

Là đơn đồ thị (không có khuyên, không có cạnh bội)Không phải đồ thị đầy đủ (chỉ có 8 cạnh, trong khi đồ thị đầy đủ 8 đỉnh cần 28 cạnh; ví dụ đỉnh 1 và 4 không nối nhau)

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.