Bài Tập Trắc Nghiệm Chuyên Đề: Chuyên đề: lí thuyết đồ thị (Toán học Lớp 11)

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh và thời gian (phút): $AB=17$, $AE=8$, $AD=20$, $BE=29$, $BC=12$, $CE=19$, $CD=10$, $ED=9$. Cần tìm chu trình Hamilton xuất phát từ $A$ đi qua $B$, $C$, $D$, $E$ mỗi xã đúng một lần rồi quay về $A$ với tổng thời gian nhỏ nhất. Liệt kê các chu trình (không phân biệt hai chiều): $A\to B\to C\to D\to E\to A$: $17+12+10+9+8=56$ phút. $A\to B\to C\to E\to D\to A$: $17+12+19+9+20=77$ phút. $A\to B\to E\to D\to C\to A$: $17+29+9+10+12=77$ phút. $A\to B\to E\to C\to D\to A$: $17+29+19+10+20=95$ phút. $A\to C\to B\to E\to D\to A$: $12+12+29+9+20=82$ phút. $A\to C\to D\to E\to B\to A$: $12+10+9+29+17=77$ phút. $A\to C\to E\to D\to B\to A$: $12+19+9+29+17=86$ phút. $A\to D\to E\to B\to C\to A$: $20+9+29+12+12=82$ phút. $A\to D\to C\to B\to E\to A$: $20+10+12+29+8=79$ phút. $A\to D\to C\to E\to B\to A$: $20+10+19+29+8=86$ phút. $A\to D\to E\to C\to B\to A$: $20+9+19+12+17=77$ phút. $A\to E\to B\to C\to D\to A$: $8+29+12+10+20=79$ phút. Vậy chu trình ngắn nhất là $A\to B\to C\to D\to E\to A$ (và chiều ngược lại) với tổng thời gian $56$ phút $=56/60$ giờ. Chi phí thuê xe nhỏ nhất: $750000\times 56/60=700000$ đồng $=700$ nghìn đồng. Kết quả khớp với đáp án nguồn (700).

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh và thời gian (phút): $AB=17$, $AE=8$, $AD=20$, $BE=29$, $BC=12$, $CE=19$, $CD=10$, $ED=9$. Lưu ý không có cạnh nối trực tiếp $A$ với $C$. Cần tìm chu trình Hamilton xuất phát từ $A$, qua $B,C,D,E$ mỗi xã đúng một lần rồi về $A$ với tổng thời gian nhỏ nhất. Xét các chu trình khả dĩ (không dùng cạnh $AC$ vì không tồn tại):
- $A\to B\to C\to D\to E\to A$: $17+12+10+9+8=56$;
- $A\to B\to C\to E\to D\to A$: $17+12+19+9+20=77$;
- $A\to B\to D\to C\to E\to A$: $17+10+10+19+8=64$;
- $A\to B\to D\to E\to C\to A$: $17+10+9+19+12=67$;
- $A\to B\to E\to C\to D\to A$: $17+29+19+10+20=95$;
- $A\to B\to E\to D\to C\to A$: $17+29+9+10+12=77$;
- $A\to D\to B\to C\to E\to A$: $20+10+12+19+8=69$;
- $A\to D\to B\to E\to C\to A$: $20+10+29+19+12=90$;
- $A\to D\to C\to B\to E\to A$: $20+10+12+29+8=79$;
- $A\to D\to E\to B\to C\to A$: $20+9+29+12+12=82$;
- $A\to D\to E\to C\to B\to A$: $20+9+19+12+17=77$;
- $A\to E\to B\to C\to D\to A$: $8+29+12+10+20=79$.

Chu trình ngắn nhất là $A\to B\to C\to D\to E\to A$ với tổng thời gian $56$ phút $=\frac{56}{60}$ giờ. Chi phí thuê xe thấp nhất: $750000\times \frac{56}{60}=700000$ đồng $=700$ nghìn đồng. Kết quả khớp với đáp án nguồn ($700$).

