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)
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.

Đây là bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của đồ thị (bài toán người đưa thư Trung Hoa). Tổng độ dài tất cả các cạnh ban đầu cộng với độ dài các cạnh cần đi lặp lại tối thiểu giữa các đỉnh bậc lẻ cho kết quả bằng $106$.