Về câu hỏi có tồn tại chu trình Hamilton hay không của một đồ thị cho trước

Về câu hỏi có tồn tại chu trình Hamilton hay không của một đồ thị cho trước

Với một đồ thị cho trước, có sách viết rằng ta không thể trả lời luôn rằng nó có tồn tại chu trình Hamilton hay không, trừ một số trường hợp đặc biệt ví dụ như đồ thị đó là đầy đủ.
Tôi muốn nêu một hướng giải quyết vấn đề này, mong các bạn để tâm theo dõi:

Với một đồ thị vô hướng, tôi định chuyển đỉnh thành cạnh và cạnh thành đỉnh.
ví dụ với 2 đoạn thẳng (1) với 2 đầu mút là 1,2 và (2) với đầu mút 2,3 như minh hoạ dưới đây :

(1) (2)
1 ------------- 2--------------3
Ta sẽ chuyển như sau:

2
(1)-------------------(2)

Tôi post kèm cả ví dụ theo đây



Sau khi chuyển đổi đồ thị thì ta sẽ trả lời được ngay đồ thị mới có chu trình Euler hay không. Nó có chu trình Euler nếu tất cả các "đỉnh" của nó có bậc chẵn ( tại example1.gif ở trên, bậc "đỉnh" (1) là chẵn vì tuy nó nối 3 "cạnh" nhưng trong đó có hai "cạnh" trùng nhau là 1 ). Mà nếu đồ thị mới có chu trình Euler thì đồ thị cũ sẽ có chu trình Hamilton. Tất nhiên, trước đó ta phải kiểm tra xem đồ thị ban đầu có liên thông hay không đã.

Không biết phát biểu thế có đúng không ?

( Bài này mình đã post tại bên CNTT nhưng có vẻ không đúng chỗ nên post lại ở đây )





Được jbravo sửa chữa / chuyển vào 22:08 ngày 17/10/2003

Được jbravo sửa chữa / chuyển vào 22:06 ngày 17/10/2003

Cái này của bác mà đúng thì bác được cả triệu USD đấy.
Nhưng tiếc quá lại không đúng.
Cái đồ thị của bác cũng được nghiên cứu khá kỹ.
Chu trình Euler ở đồ thị kia không tương đương với chu trình Harminton ở đồ thị ban đầu.
Euler có thể đi qua1 đỉnh nhiều lần.
Matek
Được matek sửa chữa / chuyển vào 05:29 ngày 19/10/2003

Việc tồn tại một thuật toán chạy với thời gian đa thức để xác định được một đồ thị có chu trình Hamilton hay không là tương đương với lời giải bài toán P = NP - Một trong 7 bài toán 1 triệu đô của viện Clay ...
Cá nhân tớ thì cho rằng bài toán này không có lời giải đâu ..
Nguyện mỗi người có một niềm vui!

Bác CXR mà chứng minh được suy nghĩ của mình là bác trở thành nhà toán học Vn giàu nhất rồi đấy!!!