Định Lý Ore: Chìa Khóa Mở Cánh Cửa Đường Đi Hamilton Trong Lý Thuyết Đồ Thị

Trong thế giới của lý thuyết đồ thị, việc tìm kiếm các cấu trúc đặc biệt như đường đi hoặc chu trình Hamilton luôn là một chủ đề hấp dẫn và đầy thách thức. Định lý Ore nổi lên như một công cụ mạnh mẽ, cung cấp những điều kiện đủ quan trọng để xác định sự tồn tại của chu trình Hamilton trong một đồ thị vô hướng. Bài viết này sẽ đi sâu vào khám phá định lý Ore, so sánh nó với định lý Dirac, và minh họa cách áp dụng các định lý này thông qua các ví dụ cụ thể, giúp người đọc nắm vững kiến thức nền tảng và kỹ năng giải toán liên quan đến đường đi Hamilton.

Đề Bài

Dưới đây là một số bài toán minh họa liên quan đến đường đi Hamilton và các định lý Dirac, Ore.

Bài Toán 1: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có deg(u) + deg(v) \ge n, thì $G$ có chu trình Hamilton không?

Bài Toán 2: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có deg(u) + deg(v) \ge n-1, thì $G$ có chu trình Hamilton không?

Bài Toán 3: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi đỉnh $v$ trong $G$, ta có deg(v) \ge \frac{n}{2}, thì $G$ có chu trình Hamilton không?

Bài Toán 4: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi đỉnh $v$ trong $G$, ta có deg(v) \ge \frac{n-1}{2}, thì $G$ có chu trình Hamilton không?

Bài Toán 5: Xét đồ thị đầy đủ K_n với $n$ đỉnh. Chứng minh rằng đồ thị này có chu trình Hamilton.

Bài Toán 6: Cho đồ thị $G$ có 5 đỉnh. Biết rằng bậc của các đỉnh lần lượt là 4, 3, 3, 2, 2. Hỏi $G$ có chu trình Hamilton không?

Phân Tích Yêu Cầu

Các bài toán trên đều xoay quanh việc xác định sự tồn tại của chu trình Hamilton trong một đồ thị dựa trên các điều kiện về bậc của các đỉnh. Yêu cầu chung là áp dụng các định lý đã học (cụ thể là Định lý Dirac và Định lý Ore) để đưa ra kết luận.

• Bài Toán 1 & 2: Kiểm tra điều kiện của Định lý Ore.
• Bài Toán 3 & 4: Kiểm tra điều kiện của Định lý Dirac.
• Bài Toán 5: Chứng minh một trường hợp đặc biệt của đồ thị có chu trình Hamilton.
• Bài Toán 6: Áp dụng cả hai định lý để kiểm tra.

Để giải quyết các bài toán này, chúng ta cần hiểu rõ phát biểu và điều kiện của Định lý Dirac và Định lý Ore.

Kiến Thức/Nền Tảng Cần Dùng

Trước khi đi vào giải chi tiết, chúng ta cần nắm vững các khái niệm và định lý liên quan.

1. Đường đi và Chu trình Hamilton

• Đường đi Hamilton: Là một đường đi trong đồ thị đi qua mỗi đỉnh đúng một lần.
• Chu trình Hamilton: Là một chu trình trong đồ thị đi qua mỗi đỉnh đúng một lần, và đỉnh đầu cũng là đỉnh cuối.

Việc tìm kiếm một chu trình Hamilton là một bài toán NP-đầy đủ, nghĩa là không có thuật toán hiệu quả nào được biết đến để giải quyết nó cho mọi trường hợp. Tuy nhiên, có những định lý cung cấp điều kiện đủ để đảm bảo sự tồn tại của chu trình Hamilton.

2. Định lý Dirac (1952)

Phát biểu: Cho một đồ thị vô hướng $G$ có $n$ đỉnh, với n \ge 3. Nếu bậc của mọi đỉnh trong $G$ đều lớn hơn hoặc bằng \frac{n}{2} (tức là deg(v) \ge \frac{n}{2} với mọi $v in V(G)$), thì $G$ có chu trình Hamilton.

Lưu ý: Điều kiện deg(v) \ge \frac{n}{2} là điều kiện đủ, không phải điều kiện cần. Tức là, có những đồ thị có chu trình Hamilton nhưng không thỏa mãn điều kiện này.

3. Định lý Ore (1960)

Phát biểu: Cho một đồ thị vô hướng $G$ có $n$ đỉnh, với n \ge 3. Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có tổng bậc của chúng lớn hơn hoặc bằng $n$ (tức là deg(u) + deg(v) \ge n với mọi cặp đỉnh không kề $u, v$), thì $G$ có chu trình Hamilton.

