Войти
В теории графов изоморфизм графов G и H является биекция между множествами вершин графа G и H
так, что любые две вершины u и v из G смежны в G тогда и только тогда, когда f ( u) и f (v) смежны в H. Этот вид биекции обычно описывается как «биекция с сохранением ребер» в соответствии с общим понятием изоморфизма, являющегося сохраняющей структуру биекцией
Если между двумя графами существует изоморфизм, то графы называются изоморфными и обозначаются как 
Граф изоморфизм - это отношение эквивалентности на графах, и как таковое оно разделяет класс всех графов на классы эквивалентности. Набор графов, изоморфных друг другу, называется классом изоморфизма графов .
Два графика, показанные ниже, изоморфны, несмотря на их разный вид рисунков.
| График G | График H | Изоморфизм. между G и H |
|---|---|---|
 |  | f (a) = 1 f (b) = 6 f (c) = 8 f (d) = 3 f (g) = 5 f (h) = 2 f (i) = 4 f (j) = 7 |
В приведенном выше определении графики понимаются как однонаправленные немаркированные невзвешенные графики. Однако понятие изоморфности может быть применено ко всем другим вариантам понятия графа, добавляя требования для сохранения соответствующих дополнительных элементов структуры: направления дуг, веса ребер и т. Д., За следующим исключением.
Для помеченных графов используются два определения изоморфизма.
Согласно одному определению, изоморфизм - это биекция вершин, которая сохраняет одновременно ребра и метки.
Согласно другому определению, изоморфизм - это биекция вершин, сохраняющая ребра, которая сохраняет классы эквивалентности меток, то есть вершины с эквивалентными (например, одинаковыми) метками отображаются на вершины с эквивалентными метками и наоборот; то же самое с метками ребер.
Например, граф 
Второе определение предполагается в определенных ситуациях, когда графы снабжены уникальными метками, обычно взятыми из целого диапазона 1,..., n, где n - количество вершин графа, используемых только для однозначно идентифицировать вершины. В таких случаях два помеченных графа иногда называют изоморфными, если соответствующие базовые немеченые графы изоморфны (в противном случае определение изоморфизма было бы тривиальным).
Формальное понятие «изоморфизм», например, «изоморфизм графа», отражает неформальное представление о том, что некоторые объекты имеют «одинаковую структуру», если игнорировать индивидуальные различия «атомарных». «компоненты рассматриваемых объектов. Когда индивидуальность «атомарных» компонентов (вершин и ребер для графов) важна для правильного представления всего, что моделируется графами, модель уточняется путем наложения дополнительных ограничений на структуру и используются другие математические объекты: орграфы, маркированные графы, цветные графы, корневые деревья и так далее. Отношение изоморфизма также может быть определено для всех этих обобщений графов: биекция изоморфизма должна сохранять элементы структуры, которые определяют рассматриваемый тип объекта: дуги, метки, цвета вершин / ребер, корень корневое дерево и т. д.
Понятие «изоморфизм графа» позволяет нам отличать свойства графа, присущие структурам самих графов, от свойств, связанных с представлениями графов: чертежи графов, структуры данных для графов, разметки графов и т. Д. Например, если граф имеет ровно один цикл, то все графы в его классе изоморфизма также иметь ровно один цикл. С другой стороны, в общем случае, когда вершины графа (представлены) целыми числами 1, 2,... N, тогда выражение
может быть различным для двух изоморфных графов.
Исключение из теоремы Уитни: эти два графа не изоморфны, но имеют изоморфные линейные графы. Теорема об изоморфизме графов Уитни, показанная Хасслером Уитни утверждает, что два связанных графа изоморфны тогда и только тогда, когда их линейные графы изоморфны, за одним исключением: K 3, полный граф на трех вершинах и полный двудольный граф K 1,3, которые не изоморфны, но оба имеют K 3 в качестве линейного графа. Теорема Уитни о графах может быть расширена до гиперграфов.
Хотя изоморфизм графов можно изучать классическим математическим способом, как показано на примере теоремы Уитни, признано, что это проблема, которую нужно решать с помощью алгоритмического подхода. Вычислительная проблема определения изоморфности двух конечных графов называется проблемой изоморфизма графов.
Его практические применения включают в первую очередь хеминформатику, математическую химию (идентификацию химических соединений) и автоматизацию проектирования электроники (проверка эквивалентности различных изображения конструкции электронной схемы ).
Проблема изоморфизма графов - одна из немногих стандартных проблем в теории сложности вычислений, принадлежащих NP, но неизвестных как принадлежащих ни к одной из ее хорошо известных (и, если P ≠ NP, непересекающиеся) подмножества: P и NP-complete. Это одна из двух из 12 проблем, перечисленных в Garey Johnson (1979), сложность которой остается нерешенной, а другая - целочисленная факторизация. Однако известно, что если задача является NP-полной, то иерархия полиномов схлопывается до конечного уровня.
В ноябре 2015 года Ласло Бабай, математик и компьютерный ученый из Чикагского университета утверждал, что доказал, что проблема изоморфизма графов разрешима за квазиполиномиальное время. По состоянию на ноябрь 2015 года эта работа еще не проходила аттестацию. В январе 2017 года Бабай на короткое время отказался от утверждения о квазиполиномиальности и вместо этого указал субэкспоненциальное время временной сложности. Он восстановил первоначальную претензию через пять дней.
Ее обобщение, проблема изоморфизма подграфов, как известно, является NP-полной.
Основными направлениями исследования проблемы являются создание быстрых алгоритмов и теоретические исследования ее вычислительной сложности, как для общей задачи, так и для специальных классов графов.
