Một điều kiện đủ cho đồ thị Hamilton tối đại
Một đồ thị được gọi là đồ thị Hamilton tối đại nếu như nó có nhiều cạnh nhất trong tất cả các đồ thị có cùng số đỉnh và có duy nhất một chu trình Hamilton. Đồ thị Hamilton tối đại đã được Sheehan nghiên cứu từ năm 1977. Sheehan đã chứng minh rằng đồ thị Hamilton tối đại đỉnh có chính xác cạnh và...
Đã lưu trong:
| Tác giả chính: | |
|---|---|
| Ngôn ngữ: | Vietnamese |
| Được phát hành: |
Trường Đại học Đà Lạt
2011
|
| Những chủ đề: | |
| Truy cập trực tuyến: | http://scholar.dlu.edu.vn/thuvienso/handle/DLU123456789/3557 |
| Các nhãn: |
Thêm thẻ
Không có thẻ, Là người đầu tiên thẻ bản ghi này!
|
| Thư viện lưu trữ: | Thư viện Trường Đại học Đà Lạt |
|---|
| Tóm tắt: | Một đồ thị được gọi là đồ thị Hamilton tối đại nếu như nó có nhiều cạnh nhất trong tất cả các đồ thị có cùng số đỉnh và có duy nhất một chu trình Hamilton. Đồ thị Hamilton tối đại đã được Sheehan nghiên cứu từ năm 1977. Sheehan đã chứng minh rằng đồ thị Hamilton tối đại đỉnh có chính xác cạnh và khẳng định rằng, với mỗi có chính xác một đồ thị Hamilton tối đại đỉnh. Năm 2006, Vũ Đình Hòa và Đỗ Như An đã phủ nhận kết quả của Sheehan về tính duy nhất của đồ thị Hamilton tối đại với đỉnh, đồng thời đề xuất thuật toán đa thức xây dựng đồ thị Hamilton tối đại đỉnh đôi một không đẳng cấu.
Bài viết này trình bày một điều kiện đủ cho đồ thị Hamilton tối đại và thảo luận một số vấn đề liên quan. |
|---|