Хамилтонов пут

Из Википедије, слободне енциклопедије
Хамилтонов пут (црно) над графом (плаво).

У области математике, теорији графова, Хамилтонов пут је пут у неусмереном графу који посећује сваки чвор тачно једном. Хамилтонов цикл је цикл у неусмереном графу који посећује сваки чвор тачно једном. Одређивање да ли такав пут или циклус постоје у датом графу је проблем Хамилтоновог пута. Овај проблем је НП-комплетан.

Хамилтонов пут и цикл су добили име по ирском математичару Вилијаму Роуану Хамилтону.

Види још[уреди]


Спољашње везе[уреди]