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

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

f\colon V(G)\to V(H)

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

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

График Ж	График Н	Изоморфизм между G и H
		ж ( а ) знак равно 1 ж ( б ) знак равно 6 ж ( с ) знак равно 8 ж ( d ) знак равно 3 ж ( г ) знак равно 5 ж ( час ) знак равно 2 ж ( я ) знак равно 4 ж ( j ) знак равно 7

Вариации [ править ]

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

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

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

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

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

Например, $K_{2}$ Граф с двумя вершинами, помеченными цифрами 1 и 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] По состоянию на 2024 год ^[update]Полная журнальная версия статьи Бабая еще не опубликована.

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

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

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

Другим известным алгоритмом изоморфизма графов является алгоритм vf2, разработанный Корделлой и др. в 2001 году. ^[15] Алгоритм vf2 — это алгоритм поиска в глубину, который пытается постепенно построить изоморфизм между двумя графами. Он использует набор правил осуществимости для сокращения пространства поиска, что позволяет эффективно обрабатывать графы с тысячами узлов. Алгоритм vf2 широко используется в различных приложениях, таких как распознавание образов, компьютерное зрение и биоинформатика. Несмотря на то, что он имеет экспоненциальную временную сложность в худшем случае, на практике он хорошо работает для многих типов графов.

См. также [ править ]

Примечания [ править ]

^ Гроэ, Мартин (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. Vol. IV. Приглашенные лекции , World Sci. Публикация, Хакенсак, Нью-Джерси, стр. 3319–3336, MR 3966534.
^ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
^ Хуан, Нинъюань Тереза; Вильяр, Соледад (2021). «Краткое руководство по тесту Вейсфейлера-Лемана и его вариантам». ICASSP 2021–2021 Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) . стр. 8533–8537. arXiv : 2201.07083 . дои : 10.1109/ICASSP39728.2021.9413523 . ISBN 978-1-7281-7605-5 . S2CID 235780517 .
^ Корделла, LP; Фоджа, П.; Сансоне, К.; Венто, М. (2001). «Улучшенный алгоритм сопоставления больших графов» . 3-й семинар IAPR-TC15 по представлениям на основе графов в распознавании образов : 149–159.

Ссылки [ править ]

Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 .

[1] Гроэ, Мартин (01 ноября 2020 г.). «Проблема изоморфизма графов» . Коммуникации АКМ . 63 (11): 128–134. дои : 10.1145/3372123 . Проверено 6 марта 2023 г. {{cite journal}}: CS1 maint: дата и год ( ссылка )

[2] Кларрайх, Эрика (14 декабря 2015 г.). «Алгоритм ориентира выходит из 30-летнего тупика» . Журнал Кванта . Проверено 6 марта 2023 г.

[3] стр.424

[4] «Эффективный метод проверки изоморфизма помеченных графов» в: Вычислительная наука и ее приложения - ICCSA 2006 , стр. 422–431.

[5] Пьер-Антуан Шампен, Кристин Солнон, «Измерение сходства помеченных графов» в: Конспекты лекций по информатике , том. 2689, стр. 80–95.

[6] Уитни, Хасслер (январь 1932 г.). «Конгруэнтные графы и связность графов». Американский журнал математики . 54 (1): 150–168. дои : 10.2307/2371086 . hdl : 10338.dmlcz/101067 . JSTOR 2371086 .

[7] Дирк Л. Вертиган, Джеффри П. Уиттл: Теорема о 2-изоморфизме для гиперграфов. Дж. Комб. Теория, сер. Б 71(2): 215–230. 1997.

[8] Шенинг, Уве (1988). «Изоморфизм графов находится в низкой иерархии». Журнал компьютерных и системных наук . 37 (3): 312–323. дои : 10.1016/0022-0000(88)90010-4 .

[9] Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi : 10.1126/science.aad7416 .

[10] Кларрайх, Эрика (14 декабря 2015 г.), «Веховой алгоритм выходит из 30-летнего тупика» , журнал Quanta

[11] Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальное время [расширенный аннотация]», STOC'16 — Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, Нью-Йорк, стр. 684–697, doi : 10.1145 /2897518.2897542 , МР 3536606 , S2CID 17118954

[12] Бабай, Ласло (2018), «Группы, графы, алгоритмы: проблема изоморфизма графов», Труды Международного конгресса математиков - Рио-де-Жанейро, 2018. Vol. IV. Приглашенные лекции , World Sci. Публикация, Хакенсак, Нью-Джерси, стр. 3319–3336, MR 3966534.

[13] Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов

[14] Хуан, Нинъюань Тереза; Вильяр, Соледад (2021). «Краткое руководство по тесту Вейсфейлера-Лемана и его вариантам». ICASSP 2021–2021 Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) . стр. 8533–8537. arXiv : 2201.07083 . дои : 10.1109/ICASSP39728.2021.9413523 . ISBN 978-1-7281-7605-5 . S2CID 235780517 .

[15] Корделла, LP; Фоджа, П.; Сансоне, К.; Венто, М. (2001). «Улучшенный алгоритм сопоставления больших графов» . 3-й семинар IAPR-TC15 по представлениям на основе графов в распознавании образов : 149–159.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]