Проблем Хамилтоновог пута

Из Википедије, слободне енциклопедије

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

Постоји проста релација између ова два проблема. Проблем Хамилтоновог пута за граф G је еквивалентан проблему Хамилтоновог циклуса за граф H који се добија из G додавањем новог чвора, и спајањем тог новог чвора са свим чворовима из G.

Проблем Хамилтоновог циклуса је специјални случај проблема трговачког путника, добијеног постављањем раздаљине између два града на коначну константу ако су суседни, а у супротном на бесконачно.

Усмерени и неусмерени проблеми Хамилтоновог циклуса су били два од 21 Карпових НП-комплетних проблема. Гери и Џонсон су убрзо затим, 1974, показали да проблем Хамилтоновог циклуса остаје НП-комплетан и за планарне графове а да неусмерени проблем Хамилтоновог циклуса остаје НП-комплетан за кубне планарне графове.

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

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

Литература[уреди]