Сложность поиска подграфа в графе

Sander

собственно субж ,
а точнее ---
Чему равна алгоритмическая сложность поиска инъективного отображения одного рафа в другой,
графы --- ориентированные, ребра помечены символами к-либо конечного алфавита, типа \Sigma
Другими словами ---
даны два графа --- G и H
Алг. сложность поиска в графе G подграфа, изомор графу H.
еще если кто может с легкостью сказать --- такой вопрос --- если речь идет не об иньективном отображении, то есть не об изоморфизме (наверное об голоморфизме (по-моему это так называется то меняются ли оценки сложности
на самом деле я вроде знаю ответ, но все-таки это мое собственное изобретение --- может у кого-нибудь есть какая-нибудь литература, где это
все посчитано или оценено?
заранее благодарен за ответ

Xephon

это проблема класса NP
переборный алгоритм очевиден

Sander

Сенькью вери матч блин! но я в курсе что это NP-полная задачя
а это значит, что алгоритмическая сложность -- НЕ полиномиальная.
а это по-моему не отвен на вопрос.
у меня получилось что-то вроде
O(|G|^|H|) (может буквы здесь местами перепутал -- голова не варит совсем уже)

kravecnata

Ну уж добавил бы, что задача "Изоморфизм подграфу" NP-полна.
(И она была в списке NP-полных задач из первоначальной статьи Кука.)

kravecnata

Так ты скажи внятно, чего хочешь. Оценки для наилучшего известного алгоритма? Такое тебе навскидку почти наверняка никто не скажет, рой литературу.

Xephon

> а это значит, что алгоритмическая сложность -- НЕ полиномиальная
я бы с удовольствием выслушал доказательство

Sander

Хочу я как раз того, что если кто -то этим занимается и разбирается,
что бы он мне сказал оценку какого-либо
не обязательно самого лучшего, можно даже самого тупого
алгоритма поиска.
Ну или в крайнем случае ссылку на литературу , лучше правда ссылку на что-нибудь в инете.
но по-моему это все мечты -- ни кто действительно не скажет.
просто до понедельника ждать не охота (к аучнику пойду)

kravecnata

Вероятность, что кто-то из форума занимается этой конкретной задачей, действительно невелика. Но что тебе мешает набрать subgraph isomorphism в Google и наслаждаться?

Sander

Мешает к сожалению неважное знание английского ---
что-то не догадался именно так перевести
и то, что сегодня весь день ботаю, так что
уже почти опух
а за совет спасибо
--- жаль в рунете я ни чего не смог по этой теме найти

kolj57

Аналогично.
Насколько мне известно - P!=NP все еще открытая проблема.

anna13

Тут стоит не жтот вопрос. А вопрос о том к какому классу принадлежит конкретно эта задача...

kolj57

Ну...
Выше же написано, что она NP полна. Значит, существование полиномиального алгоритма опять таки сводится к вопросу P != NP.
Вам замечание (+). Неуместный мат.

Sander

могу уточнить еще раз :
Внимание вопрос:
Есть ли какие-нибудь оценки сложности поиска подграфа в графе?
--- не важно какого алгоритма т.к. самого лучшего не существует,
но хотя бы какого-нибудь, пусть переборного.
нужна оценка, в виде f (G,F)

да, задача относится к классу NP-полных, и это уже было сказано --- в этом сомнений (по крайней мере у меня) не возникает.

viktor961

А что за научрук, не Афон случайно ?

viktor961

И оценка (A^B) вроде простая, простой перебор если я еще не сплю.

Sander

Ну да, он самый.
ну слава богу - хоть кто-то что то сказал !
на самом деле, у меня конечно такая же получилась.
ну ладно... забить на эту оценку, может он что-нибудь и скажет завтра, хотя скорее всего тоже самое скажет

viktor961

Предай что я не приду, у меня срочные дела.

Sander

offtop
Как ему сказать точно --- "Он не приедет!"
ну хоть бы сказал кто ты? (ТAS --- это мне ни о чем не говорит )

viktor961

Если я правильно понял кто ты, то я тебе должен
был рассказать про кластеризацию по матрице расстояния.
Если я ошибся, то прости. А кто такой TAS они поймут.
Кстати задача про "поиск подграфа в графе" вроде больше операций
чем O(|A|^|B|) (оценка сверху). Там еще может возникнуть
неопределенность если одной вершины исходит несколько
одинаковых ветвей.

Sander

Да , все, я понял
я просто твоих инициалов не знал,
а что не расскажешь --- жаль,
может здесь
в общем запутался я с жи тупям поиском, а думать не охота --- завтра у Афонина спрошу
вдруг расскажет, хотя обычно его ломает.
Оставить комментарий
Имя или ник:
Комментарий: