Изоморфизм графа

В теории графов изоморфизм графов G и H — это биекция между множествами вершин G и H.

{\ displaystyle f \ двоеточие V (G) \ to V (H)}

такие, что любые две вершины u и v из G смежны в G тогда и только тогда, когда и смежны в H . Этот вид биекции обычно описывается как «биекция, сохраняющая края», в соответствии с общим представлением об изоморфизме как биекции, сохраняющей структуру. Если между двумя графами существует изоморфизм , то графы называются изоморфными и обозначаются как . В случае, когда биекция является отображением графа на самого себя, т. е. когда G и H — один и тот же граф, биекция называется автоморфизмом G . Если граф конечен, мы можем доказать его биективность, показав, что он является «один-один»; нет необходимости показывать оба. Изоморфизм графов — это отношение эквивалентности на графах, которое разбивает класс всех графов на классы эквивалентности . Множество графов, изоморфных друг другу, называется классом изоморфизма графов. Вопрос о том, можно ли определить изоморфизм графов за полиномиальное время, является основной нерешенной проблемой в информатике, известной как проблема изоморфизма графов . ^[1]^[2] ${\ displaystyle f (u)}$ ${\ displaystyle f (v)}$ $G\simeq H$

Два графа, показанные ниже, изоморфны, несмотря на то, что они выглядят по-разному .

Вариации

В приведенном выше определении под графами понимаются неориентированные неразмеченные невзвешенные графы . Однако понятие изоморфизма можно применить ко всем остальным вариантам понятия графа, добавив требования сохранения соответствующих дополнительных элементов структуры: направлений дуг, весов ребер и т. д., за следующим исключением.

Изоморфизм помеченных графов

Для помеченных графов используются два определения изоморфизма.

Согласно одному определению, изоморфизм — это биекция вершин, которая сохраняет как ребра, так и метки. ^[3]^[4]

Согласно другому определению, изоморфизм — это сохраняющая ребра биекция вершин, которая сохраняет классы эквивалентности меток, т. е. вершины с эквивалентными (например, одинаковыми) метками отображаются на вершины с эквивалентными метками и наоборот; то же самое с краевыми метками. ^[5]

Например, граф с двумя вершинами, помеченными цифрами 1 и 2, согласно первому определению имеет один автоморфизм, но согласно второму определению существует два автоморфизма. $K_{2}$

Второе определение предполагается в определенных ситуациях, когда графы наделены уникальными метками, обычно взятыми из целочисленного диапазона 1,..., n , где n — количество вершин графа, используемое только для однозначной идентификации вершин. В таких случаях два помеченных графа иногда называют изоморфными, если соответствующие немаркированные графы изоморфны (в противном случае определение изоморфизма было бы тривиальным).

Мотивация

Формальное понятие «изоморфизма», например «изоморфизма графа», отражает неформальное представление о том, что некоторые объекты имеют «одинаковую структуру», если игнорировать индивидуальные различия «атомарных» компонентов рассматриваемых объектов. Всякий раз, когда индивидуальность «атомарных» компонентов (вершин и ребер для графов) важна для правильного представления всего, что моделируется графами, модель уточняется путем наложения дополнительных ограничений на структуру и используются другие математические объекты: орграфы , помеченные графы . , цветные графы , корневые деревья и так далее. Отношение изоморфизма также может быть определено для всех этих обобщений графов: биекция изоморфизма должна сохранять элементы структуры, которые определяют рассматриваемый тип объекта: дуги , метки, цвета вершин/ребер, корень корневого дерева и т. д.

Понятие «изоморфизм графов» позволяет отличать свойства графов, присущие структурам самих графов, от свойств, связанных с представлениями графов: рисунками графов , структурами данных для графов , разметками графов и т. д. Например, если граф имеет ровно один цикл , то все графы в его классе изоморфизма также имеют ровно один цикл. С другой стороны, в общем случае, когда вершины графа представляют собой целые числа 1, 2,... N , тогда выражение

\sum _{v\in V(G)}v\cdot {\text{deg }}v

может быть разным для двух изоморфных графов.

Теорема Уитни

Теорема об изоморфизме графа Уитни , ^[6] , показанная Хасслером Уитни , утверждает, что два связных графа изоморфны тогда и только тогда, когда их линейные графы изоморфны, за одним исключением: K ₃ , полный граф на трех вершинах и полный двудольный граф . граф K _1,3 , которые не изоморфны, но оба имеют K ₃ в качестве линейного графа. Теорема Уитни о графах может быть распространена на гиперграфы . ^[7]

Распознавание изоморфизма графов

