Định lý Dirac

trang định hướng Wikimedia

Trong lý thuyết đồ thị, có hai định lý được gọi là định lý Dirac (tiếng Anh: Dirac's theorem), cả hai đều được đặt theo tên nhà toán học Gabriel Andrew Dirac:

1. Cho G là một đồ thị k-liên thông (tiếng Anh: k-connected graph). Ta có thể khẳng định với mỗi tập k đỉnh bất kì trong G, thì tồn tại ít nhất một chu trình đơn trong G đi qua k đỉnh này.
2. Dirac, 1952: Cho G là một đồ thị đơnn ≥ 3 đỉnh. Nếu mỗi đỉnh đều có bậc không nhỏ hơn thì Gđường đi Hamilton[1].

Chứng minhSửa đổi

Định lý 2Sửa đổi

Ký hiệu n đỉnh của G .

Không mất tính tổng quát giả sử đường đi H dài nhất của G . 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   thì suy ra luôn điều phải chứng minh.

Xét trường hợp  .

Gọi tất cả các đỉnh liền kề với    (với    ). Dễ thấy   với mọi j chạy từ 1 tới t, vì nếu tồn tại  , thì suy ra tồn tại đường đi có độ dài l+1:

 .

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

 

(vô lý).

Vậy   không liền kề với các đỉnh  , với j chạy từ 1 đến t. Mà   , nên suy ra bậc của   nhỏ hơn   (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.

Chú thíchSửa đổi

  1. ^ Graham, p. 20.

Tham khảoSửa đổi