(AI giải đề cho tôi)
Đây là bài toán người đưa thư Trung Hoa (Chinese Postman) trên đồ thị vô hướng. Các cạnh của hình vẽ: $AB=8$, $BC=12$, $CD=8$, $AD=12$ (vì $ABCD$ là hình chữ nhật), $AF=FD=6$ ($F$ là trung điểm $AD$), $AE=8$, $ED=10$, $BF=8$, $BG=8$, $CF=8$, $CG=8$. Tổng độ dài tất cả các cạnh: $8+12+8+12+6+6+8+10+8+8+8+8=102$. Xét bậc của từng đỉnh: $A$ nối với $B,D,F,E$ → bậc 4; $B$ nối với $A,C,F,G$ → bậc 4; $C$ nối với $B,D,F,G$ → bậc 4; $D$ nối với $A,C,F,E$ → bậc 4; $E$ nối với $A,D$ → bậc 2; $F$ nối với $A,D,B,C$ → bậc 4; $G$ nối với $B,C$ → bậc 2. Mọi đỉnh đều có bậc chẵn nên đồ thị có chu trình Euler: tồn tại đường đi khép kín đi qua mỗi cạnh đúng một lần. Vậy tổng độ dài đường đi ngắn nhất bằng tổng độ dài các cạnh, tức $102$.

(AI giải đề cho tôi)
Tổng độ dài các cạnh: $AB=200,BC=700,CD=400,BD=900,BE=800,AE=700,ED=1000,EF=900,FA=1000$, tổng $=6600$ m. Bậc các đỉnh: $A:3$, $B:4$, $C:2$, $D:3$, $E:4$, $F:2$. Chỉ có hai đỉnh bậc lẻ là $A$ và $D$, nên theo bài toán người đưa thư (Chinese Postman) phải lặp lại đường đi ngắn nhất từ $A$ đến $D$. Các phương án: $A\to B\to D=200+900=1100$; $A\to B\to C\to D=1300$; $A\to E\to D=700+1000=1700$; $A\to B\to E\to D=1900$; $A\to E\to B\to D=2400$. Ngắn nhất là $1100$ m. Đáp số: $6600+1100=7700$ m.

Ta coi như đây là hình chóp E.ABCD, khi xuất phát từ A và kết thúc tại A thì tương đương với việc bắt đầu từ một điểm thuộc đáy và trong quá trình di chuyển phải đi qua đỉnh hình chóp. Nên ta sẽ luôn bỏ qua một cạnh đáy và hai cạnh bên đối diện với cạnh đáy đó. Ví dụ: chu trình ABCDEA thì ta bỏ qua AD và BE với BC. Suy ra để thời gian di chuyển ngắn nhất thì lấy tổng thời gian đi trừ đi thời gian đi ba cạnh trên. Mà có 4 cạnh đáy nên xét 4 trường hợp (AD; BE; CE), (AB; DE; CE) …. Tổng thời gian di chuyển trên tất cả các cạnh của sơ đồ là $16+7+18+23+13+15+12+8=112$ phút. Trong các trường hợp trên thì trường hợp bỏ (AD; BE; CE) có tổng thời gian ba cạnh bị bỏ lớn nhất: $18+23+15=56$ phút, nên thời gian di chuyển ít nhất là $112-56=56$ phút. Cộng thêm thời gian giao hàng tại 4 địa điểm $B,C,D,E$: $4\times 5=20$ phút. Vậy thời gian ít nhất để anh Hà hoàn thành công việc là $56+20=76$ phút.

Lưu ý: lời giải gốc trong tài liệu kết luận 56 phút nhưng đã quên cộng thời gian giao hàng (20 phút), nên đáp án đúng theo tính toán đầy đủ là 76 phút (B).

(AI giải đề cho tôi)
Từ sơ đồ, các cạnh có: AB=16, AE=7, AD=18, BE=23, BC=13, CE=15, CD=12, DE=8. Thời gian giao hàng tại 4 điểm là 4·5=20 phút. Xét các chu trình Hamilton xuất phát và kết thúc tại A (chu trình thuận và nghịch cùng giá trị):
- A→B→C→D→E→A: 16+13+12+8+7 = 56 phút di chuyển.
- A→B→C→E→D→A: 16+13+15+8+18 = 70.
- A→B→E→C→D→A: 16+23+15+12+18 = 84.
- A→B→E→D→C→A: 16+23+8+12+12? kiểm tra lại: BE=23, ED=8, DC=12, CA không có cạnh trực tiếp nên chu trình này không hợp lệ (A chỉ nối B, E, D).
- A→C→D→E→B→A: 13+12+8+23+16 = 72.
- A→D→C→B→E→A: 18+12+13+23+7 = 73.
- A→D→E→C→B→A: 18+8+15+13+16 = 70.
- A→E→D→C→B→A: 7+8+12+13+16 = 56.
Thời gian di chuyển nhỏ nhất là 56 phút, cộng thêm 20 phút giao hàng: 56+20 = 76 phút. Đáp án B.

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh có trọng số: $AE=0,8$, $ED=3$, $AB=2$, $AF=2,5$, $EF=1$, $FD=1,2$, $BF=2$, $FC=2,2$, $DC=3$. Xét các đường đi từ $A$ đến $C$:
- $A\to F\to C$: $2,5+2,2=4,7$.
- $A\to E\to F\to C$: $0,8+1+2,2=4,0$.
- $A\to E\to D\to C$: $0,8+3+3=6,8$.
- $A\to B\to F\to C$: $2+2+2,2=6,2$.
- $A\to F\to D\to C$: $2,5+1,2+3=6,7$.
- $A\to E\to D\to F\to C$: $0,8+3+1,2+2,2=7,2$.
Thời gian ngắn nhất là $4$ giờ theo đường $A\to E\to F\to C$. Vậy chọn đáp án B.

