Проблем изоморфизма графа
У теоријском рачунарству, проблем изоморфизама подграфа је рачунски задатак у којем су два графикона 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 фиксиран, време извршавања алгоритма може да се редукује до линеарног.

Литература 

 .
 .
 . A1.4: GT48, pp. 202.
 .
 .
 .
 .
 .
 .
 .

НП-комплетни проблеми
Графовски алгоритми
Рачунарски проблеми у теорији графова
У теоријском рачунарству , проблем изоморфизама подграфа је рачунски задатак у којем су два графикона G и H дата као улаз , и он мора се утврдити да ли G садржи подграф који је изоморфна H . Изоморфизам подграфа је генерализација два алгоритма , алгоритма за одређивање проблема клике и проблема испитивања да ли граф садржи Хамилтонов пут , па је стога НП-комплетан . Решење проблема и рачунарска комплексност Питање : Нека су , два графа . Да ли постоји подграф такав да је ? тј. да ли постоји тако да је ? Да би се доказало да је проблем НП-комплетан , мора бити формулисан као проблем одлучивања . Улаз ће онда представљати пар графова G и H . Одговор на проблем је позитиван ако је H изоморфни подграф од G , а иначе је негативан . Доказ да је овај проблрм НП-комплетан је једноставан и заснива се на сужавању проблема клика . То је НП-комплетан проблем одлучивања , у којима је улаз један граф G и број к , и питање је да ли G садржи комплетан подграф са к темена . Да би се овај проблем киле превео на нас проблем , довољно је да је H комплетан граф за Кk , онда је одговор на проблем за G и H једнак одговорu на клика проблем за G и к . Пошто је клика проблем је НП-комплетан онда је проблем изоморфизма подграфа такође је НП-комплетан јер представља сужавање проблеме клике . Други начин да се види да је проблем НП-комплетан је тај што проблем Хамилтоновог циклуса представља уопштење нашег проблема , а тај проблем јесте НП-комплетан , па је и овај НП-комплетан . Изоморфизам подграфа је генерализација проблема изоморфизам графа , који пита да ли је G изоморфна H : одговор на проблем изоморфизма графова важи ако и само ако G и H имају исти број темена и тада проблем изоморфизама подграфа за Г и Х је тачан . Међутим , теоријска сложеност овог проблема остаје отворено питање . Показало се да је сложеност овог проблема Ω( n3 /2 ) . Алгоритам Улманописује рекурзивну бектрекинг процедуру за решавање овог проблема . Иако му је време извршавања , у општем случају , експоненцијалне сложености , потребно је полиномијално време када би фиксирали H ( са полинома који зависи од избора H ) . Када је G планаран и H фиксиран , време извршавања алгоритма може да се редукује до линеарног . Литература \ . \ . \ . A1.4 : GT48 , pp . \ . \ . \ . \ . \ . \ . \ . НП-комплетни проблеми Графовски алгоритми Рачунарски проблеми у теорији графова