Định lý Dirac và ứng dụng

Định lý  (Dirac 1952)

Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.

Chứng minh:

Ký hiệu n đỉnh của G là ${\displaystyle v_{1},v_{2},v_{3},...,v_{n}}$.

Không mất tính tổng quát giả sử đường đi H dài nhất của G là ${\displaystyle v_{1}v_{2}v_{3}...v_{l}}$. H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.

Nếu ${\displaystyle l=n}$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp ${\displaystyle l<n}$.

Gọi tất cả các đỉnh liền kề với ${\displaystyle v_{l}}$ là ${\displaystyle v_{i_{1}},v_{i_{2}},...,v_{i_{t}}}$ (với ${\displaystyle 0<i_{1}<i_{2}<...<i_{t}<n+1}$ và ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$). Dễ thấy ${\displaystyle {i_{j}}<l}$ với mọi j chạy từ 1 tới t, vì nếu tồn tại ${\displaystyle {i_{j}}>l}$, thì suy ra tồn tại đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}v_{3}...v_{l}v_{i_{j}}}$.

Nếu đỉnh ${\displaystyle v_{l+1}}$ mà liền kề với đỉnh ${\displaystyle v_{i_{j}+1}}$ thì ta sẽ tạo được đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}...v_{i_{j}-1}v_{i_{j}}v_{l}v_{l-1}...v_{i_{j}+1}v_{l+1}}$

(vô lý).

Vậy ${\displaystyle v_{l+1}}$ không liền kề với các đỉnh ${\displaystyle v_{i_{j}+1}}$, với j chạy từ 1 đến t. Mà ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$, nên suy ra bậc của ${\displaystyle v_{l+1}}$ nhỏ hơn ${\displaystyle {\frac {n}{2}}}$ (vô lý).

Vậy trường hợp l<n là không tồn tại.

Suy ra điều phải chứng minh.

Ứng dụng của nó là bài toán nổi tiếng sau:

Bài toán: Tại một hội nghị có 2n quan khách.trong đó mỗi quan khách có nhiều nhất n-1 kẻ thù.chứng minh rằng có thể xếp 2n nguời đó trên 1 vòng tròn sao cho không ai ngồi cạnh kẻ thù của mình 

Lời giải:

Ta xây dựng đồ thị G như sau:

-Đỉnh: là các điểm trong mặt phẳng hay trong không gian tương ứng với các quan khách, dùng mã số của các quan khách để ghi trên các đỉnh tương ứng.

-Cạnh: hai đỉnh được nối với nhau bằng cạnh khi và chỉnh khi hai quan khác tương ứng thuộc hai đỉnh đó không là kẻ thù của nhau.

Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ giữa các quan khách. Vì đồ thị G có đúng 2n đỉnh, và mỗi đỉnh có bậc không nhỏ hơn n nên theo định lý Dirac ta có G có chu trình Halminton. Dựa vào chu trình này ta có thể xếp tất cả các quan khách thỏa mãn yêu cầu đề bài