(AI giải đề cho tôi)
Đây là bài toán tìm chu trình Hamilton ngắn nhất trên đồ thị với các cạnh: $AB=16$, $AC=12$, $AD=20$, $BC=10$, $BD=13$, $CD=9$. Xét các chu trình xuất phát từ $A$ (do tính đối xứng, chỉ cần 3 chu trình):
- $A\to B\to C\to D\to A$: $16+10+9+20=55$.
- $A\to B\to D\to C\to A$: $16+13+9+12=50$.
- $A\to C\to B\to D\to A$: $12+10+13+20=55$.
Vậy quãng đường ngắn nhất là $50$ mét (chu trình $A\to B\to D\to C\to A$ hoặc chiều ngược lại).

(AI giải đề cho tôi)
Đây là bài toán chu trình Hamilton (người bán hàng). Các cạnh: $AB=16,AC=12,BC=10,CD=9,AD=20,BD=13$. Xét các chu trình qua 4 đỉnh xuất phát từ $A$:
- $A\to B\to C\to D\to A$: $16+10+9+20=55$
- $A\to B\to D\to C\to A$: $16+13+9+12=50$
- $A\to C\to B\to D\to A$: $12+10+13+20=55$
- $A\to C\to D\to B\to A$: $12+9+13+16=50$
- $A\to D\to B\to C\to A$: $20+13+10+12=55$
- $A\to D\to C\to B\to A$: $20+9+10+16=55$

Quãng đường ngắn nhất là $50$ mét (chu trình $A\to B\to D\to C\to A$ hoặc $A\to C\to D\to B\to A$). Vậy chọn đáp án D.

(AI giải đề cho tôi)
Đây là bài toán người đưa thư Trung Hoa (Chinese Postman). Từ hình vẽ trang 6, đồ thị có các cạnh: $AB=1$, $BC=2$, $CD=3$, $BD=4$, $ED=5$, $AE=6$ (cạnh thẳng đứng), $BE=7$ (đường chéo), và cạnh cong ngoài $AE=8$. Tổng trọng số các cạnh: $1+2+3+4+5+6+7+8=36$ km. Xét bậc các đỉnh: $A$ bậc 3 (các cạnh $AB$, $AE=6$, cạnh cong $AE=8$) — lẻ; $B$ bậc 4 — chẵn; $C$ bậc 2 — chẵn; $D$ bậc 3 (các cạnh $BD$, $CD$, $ED$) — lẻ; $E$ bậc 4 — chẵn. Vậy chỉ có hai đỉnh bậc lẻ là $A$ và $D$, nên cần lặp lại con đường ngắn nhất nối $A$ với $D$. Đường đi ngắn nhất từ $A$ đến $D$: $A\to B\to D$ có độ dài $1+4=5$ (so sánh: $A\to E\to D=6+5=11$; $A\to B\to E\to D=1+7+5=13$). Quãng đường ngắn nhất $=36+5=41$ km. Hành trình cụ thể đạt 41 km: đi cạnh $A\to B\to D$ (lặp lại một lần) và mỗi cạnh còn lại đúng một lần, ví dụ $A\to B\to C\to D\to B\to E\to D\to E\to A(6)\to A(8)\to B\to A$... tổng bằng $36+5=41$. Kết quả khớp với đáp án nguồn: 41.

