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