گراف نیمه همیلتونی (Semi-Hamiltonian Graph)، در ریاضیات (Mathematics)
انواع گراف همیلتونی (Hamiltonian Graph) را در آموزش زیر شرح دادیم :
گراف نیمه همیلتونی (Semi-Hamiltonian Graph) :
این نوع گراف، بر خلاف گراف همیلتونی، دور همیلتونی ندارد اما حداقل یک مسیر همیلتونی (Hamiltonian Path) در آن وجود دارد. مسیر همیلتونی مسیری است که از تمام رئوس گراف دقیقا یک بار عبور می کند، ولی لزومی ندارد که به نقطه شروع بازگردد (یال شروع و پایان یکی نیست). به عبارت دیگر، این گراف ها تمام رئوس را پوشش می دهند اما یک دور بسته ایجاد نمی کنند. برای مثال، یک مسیر ساده (Path graph) مانند
\[ P_n \]یک گراف نیمه همیلتونی است زیرا تمام رئوس را در یک خط پوشش می دهد اما دو راس ابتدا و انتها به هم متصل نیستند تا یک دور تشکیل شود. بسیاری از گراف ها ممکن است نیمه همیلتونی باشند بدون اینکه همیلتونی باشند. وجود یک مسیر همیلتونی نیز مانند دور همیلتونی یک مسئله NP-Complete است. در کاربردهای عملی، گاهی اوقات یافتن یک مسیر که از تمام نقاط عبور کند (بدون نیاز به بازگشت) کافی است، مانند برنامه ریزی برای بازدید از تمام شهرها بدون لزوم بازگشت به شهر مبدا.
