Проблем изоморфизма графа

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

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

Решење проблема и рачунарска комплексност[уреди]

Питање:

Нека су , два графа. Да ли постоји подграф такав да је ? тј. да ли постоји тако да је ?

Да би се доказало да је проблем НП-комплетан, мора бити формулисан као проблем одлучивања. Улаз ће онда представљати пар графова G и H. Одговор на проблем је позитиван ако је H изоморфни подграф од G, а иначе је негативан.

Доказ да је овај проблрм НП-комплетан је једноставан и заснива се на сужавању проблема клика. То је НП-комплетан проблем одлучивања, у којима је улаз један граф G и број к, и питање је да ли G садржи комплетан подграф са к темена. Да би се овај проблем киле превео на нас проблем, довољно је да је H комплетан граф за Кk, онда је одговор на проблем за G и H једнак одговорu на клика проблем за G и к. Пошто је клика проблем је НП-комплетан онда је проблем изоморфизма подграфа такође је НП-комплетан јер представља сужавање проблеме клике.

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

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

Показало се да је сложеност овог проблема Ω(n3/2).

Алгоритам[уреди]

Улман (1976) описује рекурзивну бектрекинг процедуру за решавање овог проблема. Иако му је време извршавања , у општем случају, експоненцијалне сложености, потребно је полиномијално време када би фиксирали H (са полинома који зависи од избора H). Када је G планаран и H фиксиран, време извршавања алгоритма може да се редукује до линеарног.

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