Этот вопрос возникает из чистого любопытства (он возник, когда я думал о том, чтобы отменить перетасовку строки , но я не уверен, действительно ли это связано), поэтому я надеюсь, что это уместно.
Существуют различные графические продукты, и я заинтересован в любом из них здесь. В чем сложность определения того, является ли граф изоморфным нетривиальному произведению? (Конечно, для декартового произведения где - граф с одной вершиной.)K = K ◻ 1
Я посмотрел на страницах «Фактор графа» и «График факторизации» в Википедии, но ни один из них, похоже, не связан. Эта проблема известна под другим именем?
источник
Несколько графовых произведений могут быть распознаны за полиномиальное время. Как обычно, декартово произведение является самым простым, и декартово число также является основой для алгоритмов для нескольких других произведений. Распознавание лексикографического произведения (композиции) эквивалентно изоморфизму графа.
Более детально:
ПустьΓ - класс конечных простых графов, а Γ0 - класс конечных простых графов, которые могут иметь самоконтроли. (Понятно Γ ⊂ Γ0 .)
Решение о том, имеет ли связанный входной граф факторы в может быть за полиномиальное время для декартовых и сильных произведений, а также для прямого произведения, когда не двудольный. Решение о том, имеет ли факторы в принимается за полиномиальное время для декартового произведения, но вряд ли будет за полиномиальное время для лексикографического произведения. Я не знаю статус решения, если имеет факторы в для прямых и сильных продуктов.Γ 0 G G Γ G ΓG Γ0 G G Γ G Γ
Соответствующие результаты от Имрича и Клавжара:
Затем результат для декартового произведения улучшается до времени и пространства в главе 7. Как указывалось в других ответах, с тех пор оно было улучшено до линейного времени.O ( м )O(mlogn) O(m)
Для лексикографического продукта:
Поэтому решение о том, является ли граф простым по отношению к лексикографическому произведению, эквивалентно изоморфизму ГРАФА в отношении сокращений по Тьюрингу.
Случай с прямым и сильным произведением, имеющим факторы без самопетлей, по-видимому, отсутствует в ссылках, на которые я смотрел. Я был бы признателен за любые ссылки на статьи, которые обсуждают это дело, или подсказку, почему это неинтересно.
источник
Существует линейно-временной алгоритм определения простых множителей связных графов относительно декартового произведения. Смотрите статью Имрича и Петерина.
источник