(AI giải đề cho tôi)
Bài toán tìm chu trình Euler có trọng số nhỏ nhất (bài toán người đưa thư Trung Hoa). Các cạnh: $AB=1$, $AE=8$ (cung), $AE=6$, $EB=7$, $ED=5$, $BD=4$, $BC=2$, $CD=3$. Tổng trọng số tất cả các cạnh: $1+8+6+7+5+4+2+3=36$. Bậc các đỉnh: $A$ có bậc $3$ ($AB$, $AE=8$, $AE=6$) lẻ; $B$ có bậc $4$ chẵn; $C$ có bậc $2$ chẵn; $D$ có bậc $3$ ($ED$, $BD$, $CD$) lẻ; $E$ có bậc $4$ chẵn. Hai đỉnh bậc lẻ là $A$ và $D$, nên cần lặp lại con đường ngắn nhất từ $A$ đến $D$. Đường đi ngắn nhất $A$ đến $D$: $A$–$B$–$D=1+4=5$ (so với $A$–$E$–$D=8+5=13$ hay $6+5=11$). Tổng quãng đường ngắn nhất $=36+5=41$ km.

(AI giải đề cho tôi)
Biểu diễn bài toán bằng lý thuyết đồ thị: 20 vận động viên là 20 đỉnh; hai đỉnh kề nhau nếu hai người đã thi đấu với nhau. Mỗi vòng đấu là một ghép cặp hoàn hảo (perfect matching) gồm 10 cạnh; sau 4 vòng ta được đồ thị $G$ đều bậc 4 trên 20 đỉnh, là hợp của 4 ghép cặp hoàn hảo, không có cặp cạnh lặp. Cần tìm $k$ lớn nhất sao cho mọi đồ thị như vậy đều có tập độc lập (các đỉnh đôi một không kề) cỡ ít nhất $k$.

BƯỚC 1: Chứng minh mọi cách đấu đều cho phép chọn được 5 người đôi một chưa từng gặp nhau, tức $\alpha (G)\ge 5$.

Giả sử ngược lại $\alpha (G)\le 4$. Xét đồ thị bổ $H=\overline{G}$: $H$ là đồ thị 15-chuẩn trên 20 đỉnh nên có $\frac{20\cdot 15}{2}=150$ cạnh. Điều kiện $\alpha (G)\le 4$ tức $\omega (H)\le 4$, nghĩa là $H$ không chứa $K_5$. Theo định lý Turán, số cạnh lớn nhất của đồ thị trên 20 đỉnh không chứa $K_5$ là $$t_4(20)=\left(1-\frac{1}{4}\right)\cdot \frac{20^2}{2}=150.$$ Vậy $H$ đạt đúng số cạnh cực đại, suy ra $H$ chính là đồ thị Turán $T_4(20)$ (đa phần hoàn chỉnh với 4 phần, mỗi phần 5 đỉnh), do đó $G=\overline{H}$ là hợp rời của 4 đồ thị $K_5$.

Nhưng điều này vô lý: trong một vòng đấu, các cặp đấu nội bộ một nhóm $K_5$ (5 người) tạo thành một ghép cặp trên 5 đỉnh nên gồm tối đa 2 cạnh, luôn còn ít nhất 1 người của nhóm phải đấu với người ngoài nhóm; trong khi $G$ không có cạnh nối giữa các nhóm. Mỗi vòng chỉ có tối đa 2 cạnh nội nhóm nên 4 vòng có tối đa 8 cạnh, nhỏ hơn 10 cạnh của $K_5$. Mâu thuẫn. Vậy $\alpha (G)\ge 5$ với mọi cách chia cặp.

BƯỚC 2: Xây dựng một lịch đấu 4 vòng cụ thể sao cho không chọn được 6 người đôi một chưa từng gặp, tức tồn tại cách đấu với $\alpha (G)=5$.

Chia 20 người thành 5 nhóm $A,B,C,D,E$, mỗi nhóm 4 người đánh số $0,1,2,3$. Mỗi nhóm sẽ đấu đủ 6 cặp nội bộ (tạo thành một $K_4$); mỗi người còn đấu đúng 1 ván chéo với người của nhóm khác. Lịch cụ thể:

- Vòng 1 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_1,a_2{a}_3,b_0{b}_1,b_2{b}_3,c_0{c}_1,c_2{c}_3,d_2{d}_3,e_2{e}_3,d_2{e}_2,d_3{e}_3.$$
- Vòng 2 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_2,a_1{a}_3,b_0{b}_2,b_1{b}_3,c_0{c}_2,c_1{c}_3,d_0{d}_1,e_0{e}_1,d_0{e}_0,d_1{e}_1.$$
- Vòng 3 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_0{a}_3,b_0{b}_3,c_0{c}_3,d_0{d}_2,d_1{d}_3,e_0{e}_2,e_1{e}_3,a_1{b}_1,a_2{c}_1,b_2{c}_2.$$
- Vòng 4 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_1{a}_2,b_1{b}_2,c_1{c}_2,d_0{d}_3,d_1{d}_2,e_0{e}_3,e_1{e}_2,a_0{b}_0,a_3{c}_3,b_3{c}_0.$$

Kiểm tra tính hợp lệ:
- Mỗi vòng đúng 10 ván; mỗi người đấu đúng 1 ván mỗi vòng (kiểm tra từng vòng: mỗi tên xuất hiện đúng một lần).
- Nội bộ mỗi nhóm: 6 cặp $x_0{x}_1,x_2{x}_3$ (vòng 1 hoặc 3 tùy nhóm), $x_0{x}_2,x_1{x}_3$, $x_0{x}_3$, $x_1{x}_2$ — đủ 6 cặp của $K_4$, mỗi cặp đúng một lần.
- Các ván chéo: mỗi người đúng 1 ván chéo, mọi ván chéo nối hai người khác nhóm, không ván nào lặp lại.

Vậy đây là một lịch đấu hợp lệ sau 4 vòng. Trong đồ thị tương ứng, mỗi nhóm là một $K_4$ nên một tập độc lập chứa tối đa 1 đỉnh từ mỗi nhóm, suy ra $\alpha (G)\le 5$; hiển nhiên $\alpha (G)=5$. Do đó với cách chia cặp này không thể chắc chắn chọn 6 người đôi một chưa từng thi đấu.

KẾT LUẬN: Giá trị $k$ lớn nhất cần tìm là $k=5$.

(AI giải đề cho tôi)
Biểu diễn bài toán bằng đồ thị: 20 đỉnh là 20 vận động viên, nối cạnh giữa hai người đã thi đấu với nhau. Mỗi vòng mọi người đều đấu nên sau 3 vòng mỗi đỉnh có bậc đúng 3 (đồ thị 3-chính trên 20 đỉnh, có 60 cạnh). Cần tìm $k$ lớn nhất sao cho mọi đồ thị như vậy đều chứa một tập độc lập (các đỉnh đôi một không kề) cỡ $k$.

**Bước 1: Chắc chắn chọn được 5 người.** Chọn tập độc lập tham lam: chọn một đỉnh bất kỳ, loại bỏ nó cùng tất cả các đỉnh kề với nó. Vì mỗi đỉnh chỉ kề với đúng 3 đỉnh khác, mỗi bước loại đi nhiều nhất 4 đỉnh. Sau nhiều nhất $\lceil 20/4\rceil =5$ bước, mọi đỉnh đã bị loại, và các đỉnh đã chọn đôi một không kề. Vậy luôn chọn được ít nhất $k=5$ người đôi một chưa từng đấu với nhau.

**Bước 2: Không thể đảm bảo 6 người — dựng cách chia cặp phản ví dụ.** Chia 20 vận động viên thành 5 nhóm 4 người. Trong mỗi nhóm, cho 4 người đấu đủ 3 vòng tương ứng 3 cách ghép cặp hoàn hảo của $K_4$: vòng 1: (1-2),(3-4); vòng 2: (1-3),(2-4); vòng 3: (1-4),(2-3). Khi đó mỗi người đấu đúng 3 trận, hai người bất kỳ không đấu quá một lần, thỏa mãn đề bài. Trong mỗi nhóm 4 người, mọi cặp đều đã đấu với nhau, nên những người 'chưa từng đấu với nhau' phải thuộc các nhóm khác nhau, do đó chọn được nhiều nhất 1 người từ mỗi nhóm, tức nhiều nhất 5 người. Vậy có cách chia cặp mà không thể chọn 6 người đôi một chưa từng thi đấu.

**Kết luận:** Số nguyên dương $k$ lớn nhất cần tìm là $k=5$.

Coi mỗi thành viên là một đỉnh và nối hai đỉnh khi hai thành viên tương ứng quen nhau. Ta thu được một đồ thị vô hướng đơn có tập đỉnh $V$, $|V|=99$. Với $u\in V$, kí hiệu $N(u)$ là tập các đỉnh kề với $u$ và $d(u)=|N(u)|$. Theo giả thiết, $81\le d(u)\le 90$ với mọi $u\in V$.

