4551
правка
Задача изоморфизма графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:20, 21 апреля 2015
, 21 апреля 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
== Основные результаты == | == Основные результаты == | ||
Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем исполнения известны для многих специальных классов графов – в частности, графов ограниченного рода, графов с ограниченной степенью, ограниченной древесной шириной и ограниченной кратностью собственного значения. Самый быстрый теоретический алгоритм для графов общего вида требует exp( | Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем исполнения известны для многих специальных классов графов – в частности, графов ограниченного рода, графов с ограниченной степенью, ограниченной древесной шириной и ограниченной кратностью собственного значения. Самый быстрый теоретический алгоритм для графов общего вида требует <math>exp(n^{1/2+o(1)})</math> времени [1], однако нет сведений о его практичности. | ||
| Строка 38: | Строка 38: | ||
Поддерживаются две структуры данных для графов: упакованная матрица смежности, подходящая для небольших плотных графов, и список указателей, подходящий для больших разреженных графов. | Поддерживаются две структуры данных для графов: упакованная матрица смежности, подходящая для небольших плотных графов, и список указателей, подходящий для больших разреженных графов. | ||
== Применение == | == Применение == | ||