Mối quan hệ giữa Định lý Dirac và Định lý Ore:
Định lý Ore là một trường hợp tổng quát hơn của Định lý Dirac. Nếu một đồ thị thỏa mãn điều kiện của Định lý Dirac, nó cũng sẽ thỏa mãn điều kiện của Định lý Ore.

• Giả sử deg(v) \ge \frac{n}{2} với mọi $v$.
• Xét hai đỉnh không kề $u, v$. Ta có deg(u) \ge \frac{n}{2} và deg(v) \ge \frac{n}{2}.
• Do đó, deg(u) + deg(v) \ge \frac{n}{2} + \frac{n}{2} = n.
• Vậy, điều kiện của Định lý Dirac suy ra điều kiện của Định lý Ore.

Tuy nhiên, điều ngược lại không đúng. Có những đồ thị thỏa mãn Định lý Ore nhưng không thỏa mãn Định lý Dirac. Ví dụ, một đồ thị có 5 đỉnh với các bậc là 3, 3, 3, 2, 2.

• n=5.
• Điều kiện Dirac: deg(v) \ge \frac{5}{2} = 2.5. Đỉnh có bậc 2 không thỏa mãn.
• Điều kiện Ore: Xét các cặp không kề. Giả sử đỉnh có bậc 2 là v_4, v_5.
  • Nếu v_4 không kề v_1, deg(v_4) + deg(v_1) = 2 + 3 = 5 \ge 5.
  • Nếu v_4 không kề v_2, deg(v_4) + deg(v_2) = 2 + 3 = 5 \ge 5.
  • Nếu v_4 không kề v_3, deg(v_4) + deg(v_3) = 2 + 3 = 5 \ge 5.
  • Nếu v_5 không kề v_1, deg(v_5) + deg(v_1) = 2 + 3 = 5 \ge 5.
  • … và cứ thế. Nếu không có cặp đỉnh nào có tổng bậc nhỏ hơn 5, thì đồ thị thỏa mãn Ore.

4. Đồ thị đầy đủ K_n

Đồ thị đầy đủ K_n là đồ thị có $n$ đỉnh, trong đó mỗi cặp đỉnh phân biệt đều được nối với nhau bởi một cạnh.

• Trong K_n, bậc của mỗi đỉnh là n-1.
• Với n \ge 3, ta có deg(v) = n-1.
• So với điều kiện Dirac: n-1 \ge \frac{n}{2} Leftrightarrow 2n-2 \ge n Leftrightarrow n \ge 2. Điều này luôn đúng với n \ge 3.
• So với điều kiện Ore: Với mọi cặp đỉnh không kề $u, v$. Trong K_n, mọi cặp đỉnh đều kề nhau, nên điều kiện này được coi là “trivially true” (hiển nhiên đúng) vì không có cặp đỉnh không kề nào để kiểm tra.

Do đó, K_n luôn có chu trình Hamilton với n \ge 3.

Hướng Dẫn Giải Chi Tiết

Bây giờ, chúng ta sẽ áp dụng các kiến thức trên để giải quyết từng bài toán.

Bài Toán 1: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có deg(u) + deg(v) \ge n, thì $G$ có chu trình Hamilton không?

• Phân tích: Điều kiện deg(u) + deg(v) \ge n cho mọi cặp đỉnh không kề $u, v$ chính là phát biểu của Định lý Ore.
• Áp dụng định lý: Theo Định lý Ore, nếu điều kiện này được thỏa mãn, thì đồ thị $G$ chắc chắn có chu trình Hamilton.
• Kết luận: Có.

Bài Toán 2: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có deg(u) + deg(v) \ge n-1, thì $G$ có chu trình Hamilton không?

• Phân tích: Điều kiện deg(u) + deg(v) \ge n-1 là một điều kiện yếu hơn so với Định lý Ore (deg(u) + deg(v) \ge n).
• Áp dụng định lý: Định lý Ore chỉ đảm bảo chu trình Hamilton khi tổng bậc là \ge n. Điều kiện \ge n-1 không đủ để kết luận theo Định lý Ore.
• Ví dụ phản chứng: Xét đồ thị đường đi P_n với n \ge 4. Ví dụ P_4 có 4 đỉnh, các bậc là 1, 2, 2, 1. n=4.
  • Cặp đỉnh không kề: (đỉnh 1, đỉnh 3), (đỉnh 1, đỉnh 4), (đỉnh 2, đỉnh 4).
  • deg(1) + deg(3) = 1 + 2 = 3. n-1 = 4-1 = 3. Điều kiện deg(u) + deg(v) \ge n-1 được thỏa mãn (3 \ge 3).
  • Tuy nhiên, P_4 là một đường đi, không phải chu trình Hamilton.