a) Ta sẽ đếm các bộ $(w,\{u,v\})$, trong đó $u,v$ là hai đỉnh phân biệt cùng thuộc $N(w)$.
- Cố định $w$, ta có số bộ là $$\sum _{w\in V}{C}_{d(w)}^2\ge 99C_{81}^2.$$
- Mặt khác, với mỗi cặp $\{u,v\}$, số cách chọn $w$ chính là $|N(u)\cap N(v)|$.
Vì có $C_{99}^2$ cặp đỉnh nên tồn tại một cặp $\{u,v\}$ có số người quen chung ít nhất bằng
$$\frac{99C_{81}^2}{C_{99}^2}=\frac{81\cdot 80}{98}=66+\frac{6}{49}>66.$$
Số người quen chung là một số nguyên, do đó cặp này có ít nhất 67 người quen chung.

b) Giả sử ngược lại rằng không tồn tại 10 đỉnh có cùng bậc và có một đỉnh kề chung. Khi đó không thể có trường hợp mọi đỉnh đều có bậc 81, vì khi đó tổng các bậc bằng $99\cdot 81$ là một số lẻ, trái với bổ đề bắt tay. Do đó tồn tại một đỉnh $v$ có $d(v)>81$.
Với mỗi $k\in \{81,82,\dots ,89\}$, tập $N(v)$ chứa nhiều nhất 9 đỉnh bậc $k$; nếu không, ta có ngay 10 đỉnh cùng bậc $k$ và cùng kề với $v$. Vì
$$|N(v)|>81=9\cdot 9,$$
trong $N(v)$ phải có một đỉnh $w$ bậc 90.
Xét tập $N(w)$ gồm 90 đỉnh. Với mỗi $k\in \{81,82,\dots ,90\}$, tập này chứa nhiều nhất 9 đỉnh bậc $k$. Có đúng 10 giá trị có thể của $k$, nên $N(w)$ phải chứa đúng 9 đỉnh thuộc mỗi bậc $81,82,\dots ,90$. Đặc biệt, $N(w)$ chứa 9 đỉnh bậc 90. Cùng với $w$, ta được một tập $A$ gồm 10 đỉnh, tất cả đều có bậc 90.
Với mỗi $u\in A$, trong 99 đỉnh có đúng $99-90=9$ đỉnh không kề với $u$, kể cả $u$. Do đó có không quá $10\cdot 9=90$ đỉnh không kề với ít nhất một đỉnh của $A$. Vì thế có ít nhất $99-90=9$ đỉnh kề với mọi đỉnh của $A$ nên có 10 đỉnh của $A$ có cùng bậc và có đỉnh kề chung, mâu thuẫn với phản chứng.
Vậy tồn tại 10 thành viên có cùng số lượng người quen và cùng quen chung một người.

Ta mô hình hóa bài toán bằng một đồ thị đơn $G=(V,E)$, trong đó mỗi đỉnh tương ứng với một hòn đảo và mỗi cạnh tương ứng với một cây cầu. Khi đó $|V|=300$ và $|E|=m$.
(1) Trước hết ta sẽ chứng minh bổ đề (định lí Euler):

Bổ đề 0.1. Một đồ thị vô hướng liên thông có chu trình Euler, tức là đi qua tất cả các cạnh đúng một lần và quay về đỉnh xuất phát khi và chỉ khi mọi đỉnh của đồ thị đều có bậc chẵn.

Chứng minh. Trước hết, giả sử tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần. Mỗi lần đường đi đi đến một đỉnh thì nó cũng rời đỉnh đó bằng một cạnh khác; đồng thời điểm đầu cũng là điểm cuối. Vì mỗi cạnh được dùng đúng một lần nên số cạnh kề với mỗi đỉnh là chẵn. Do đó mọi đỉnh đều có bậc chẵn.
Ngược lại, giả sử mọi đỉnh có bậc chẵn và tất cả các đỉnh có bậc dương thuộc cùng một thành phần liên thông. Chọn một đỉnh $v_0$ có bậc dương và bắt đầu đi từ $v_0$, tại mỗi bước chọn một cạnh chưa dùng kề với đỉnh hiện tại.
Để ý ta không thể dừng tại một đỉnh $v\ne v_0$. Thật vậy, mỗi lần đã đến rồi rời $v$ thì có hai cạnh kề với $v$ được dùng. Nếu hiện tại vừa đến $v$ mà không còn cạnh chưa dùng để đi tiếp thì số cạnh đã dùng kề với $v$ là lẻ, trong khi $\mathrm{deg}v$ chẵn, vô lí. Tiếp tục đi cho đến khi không thể đi tiếp. Vì $E$ hữu hạn nên quá trình phải dừng, và theo lập luận trên, đỉnh dừng phải là $v_0$. Do đó ta thu được một đường đi khép kín $C$ không lặp cạnh.
Nếu $C$ đã chứa tất cả các cạnh thì ta có điều phải chứng minh. Nếu chưa, vì tất cả các đỉnh có bậc dương thuộc cùng một thành phần liên thông nên tồn tại một đỉnh $u$ của $C$ kề với một cạnh chưa dùng. Bắt đầu từ $u$ và chỉ đi qua các cạnh chưa dùng; lập luận như trên cho ta một đường đi khép kín $C^{\prime }$ bắt đầu và kết thúc tại $u$. Bổ sung thêm $C^{\prime }$ vào $C$ tại $u$, ta được một đường đi khép kín dài hơn và vẫn không lặp cạnh. Lặp lại quá trình này; vì $E$ hữu hạn nên sau hữu hạn bước ta thu được một đường đi khép kín đi qua tất cả các cạnh đúng một lần.

