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

Биекция между множеством вершин двух графов

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

${\displaystyle f\colon V(G)\to V(H)}$

такой, что любые две вершины u и v графа G смежны в G тогда и только тогда, когда и смежны в H. Этот вид биекции обычно описывается как «сохраняющая ребра биекция» в соответствии с общим понятием изоморфизма как сохраняющей структуру биекции. ${\displaystyle f(u)}$ ${\displaystyle f(v)}$

Если между двумя графами существует изоморфизм , то графы называются изоморфными и обозначаются как . В случае, когда изоморфизм является отображением графа на себя, т. е. когда G и H — один и тот же граф, изоморфизм называется автоморфизмом графа G . ${\displaystyle G\simeq H}$

Изоморфизм графов — это отношение эквивалентности на графах, и как таковое оно разбивает класс всех графов на классы эквивалентности . Набор графов, изоморфных друг другу, называется классом изоморфизма графов. Вопрос о том, можно ли определить изоморфизм графов за полиномиальное время, является основной нерешенной проблемой в информатике, известной как проблема изоморфизма графов . ^{[1] [2]}

Два графика, показанных ниже, изоморфны, несмотря на разный внешний вид .

Вариации

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

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

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

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

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

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

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

Мотивация

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

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

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

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

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

Исключение из теоремы Уитни: эти два графа не изоморфны, но имеют изоморфные линейные графы.

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

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

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

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

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

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

Известно, что ее обобщение, задача изоморфизма подграфов , является NP-полной.

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

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

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

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

• Гомоморфизм графа
• Проблема автоморфизма графа
• Проблема изоморфизма графов
• Канонизация графа

Примечания

1. Гроэ, Мартин (2020-11-01). «Проблема изоморфизма графов». Сообщения ACM . 63 (11): 128–134. doi :10.1145/3372123 . Получено 2023-03-06 .{{cite journal}}: CS1 maint: дата и год ( ссылка )
2. Кларрайх, Эрика (14.12.2015). «Знаменитый алгоритм выводит из 30-летнего тупика». Журнал Quanta . Получено 06.03.2023 .
3. стр.424
4. Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). "Эффективный метод выполнения проверки изоморфизма помеченных графов". Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science. Vol. 3984. pp. 422–431. doi :10.1007/11751649_46. ISBN 978-3-540-34079-9.
5. Пьер-Антуан Шампэн, Кристин Солнон, «Измерение сходства помеченных графов» в: Lecture Notes in Computer Science , т. 2689, стр. 80–95
6. Уитни, Хасслер (январь 1932 г.). «Конгруэнтные графы и связность графов». American Journal of Mathematics . 54 (1): 150–168. doi :10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR  2371086.
7. Дирк Л. Вертиган, Джеффри П. Уиттл: Теорема о 2-изоморфизме для гиперграфов. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
8. Шёнинг, Уве (1988). «Изоморфизм графов находится в низкой иерархии». Журнал компьютерных и системных наук . 37 (3): 312–323. doi :10.1016/0022-0000(88)90010-4.
9. Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , doi :10.1126/science.aad7416.
10. Кларрайх, Эрика (14 декабря 2015 г.), «Знаменитый алгоритм выводит из 30-летнего тупика», Quanta Magazine
11. Бабай, Ласло (2016), «Изоморфизм графов за квазиполиномиальное время [расширенный реферат]», STOC'16 — Труды 48-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, Нью-Йорк, стр. 684–697, doi :10.1145/2897518.2897542, ISBN 978-1-4503-4132-5, MR  3536606, S2CID  17118954
12. Бабай, Ласло (2018), "Группа, графы, алгоритмы: проблема изоморфизма графов", Труды Международного конгресса математиков — Рио-де-Жанейро 2018. Том IV. Приглашенные лекции , World Sci. Publ., Хакенсак, Нью-Джерси, стр. 3319–3336, MR  3966534
13. Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
14. Хуан, Нинюань Тереза; Виллар, Соледад (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.
15. Корделла, Л. П.; Фоджа, П.; Сансоне, К.; Венто, М. (2001). «Улучшенный алгоритм сопоставления больших графов». 3-й семинар IAPR-TC15 по графовым представлениям в распознавании образов : 149–159.

Ссылки

• Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676.