• Kết luận: Không chắc chắn. Điều kiện này không đủ để đảm bảo $G$ có chu trình Hamilton.

Bài Toán 3: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi đỉnh $v$ trong $G$, ta có deg(v) \ge \frac{n}{2}, thì $G$ có chu trình Hamilton không?

• Phân tích: Điều kiện deg(v) \ge \frac{n}{2} cho mọi đỉnh $v$ chính là phát biểu của Định lý Dirac.
• Áp dụng định lý: Theo Định lý Dirac, nếu điều kiện này được thỏa mãn, thì đồ thị $G$ chắc chắn có chu trình Hamilton.
• Kết luận: Có.

Bài Toán 4: Cho đồ thị $G$ có $n$ đỉnh (n \ge 3). Nếu với mọi đỉnh $v$ trong $G$, ta có deg(v) \ge \frac{n-1}{2}, thì $G$ có chu trình Hamilton không?

• Phân tích: Điều kiện deg(v) \ge \frac{n-1}{2} là một điều kiện yếu hơn so với Định lý Dirac (deg(v) \ge \frac{n}{2}).
• Áp dụng định lý: Định lý Dirac chỉ đảm bảo chu trình Hamilton khi bậc mỗi đỉnh là \ge \frac{n}{2}. Điều kiện \ge \frac{n-1}{2} không đủ để kết luận theo Định lý Dirac.
• Ví dụ phản chứng: Xét đồ thị K_{1,n-1} (đồ thị sao) với n \ge 4. Đồ thị này có 1 đỉnh trung tâm bậc n-1 và n-1 đỉnh lá bậc 1.
  • Chọn n=5. Đồ thị K_{1,4} có 5 đỉnh. Bậc các đỉnh là 4, 1, 1, 1, 1.
  • Điều kiện đề bài: deg(v) \ge \frac{5-1}{2} = 2. Đỉnh có bậc 1 không thỏa mãn.
  • Tuy nhiên, ta có thể xem xét một trường hợp khác. Xét đồ thị với n=6. Điều kiện là deg(v) \ge \frac{6-1}{2} = 2.5. Tức là bậc ít nhất phải là 3.
  • Xét đồ thị C_6 (chu trình 6 đỉnh). Bậc mỗi đỉnh là 2. n=6. \frac{n-1}{2} = 2.5. Đồ thị C_6 không thỏa mãn điều kiện deg(v) \ge 2.5. Nhưng C_6 có chu trình Hamilton.
  • Xét đồ thị $G$ có 6 đỉnh, các bậc là 3, 3, 3, 3, 3, 3. Điều kiện deg(v) \ge 2.5 thỏa mãn. $G$ có thể có chu trình Hamilton.
  • Xét đồ thị $G$ có 6 đỉnh, các bậc là 3, 3, 3, 3, 2, 2. n=6. \frac{n-1}{2} = 2.5. Đỉnh có bậc 2 không thỏa mãn. Tuy nhiên, đồ thị này có thể có chu trình Hamilton.
  • Để có phản ví dụ rõ ràng hơn: Xét đồ thị $G$ có $n$ đỉnh, trong đó có n-1 đỉnh bậc 1 và 1 đỉnh bậc n-1. Đây là đồ thị sao K_{1,n-1}.
    • Nếu n=4, bậc là 3, 1, 1, 1. Điều kiện deg(v) \ge \frac{4-1}{2} = 1.5. Đỉnh bậc 1 không thỏa mãn. K_{1,3} không có chu trình Hamilton.
    • Nếu n=5, bậc là 4, 1, 1, 1, 1. Điều kiện deg(v) \ge \frac{5-1}{2} = 2. Đỉnh bậc 1 không thỏa mãn. K_{1,4} không có chu trình Hamilton.
  • Ta cần một đồ thị thỏa mãn điều kiện nhưng không có chu trình Hamilton.
  • Xét đồ thị $G$ gồm hai K_3 nối với nhau bởi một cạnh duy nhất. n=6. Bậc các đỉnh là 3, 3, 3, 3, 2, 2. Điều kiện deg(v) \ge \frac{6-1}{2} = 2.5. Hai đỉnh bậc 2 không thỏa mãn. Đồ thị này không có chu trình Hamilton.
• Kết luận: Không chắc chắn. Điều kiện này không đủ để đảm bảo $G$ có chu trình Hamilton.