Trở lại bài toán ban đầu: Vì tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần nên theo chiều thuận của định lí Euler, mỗi đỉnh của $G$ đều có bậc chẵn.
Vì $G$ là đồ thị đơn có 300 đỉnh nên $\mathrm{deg}v\le 299$ với mọi $v\in V$. Do $\mathrm{deg}v$ chẵn nên $\mathrm{deg}v\le 298$.
Theo bổ đề bắt tay, ta có $2m={\sum }_{v\in V}\mathrm{deg}v\le 300\cdot 298$, suy ra $m\le 44700$.
Giờ ta chỉ ra cách xây dựng thỏa mãn $m=44700$.
Đặt $V=\{1,2,\dots ,300\}$ và lấy tất cả các cạnh của đồ thị đầy đủ trên $V$, ngoại trừ 150 cạnh
$$\{i,i+150\},i=1,2,\dots ,150.$$
Khi đó mỗi đỉnh có bậc 298. Hơn nữa, đồ thị này liên thông. Thật vậy, nếu hai đỉnh $u,v$ không kề nhau thì chúng là hai đầu mút của một trong 150 cạnh đã bỏ. Lấy bất kì $w\notin \{u,v\}$, khi đó cả $uw$ và $wv$ đều là cạnh của đồ thị, nên ta có đường đi $u-w-v$.
Vì mọi đỉnh đều có bậc chẵn và đồ thị liên thông nên theo định lí Euler, tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần, và số cạnh của đồ thị là
$$\frac{300\cdot 299}{2}-150=44700.$$
Vậy $m_{\max }=44700$.
(2) Trước hết ta có bổ đề sau:

Bổ đề 0.2. Nếu một đồ thị $G=(V,E)$ không chứa chu trình thì $|E|\le |V|-1$.

Chứng minh. Ta quy nạp theo $|V|$. Với $|V|=1$ thì hiển nhiên.
Giả sử $|V|\ge 2$. Ta chứng minh rằng $G$ có một đỉnh bậc không quá 1. Thật vậy, giả sử ngược lại mọi đỉnh đều có bậc ít nhất 2. Chọn một đường đi đơn
$$v_0{v}_1\cdots v_k$$
có số cạnh lớn nhất. Vì $\mathrm{deg}{v}_0\ge 2$, ngoài $v_1$ còn có một đỉnh $u$ kề với $v_0$.
Nếu $u\notin \{v_0,v_1,\dots ,v_k\}$ thì $u{v}_0{v}_1\cdots v_k$ là đường đi đơn dài hơn, mâu thuẫn cách chọn đường đi.
Do đó $u=v_j$ với một $j\ge 2$. Khi ấy $v_0{v}_1\cdots v_j{v}_0$ là một chu trình, cũng mâu thuẫn.
Vậy tồn tại một đỉnh $v\in V$ có $\mathrm{deg}v\le 1$.
Xóa đỉnh $v$ cùng các cạnh kề với $v$. Đồ thị còn lại không chứa chu trình và có $|V|-1$ đỉnh, nên theo giả thiết quy nạp có nhiều nhất $|V|-2$ cạnh. Vì $\mathrm{deg}v\le 1$, ta có
$$|E|\le (|V|-2)+1=|V|-1.$$
Bổ đề được chứng minh theo nguyên lý quy nạp.

