THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH HAMILTON TRONG LỚP ĐỒ THỊ

Vũ Đình Hòa, Nguyễn Hữu Xuân Trường

Abstract


Cho trước một đồ thị đơn vô hướng với  đỉnh, ta kí hiệu  là tổng bậc bé nhất của các cặp đỉnh không kề nhau trong .

Trong [1], các tác giả đã khảo sát đồ thị đỉnh thỏa mãn điều kiện  cho mọi cặp đỉnh không kề nhau và và chứng minh rằng đồ thị có chu trình Hamilton (chu trình đi qua tất cả các đỉnh của đồ thị) khi và chỉ khi  lẻ và   , ở đó  là chỉ số ổn định trong (số lớn nhất các đỉnh đôi một không kề nhau). Trong bài báo này chúng tôi khảo sát các lớp đồ thị rộng hơn là các lớp đồ thị thỏa mãn . Chúng tôi chứng minh rằng khi đồ thị thỏa mãn  thì nó có chu trình Hamilton trừ một số lớp đồ thị đặc biệt có thể nhận biết trong thời gian đa thức.


Keywords


chu trình Hamilton, NPC, tough,



DOI: https://doi.org/10.15625/0866-708X/51/5/9619 Display counter: Abstract : 110 views. PDF (Tiếng Việt) : 800 views. PDF (Tiếng Việt) : 161 views.

Refbacks

  • There are currently no refbacks.


Index: Google Scholar; Crossref; VCGate; Asean Citation Index

Published by Vietnam Academy of Science and Technology