Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов , изоморфизм графов G и H является взаимно однозначное соответствие между множествами вершин G и H

таким образом, чтобы любые две вершины U и V из G являются смежными в G тогда и только тогда , когда и смежны в H . Этот вид биекции обычно описывается как «биекция, сохраняющая ребра», в соответствии с общим понятием изоморфизма, являющегося биекцией, сохраняющей структуру.

Если между двумя графами существует изоморфизм , то графы называются изоморфными и обозначаются как . В том случае , когда биекция является отображение графика на себя, то есть, когда G и Н являются одним и тем же граф, биекция называется автоморфизм из G .

Изоморфизм графов - это отношение эквивалентности на графах, и как таковой он разбивает класс всех графов на классы эквивалентности . Набор графов, изоморфных друг другу, называется классом изоморфизма графов.

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

График GГрафик HИзоморфизм
между G и H
Изоморфизм графов a.svgИзоморфизм графов b.svgf ( а ) = 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]

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

Например, граф с двумя вершинами, помеченными цифрами 1 и 2, имеет один автоморфизм при первом определении, но при втором определении есть два автоморфизма.

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

Мотивация [ править ]

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

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

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

Теорема Уитни [ править ]

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

Уитни изоморфизм графов теорема , [4] показано Hassler Уитни , утверждает , что две связные графы изоморфны тогда и только тогда , когда их линейные графики изоморфны, с одним исключением: K 3 , в полном графе на трех вершинах, и полный двудольный граф K 1,3 , которые не изоморфны, но оба имеют K 3 в качестве линейного графа. Теорема Уитни о графах может быть распространена на гиперграфы . [5]

Распознавание изоморфизма графов [ править ]

Основная статья: Проблема изоморфизма графов

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

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

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

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

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

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

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

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

Заметки [ править ]

  1. ^ стр.424
  2. ^ «Эффективный метод для выполнения проверки изоморфизма помеченных графов» в: Вычислительная наука и ее приложения - ICCSA 2006 , стр 422–431
  3. Перейти ↑ Pierre-Antoine Champ in, Christine Sol-non, «Измерение сходства помеченных графов» в: Lecture Notes in Computer Science , vol. 2689, стр 80–95
  4. ↑ Уитни, Хасслер (январь 1932 г.). «Конгруэнтные графы и связность графов». Американский журнал математики . 54 (1): 150–168. DOI : 10.2307 / 2371086 . hdl : 10338.dmlcz / 101067 . JSTOR  2371086 .
  5. ^ Дирк Л. Вертиган, Джеффри П. Уиттл: теорема о 2-изоморфизме для гиперграфов. J. Comb. Теория, сер. В 71 (2): 215–230. 1997 г.
  6. ^ Шёнинг, Уве (1988). «Изоморфизм графов находится в низшей иерархии». Журнал компьютерных и системных наук . 37 (3): 312–323. DOI : 10.1016 / 0022-0000 (88) 90010-4 .
  7. ↑ Чо, Адриан (10 ноября 2015 г.), «Математик заявляет о прорыве в теории сложности», Science , DOI : 10.1126 / science.aad7416.
  8. ^ Klarreich, Erica (14 декабря 2015), "Landmark Алгоритм Перерывы 30-летний IMPASSE" , Quanta Magazine
  9. ^ Бабай, Ласло (2016), «Изоморфизм графов в квазиполиномиальном времени [расширенная аннотация]», STOC'16 - Материалы 48-го ежегодного симпозиума ACM SIGACT по теории вычислений , ACM, Нью-Йорк, стр. 684–697, doi : 10.1145 / 2897518.2897542 , MR 3536606 
  10. ^ Бабай, Ласло (2018), «Группа, графы, алгоритмы: проблема изоморфизма графов», Труды Международного конгресса математиков - Рио-де-Жанейро 2018. Vol. IV. Приглашенные лекции , World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR 3966534. 
  11. ↑ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов

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

  • Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5