Bài Toán 5: Xét đồ thị đầy đủ K_n với $n$ đỉnh. Chứng minh rằng đồ thị này có chu trình Hamilton.

• Phân tích: Đồ thị đầy đủ K_n có $n$ đỉnh, và mỗi cặp đỉnh phân biệt được nối với nhau bởi một cạnh.
• Áp dụng Định lý Ore:
  • Trong K_n, mọi cặp đỉnh đều kề nhau. Do đó, không tồn tại cặp đỉnh không kề nào.
  • Phát biểu của Định lý Ore là “Nếu với mọi cặp đỉnh không kề $u, v$ trong $G$, ta có deg(u) + deg(v) \ge n“.
  • Vì không có cặp đỉnh không kề nào, điều kiện này được coi là đúng một cách hiển nhiên (vacuously true).
  • Do đó, theo Định lý Ore, K_n có chu trình Hamilton.
• Áp dụng Định lý Dirac:
  • Trong K_n, bậc của mỗi đỉnh là n-1.
  • Với n \ge 3, ta có n-1 \ge \frac{n}{2} Leftrightarrow 2n-2 \ge n Leftrightarrow n \ge 2. Điều này luôn đúng với n \ge 3.
  • Do đó, theo Định lý Dirac, K_n có chu trình Hamilton.
• Chứng minh trực tiếp (xây dựng chu trình):
  • Ta có thể xây dựng một chu trình Hamilton cho K_n bằng cách đánh số các đỉnh từ 0 đến n-1.
  • Một chu trình Hamilton là: 0 \to 1 \to 2 \to dots \to n-1 \to 0.
  • Vì K_n có cạnh giữa mọi cặp đỉnh, nên tất cả các cạnh trong đường đi này đều tồn tại.
  • Đường đi này đi qua mỗi đỉnh đúng một lần và quay về đỉnh ban đầu, do đó nó là một chu trình Hamilton.
• Kết luận: Có. K_n luôn có chu trình Hamilton với n \ge 3.

Bài Toán 6: Cho đồ thị $G$ có 5 đỉnh. Biết rằng bậc của các đỉnh lần lượt là 4, 3, 3, 2, 2. Hỏi $G$ có chu trình Hamilton không?

• Phân tích: Ta có n=5. Bậc của các đỉnh là d_1=4, d_2=3, d_3=3, d_4=2, d_5=2.
• Kiểm tra Định lý Dirac:
  • Điều kiện Dirac là deg(v) \ge \frac{n}{2} với mọi $v$.
  • Ở đây, \frac{n}{2} = \frac{5}{2} = 2.5.
  • Ta có các đỉnh với bậc 2 (ví dụ d_4, d_5) không thỏa mãn điều kiện deg(v) \ge 2.5.
  • Do đó, Định lý Dirac không áp dụng được để khẳng định $G$ có chu trình Hamilton.