Хотя изоморфизм графов можно изучать классическим математическим способом, примером которого является теорема Уитни, признается, что эту проблему следует решать с помощью алгоритмического подхода. Вычислительная задача определения изоморфности двух конечных графов называется проблемой изоморфизма графов.

Его практические приложения включают в первую очередь химинформатику , математическую химию (идентификацию химических соединений) и автоматизацию электронного проектирования (проверку эквивалентности различных представлений конструкции электронной схемы ).

Проблема изоморфизма графов — одна из немногих стандартных задач теории сложности вычислений , принадлежащих NP , но не принадлежащих ни к одному из ее хорошо известных (и, если P ≠ NP , непересекающихся) подмножеств: P и NP-полных . Это одна из двух из 12 задач, перечисленных в работе Гари и Джонсона (1979), сложность которых остается нерешенной, а вторая — целочисленная факторизация . Однако известно, что если задача NP-полна, то полиномиальная иерархия коллапсирует до конечного уровня. ^[8]

В ноябре 2015 года Ласло Бабай , математик и ученый-компьютерщик из Чикагского университета, заявил, что доказал, что проблема изоморфизма графов разрешима за квазиполиномиальное время . ^[9]^[10] Он опубликовал предварительные версии этих результатов в материалах Симпозиума по теории вычислений 2016 года , ^[11] и Международного конгресса математиков 2018 года . ^[12] В январе 2017 года Бабай ненадолго отказался от утверждения о квазиполиномиальности и вместо этого сформулировал субэкспоненциальную оценку временной сложности. Пять дней спустя он восстановил первоначальный иск. ^[13] По состоянию на 2020 год ^{[обновлять]}полная журнальная версия статьи Бабая еще не опубликована.

Ее обобщение, проблема изоморфизма подграфов , как известно, NP-полна.

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

Тест на изоморфизм графов Вейсфейлера-Лемана можно использовать для эвристической проверки изоморфизма графов. ^[14] Если тест не пройден, два входных графа гарантированно будут неизоморфными. Если тест пройден успешно, графы могут быть изоморфными, а могут и не быть. Существуют обобщения алгоритма тестирования, которые гарантированно обнаруживают изоморфизмы, однако время их выполнения экспоненциально.

Смотрите также

Примечания

^ Гроэ, Мартин (01 ноября 2020 г.). «Проблема изоморфизма графов». Коммуникации АКМ . 63 (11): 128–134. дои : 10.1145/3372123 . Проверено 6 марта 2023 г.{{cite journal}}: CS1 maint: дата и год ( ссылка )
^ Кларрайх, Эрика (14 декабря 2015 г.). «Ориентарный алгоритм выходит из 30-летнего тупика». Журнал Кванта . Проверено 6 марта 2023 г.
^ стр.424
^ «Эффективный метод проверки изоморфизма помеченных графов» в: Вычислительная наука и ее приложения - ICCSA 2006 , стр. 422–431.
^ Пьер-Антуан Шампен, Кристин Солнон, «Измерение сходства помеченных графов» в: Конспекты лекций по информатике , том. 2689, стр. 80–95.
^ Уитни, Хасслер (январь 1932 г.). «Конгруэнтные графы и связность графов». Американский журнал математики . 54 (1): 150–168. дои : 10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR 2371086.
^ Дирк Л. Вертиган, Джеффри П. Уиттл: Теорема о 2-изоморфизме для гиперграфов. Дж. Комб. Теория, сер. Б 71(2): 215–230. 1997.
^ Шёнинг, Уве (1988). «Изоморфизм графов находится в низкой иерархии». Журнал компьютерных и системных наук . 37 (3): 312–323. дои : 10.1016/0022-0000(88)90010-4.
↑ Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi : 10.1126/science.aad7416.
↑ Кларрайх, Эрика (14 декабря 2015 г.), «Веховой алгоритм выходит из 30-летнего тупика», журнал Quanta
^ Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальное время [расширенный аннотация]», STOC'16 — Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, Нью-Йорк, стр. 684–697, doi : 10.1145/2897518.2897542, МР 3536606, S2CID 17118954
^ Бабай, Ласло (2018), «Группы, графы, алгоритмы: проблема изоморфизма графов», Труды Международного конгресса математиков - Рио-де-Жанейро, 2018. Том. IV. Приглашенные лекции , World Sci. Публикация, Хакенсак, Нью-Джерси, стр. 3319–3336, MR 3966534.
^ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
^ Хуан, Нинъюань Тереза; Вильяр, Соледад (2021). «Краткое руководство по тесту Вейсфейлера-Лемана и его вариантам». ICASSP 2021–2021 Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) . стр. 8533–8537. arXiv : 2201.07083 . doi : 10.1109/ICASSP39728.2021.9413523. ISBN 978-1-7281-7605-5. S2CID 235780517.