Chủ đề này có 2 trả lời

[The Collection]

Có $2n$ đại sứ đến dự một hội nghị. Mỗi vị đại sứ có nhiều nhất $n-1$ kẻ đối địch. Chứng minh rằng các vị đại sứ có thể ngồi xung quanh một cái bàn, mà trong đó không có ai ngồi cạnh kẻ đối địch của mình.

[whatever2507]

Bài này có thể giải bằng đơn biến nhưng nhân thể đang học đồ thị mình giải kiểu đồ thị :

Xét đồ thị $G=(V,E)$ với $\left \{ V \right \}=\left \{ A_i| 1 \leq i \leq 2n  \right \}$, mỗi đỉnh $A_i$ đại diện cho đại sứ $X_i \forall 1 \le i \le 2n$, $2$ đỉnh bất kỳ kề nhau khi và chỉ khi $2$ người mà chúng đại diện không phải là kẻ thù của nhau $\Rightarrow$ Mỗi đỉnh có bậc lớn hơn $n+1$ $\Rightarrow$ theo định lý Dirac, đồ thị tồn tại chu trình Hamilton.

WLOG, giả sử chu trình Hamilton đi theo thứ tự $A_1A_2...A_{2n}A_1$. Khi đó ta xếp các vị đại biểu lần lượt từ trái sang phải $X_1 \rightarrow X_2 \rightarrow...\rightarrow X_{2n} \rightarrow X_1$, khi đó đại sứ $X_i$ ngồi cạnh $X_{i-1}$ & $X_{i+1} (X_{2n+1}=X_1)$ mà theo lập luận trên đồ thị ta có $A_i$ kề $A_{i-1}$ & $A_{i+1}$ nên $X_{i-1}$ & $X_{i+1}$ không phải kẻ thù của $X_i$. Vậy ta có đpcm.

 

[The Collection]

Bài này có thể giải bằng đơn biến nhưng nhân thể đang học đồ thị mình giải kiểu đồ thị :

Xét đồ thị $G=(V,E)$ với $\left \{ V \right \}=\left \{ A_i| 1 \leq i \leq 2n  \right \}$, mỗi đỉnh $A_i$ đại diện cho đại sứ $X_i \forall 1 \le i \le 2n$, $2$ đỉnh bất kỳ kề nhau khi và chỉ khi $2$ người mà chúng đại diện không phải là kẻ thù của nhau $\Rightarrow$ Mỗi đỉnh có bậc lớn hơn $n+1$ $\Rightarrow$ theo định lý Dirac, đồ thị tồn tại chu trình Hamilton.

WLOG, giả sử chu trình Hamilton đi theo thứ tự $A_1A_2...A_{2n}A_1$. Khi đó ta xếp các vị đại biểu lần lượt từ trái sang phải $X_1 \rightarrow X_2 \rightarrow...\rightarrow X_{2n} \rightarrow X_1$, khi đó đại sứ $X_i$ ngồi cạnh $X_{i-1}$ & $X_{i+1} (X_{2n+1}=X_1)$ mà theo lập luận trên đồ thị ta có $A_i$ kề $A_{i-1}$ & $A_{i+1}$ nên $X_{i-1}$ & $X_{i+1}$ không phải kẻ thù của $X_i$. Vậy ta có đpcm.

 

Bạn có thể giải bằng đơn biến không?