• Kiểm tra Định lý Ore:
  • Điều kiện Ore là deg(u) + deg(v) \ge n với mọi cặp đỉnh không kề $u, v$.
  • Ở đây, n=5. Điều kiện là deg(u) + deg(v) \ge 5.
  • Ta cần xem xét các cặp đỉnh không kề.
  • Đỉnh có bậc 4 là đỉnh kề với tất cả các đỉnh còn lại (vì 4 = n-1). Gọi đỉnh này là v_1.
  • Các đỉnh có bậc 2 (gọi là v_4, v_5) không kề với đỉnh v_1.
  • Xét cặp (v_4, v_1): v_4 không kề v_1. deg(v_4) + deg(v_1) = 2 + 4 = 6. 6 \ge 5. Thỏa mãn.
  • Xét cặp (v_5, v_1): v_5 không kề v_1. deg(v_5) + deg(v_1) = 2 + 4 = 6. 6 \ge 5. Thỏa mãn.
  • Bây giờ, xét các đỉnh còn lại: v_2, v_3 (bậc 3) và v_4, v_5 (bậc 2).
  • Giả sử v_4 không kề v_5. deg(v_4) + deg(v_5) = 2 + 2 = 4. $4 < 5$.
  • Nếu v_4 và v_5 không kề nhau, thì điều kiện của Định lý Ore không được thỏa mãn.
  • Tuy nhiên, chúng ta cần biết liệu có tồn tại một đồ thị 5 đỉnh với các bậc như vậy mà thỏa mãn Định lý Ore hay không.
  • Một đồ thị có 5 đỉnh với các bậc 4, 3, 3, 2, 2 có thể là:
    • Đỉnh v_1 (bậc 4) nối với v_2, v_3, v_4, v_5.
    • Đỉnh v_2 (bậc 3) nối với v_1, v_3, v_x.
    • Đỉnh v_3 (bậc 3) nối với v_1, v_2, v_y.
    • Đỉnh v_4 (bậc 2) nối với v_1, v_z.
    • Đỉnh v_5 (bậc 2) nối với v_1, v_w.
  • Vì v_1 nối với tất cả, nên v_2, v_3, v_4, v_5 đều kề với v_1.
  • Các đỉnh v_2, v_3 có bậc 3. Chúng đã nối với v_1. Chúng cần thêm 2 cạnh nữa.
  • Các đỉnh v_4, v_5 có bậc 2. Chúng đã nối với v_1. Chúng cần thêm 1 cạnh nữa.
  • Để tổng bậc là 4, 3, 3, 2, 2, đồ thị phải là:
    • v_1 nối với v_2, v_3, v_4, v_5.
    • v_2 nối với v_1, v_3, v_4. (bậc 3)
    • v_3 nối với v_1, v_2, v_5. (bậc 3)
    • v_4 nối với v_1, v_2. (bậc 2)
    • v_5 nối với v_1, v_3. (bậc 2)
  • Kiểm tra lại bậc:
    • deg(v_1) = 4 (với v_2, v_3, v_4, v_5) – Đúng.
    • deg(v_2) = 3 (với v_1, v_3, v_4) – Đúng.
    • deg(v_3) = 3 (với v_1, v_2, v_5) – Đúng.
    • deg(v_4) = 2 (với v_1, v_2) – Đúng.
    • deg(v_5) = 2 (với v_1, v_3) – Đúng.
  • Bây giờ, kiểm tra điều kiện Ore: deg(u) + deg(v) \ge 5 cho mọi cặp không kề.
    • Cặp (v_4, v_5): v_4 không kề v_5 (vì v_4 chỉ kề v_1, v_2; v_5 chỉ kề v_1, v_3).
    • deg(v_4) + deg(v_5) = 2 + 2 = 4.
    • $4 < 5$.
  • Do đó, đồ thị với các bậc 4, 3, 3, 2, 2 như mô tả trên không thỏa mãn điều kiện của Định lý Ore.
• Kết luận: Không chắc chắn. Định lý Dirac không áp dụng được. Đồ thị có thể có hoặc không có chu trình Hamilton. Dựa trên ví dụ cụ thể của một đồ thị có các bậc này, ta thấy nó không thỏa mãn Định lý Ore. Tuy nhiên, có thể tồn tại một đồ thị khác với cùng các bậc này mà thỏa mãn Định lý Ore (hoặc không). Nhưng với ví dụ cụ thể này, ta không thể kết luận có chu trình Hamilton.

Mẹo kiểm tra: Khi gặp bài toán về chu trình Hamilton, hãy luôn nghĩ đến Định lý Dirac và Định lý Ore. Kiểm tra điều kiện của chúng trước tiên. Nếu thỏa mãn, kết luận có chu trình Hamilton. Nếu không thỏa mãn, cần xem xét thêm hoặc tìm ví dụ phản chứng.

Lỗi hay gặp:

• Nhầm lẫn điều kiện đủ và điều kiện cần.
• Áp dụng sai công thức tính bậc hoặc số đỉnh.
• Quên kiểm tra điều kiện n \ge 3.
• Không kiểm tra tất cả các cặp đỉnh không kề khi áp dụng Định lý Ore.

Đáp Án/Kết Quả

• Bài Toán 1: Có.
• Bài Toán 2: Không chắc chắn.
• Bài Toán 3: Có.
• Bài Toán 4: Không chắc chắn.
• Bài Toán 5: Có.
• Bài Toán 6: Không chắc chắn. (Dựa trên ví dụ cụ thể, đồ thị không thỏa mãn Định lý Ore).

Conclusion

Định lý Ore và Định lý Dirac là những công cụ nền tảng trong lý thuyết đồ thị, cung cấp những tiêu chí mạnh mẽ để xác định sự tồn tại của chu trình Hamilton. Hiểu rõ phát biểu, điều kiện và mối quan hệ giữa hai định lý này, cùng với khả năng áp dụng chúng vào các bài toán cụ thể, là kỹ năng thiết yếu cho bất kỳ ai nghiên cứu về cấu trúc đồ thị. Việc phân tích cẩn thận các điều kiện về bậc của đỉnh và các cặp đỉnh không kề sẽ giúp chúng ta đưa ra kết luận chính xác, từ đó mở rộng hiểu biết về các tính chất phức tạp của đồ thị.

Ngày chỉnh sửa nội dung mới nhất January 15, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT
Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.