Trở lại bài toán ban đầu: Gọi $A_i$ là tập các đỉnh thuộc vương quốc thứ $i$ với $i\in \{1,2,3,4,5\}$. Trước hết, nếu có một vương quốc không quản lí hòn đảo nào thì $G$ không thể chứa chu trình nào, bởi một chu trình như vậy không đi qua hòn đảo thuộc vương quốc đó. Khi ấy theo bổ đề trên, $m\le 299<398$, nên kết luận hiển nhiên.
Vì vậy, ta chỉ cần xét trường hợp cả 5 vương quốc đều quản lí ít nhất một hòn đảo.
Đặt $n_i=|A_i|$. Khi đó $n_i\ge 1$ với mọi $i$ và $n_1+n_2+n_3+n_4+n_5=300$.
Với mỗi $i\in \{1,2,3,4,5\}$, ta bỏ khỏi $G$ tất cả các đỉnh thuộc $A_i$ cùng các cạnh kề với các đỉnh đó. Gọi đồ thị còn lại là $G_i$ và gọi $m_i$ là số cạnh của $G_i$.
Theo giả thiết, $G_i$ không chứa chu trình. Thật vậy, nếu $G_i$ chứa một chu trình thì chu trình đó cũng là một chu trình của $G$ và không đi qua bất kì đỉnh nào thuộc $A_i$, tức là không đi qua hòn đảo nào của vương quốc thứ $i$, trái với giả thiết.
Đồ thị $G_i$ có $300-n_i$ đỉnh nên theo bổ đề, $m_i\le 300-n_i-1=299-n_i$. Cộng lại ta được
$$m_1+m_2+m_3+m_4+m_5\le 5\cdot 299-(n_1+n_2+n_3+n_4+n_5)=1195$$
Xét một cạnh $uv$ của $G$.
- Nếu $u,v$ thuộc hai vương quốc khác nhau, chẳng hạn $u\in A_i$, $v\in A_j$ với $i\ne j$, thì cạnh $uv$ bị xóa khỏi $G_i$ và $G_j$, còn xuất hiện trong đúng ba đồ thị $G_k$ với $k\notin \{i,j\}$.
- Nếu $u,v$ cùng thuộc một vương quốc $A_i$ thì cạnh $uv$ chỉ bị xóa khỏi $G_i$, nên xuất hiện trong bốn đồ thị $G_k$ với $k\ne i$.
Vì vậy mỗi cạnh của $G$ được tính ít nhất ba lần trong tổng $m_1+m_2+m_3+m_4+m_5$.
Do đó $3m\le m_1+m_2+m_3+m_4+m_5\le 1195$ hay $m\le 398$.
Vậy tổng số cây cầu không thể vượt quá 398.

Xét các lộ trình hợp lệ xuất phát từ $M$ đi qua cả $4$ địa điểm $A,B,C,D$ (không đi theo chiều từ $B$ đến $A$), lộ trình ngắn nhất là $M\to C\to B\to D\to A$ với tổng quãng đường bằng $4+3+4+5=16\text{ km}$.

Xét các chu trình xuất phát từ $A$ đi qua $B,C,D$ rồi về $A$:
- $A\to C\to B\to D\to A$: $15+34+20+30=99$ (phút).
- $A\to B\to D\to C\to A$: $42+20+35+15=112$ (phút).
- $A\to B\to C\to D\to A$: $42+34+35+30=141$ (phút).
Vậy thời gian đi ít nhất là $99$ phút.

Xét các chu trình đi qua Thư viện ($T$) và $4$ trường $A,B,C,D$:
- $T\to A\to B\to C\to D\to T$ (hoặc ngược lại): $4+6+2+6+6=24\text{ km}$.
- $T\to A\to C\to D\to B\to T$: $4+7+6+5+3=25\text{ km}$.
- $T\to B\to D\to C\to A\to T$: $3+5+6+7+4=25\text{ km}$.
Vậy tổng độ dài quãng đường nhỏ nhất là $24\text{ km}$.

Xét các chu trình đi qua tất cả $5$ thành phố rồi quay về điểm xuất phát:
- $A\to B\to E\to C\to D\to A$ (hoặc ngược lại): $9+8+12+13+11=53$.
- $A\to E\to B\to C\to D\to A$: $10+8+14+13+11=56$.
- $A\to B\to C\to E\to D\to A$: $9+14+12+14+11=60$.
Vậy chi phí thấp nhất là $53$.

Chu trình đi qua tất cả $5$ trụ và quay về trụ ban đầu có tổng số thử thách nhỏ nhất là $A-B-D-C-E-A$ (hoặc ngược lại) với tổng số thử thách là $9+10+8+4+14=45$.