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

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

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

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

Питање:

Нека су G=(V,E), H=(V^\prime,E^\prime) два графа. Да ли постоји подграф G_0=(V_0,E_0): V_0\subseteq V, E_0=E\cap(V\times V) такав да је G_0\cong H? тј. да ли постоји \varphi:V_0\rightarrow V^\prime тако да је (v_1,v_2)\in E_0\Leftrightarrow (f(v_1),f(v_2))\in E^\prime?

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

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

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

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

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

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

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

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