1294
правки
Задача изоморфизма графов: различия между версиями
Перейти к навигации
Перейти к поиску
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:15, 25 ноября 2024
, 25 ноября 2024→Ключевые слова и синонимы
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 18 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
'''Задача изоморфизма графов''' --- ''Graph isomorphism problem'' | |||
Паросочетания в графах (''Graph matching''); Группы симметрии (''Symmetry group'') | |||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 14: | Строка 16: | ||
Пусть даны два графа <math>G_1 = (V_1, E_1) \; </math> и <math>G_2 = (V_2, E_2) \;</math>. Изоморфизм графа <math>G_1 \;</math> на <math>G_2 \;</math> представляет собой биекцию <math>V_1 \;</math> на <math>V_2 \;</math>, такую, что она порождает биекцию <math>E_1 \;</math> на <math>E_2 \;</math>. Если <math>G_1 = G_2 \; </math>, то изоморфизм является автоморфизмом <math>G_1 \;</math>. Множество всех автоморфизмов <math>G_1 \;</math> образует группу относительно операции композиции, называемую группой автоморфизмов <math>G_1 \; </math> и обозначаемую <math>Aut(G_1) \;</math>. | Пусть даны два графа <math>G_1 = (V_1, E_1) \; </math> и <math>G_2 = (V_2, E_2) \;</math>. Изоморфизм графа <math>G_1 \;</math> на <math>G_2 \;</math> представляет собой биекцию <math>V_1 \;</math> на <math>V_2 \;</math>, такую, что она порождает биекцию <math>E_1 \;</math> на <math>E_2 \;</math>. Если <math>G_1 = G_2 \; </math>, то изоморфизм является автоморфизмом <math>G_1 \;</math>. Множество всех автоморфизмов <math>G_1 \;</math> образует группу относительно операции композиции, называемую группой автоморфизмов <math>G_1 \; </math> и обозначаемую <math>Aut(G_1) \;</math>. | ||
На рис. 1 представлены два изоморфных графа, а также изоморфизм между ними и группа автоморфизмов первого графа. | На рис. 1 представлены два изоморфных графа, а также изоморфизм между ними и группа автоморфизмов первого графа. | ||
[[Файл:Graph_Isom_1.jpg]] | |||
Рис. 1. Пример изоморфизма и группы изоморфизмов | |||
| Строка 21: | Строка 28: | ||
Альтернативу представляет | Альтернативу представляет алгоритм [[каноническая разметка|канонической разметки]]. Его идея заключается в следующем: в каждом классе изоморфизмов имеется уникальный канонический граф, который может быть найден алгоритмом, получившим на входе любой граф класса изоморфизмов. Каноническим графом может быть, например, наименьший граф в классе изоморфизмов согласно какому-либо упорядочению (к примеру, лексикографическому). Практические алгоритмы обычно вычисляют каноническую форму с прицелом на эффективность, а не простоту описания. | ||
== Основные результаты == | == Основные результаты == | ||
Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем | Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем выполнения известны для многих специальных классов графов – в частности, графов ограниченного рода, графов с ограниченной степенью, ограниченной древесной шириной и ограниченной кратностью собственного значения. Самый быстрый теоретический алгоритм для графов общего вида требует <math>exp(n^{1/2+o(1)}) \; </math> времени [1], однако нет сведений о его практичности. | ||
В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в [ ]. Известно [7], что она имеет экспоненциальное время | В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в статье [5]. Известно [7], что она имеет экспоненциальное время выполнения в наихудшем случае, но на практике этот наихудший случай встречается редко. | ||
| Строка 38: | Строка 41: | ||
Поддерживаются две структуры данных для графов: упакованная матрица смежности, подходящая для небольших плотных графов, и список указателей, подходящий для больших разреженных графов. | Поддерживаются две структуры данных для графов: упакованная матрица смежности, подходящая для небольших плотных графов, и список указателей, подходящий для больших разреженных графов. | ||
== Применение == | == Применение == | ||
| Строка 45: | Строка 47: | ||
Изоморфизм графов с раскрашенными ребрами | Изоморфизм графов с раскрашенными ребрами | ||
Изоморфизм двух графов – имеющих как раскрашенные вершины, так и раскрашенные ребра – определяется очевидным образом. Пример такого графа приведен на рис. 2. | Изоморфизм двух графов – имеющих как раскрашенные вершины, так и раскрашенные ребра – определяется очевидным образом. Пример такого графа приведен на рис. 2. | ||
| Строка 51: | Строка 54: | ||
В общем случае, если цвета ребер обозначены целыми числами {1; 2... , | В общем случае, если цвета ребер обозначены целыми числами <math> \{ 1; 2,... , 2^d - 1 \} \; </math>, имеются d уровней, и двоичное разложение каждого числа, обозначающего цвет, определяет, какие уровни содержат ребра. Вертикальные потоки (каждый из которых соответствует одной вершине исходного графа) могут связываться посредством путей либо клик. Если исходный граф имел n вершин и k цветов, новый граф будет иметь <math>O(n \; log \; k)</math> вершин. Это значение может быть улучшено до <math>O(n \sqrt {log k} ) \;</math> вершин в случае использования негоризонтальных ребер. | ||
[[Файл:Graph_Isom_2.jpg]] | |||
Рис. 2. Изоморфизм графов с раскрашенными ребрами | |||
Изоморфизм графов с раскрашенными ребрами | |||
Изоморфизм гиперграфов и схем | |||
Изоморфизм гиперграфов | |||
[[Гиперграф]] похож на неориентированный граф, за исключением того, что ребра могут представлять собой множества вершин любой величины, а не только величины 2. Подобная структура также называется [[схема|схемой]]. | |||
Гиперграф похож на неориентированный граф, за исключением того, что ребра могут представлять собой множества вершин любой величины, а не только величины 2. Подобная структура также называется схемой. | |||
В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | В левой части рисунка 3 представлен гиперграф с пятью вершинами, двумя ребрами величины 2 и одним ребром величины 3. Справа представлен эквивалентный ему граф с раскрашенными вершинами. Вершины слева, раскрашенные в один цвет, представляют ребра гиперграфа; вершины справа, раскрашенные в другой цвет, представляют дуги гиперграфа. Ребра графа обозначают отношение инцидентности (включения) гиперграфа. | ||
[[Файл:Graph_Isom_3.jpg]] | |||
Рис. 3. Изоморфизм гиперграфов/схем как изоморфизм графов | |||
Матрица инцидентности ребер и вершин изображена в центральной части рисунка. Ею может быть любая бинарная матрица, позволяющая корректно отобразить тот факт, что рассматриваемая задача заключается в определении эквивалентности матриц (0, 1) при независимой перестановке строк и столбцов. Сочетая эту идею с предыдущей конструкцией, можно поддерживать подобное отношение эквивалентности на множестве матриц с произвольными значениями. | Матрица инцидентности ребер и вершин изображена в центральной части рисунка. Ею может быть любая бинарная матрица, позволяющая корректно отобразить тот факт, что рассматриваемая задача заключается в определении эквивалентности матриц (0, 1) при независимой перестановке строк и столбцов. Сочетая эту идею с предыдущей конструкцией, можно поддерживать подобное отношение эквивалентности на множестве матриц с произвольными значениями. | ||
== Другие примеры == | == Другие примеры == | ||
Несколько примеров применения таких операций эквивалентности, как изотопия, имеющих важное значение для латинских квадратов и квазигрупп, можно найти в [6]. | Несколько примеров применения таких операций эквивалентности, как изотопия, имеющих важное значение для латинских квадратов и квазигрупп, можно найти в [6]. | ||
Еще один важный тип эквивалентности связывает матрицы посредством {-1,+1}. Помимо перестановки строк и столбцов, он позволяет умножать столбцы и строки на -1. Преобразование подобной задачи эквивалентности Адамара в задачу определения изоморфизма графов предложено в [4]. | Еще один важный тип эквивалентности связывает матрицы посредством {-1,+1}. Помимо перестановки строк и столбцов, он позволяет умножать столбцы и строки на -1. Преобразование подобной задачи [[эквивалентность Адамара|эквивалентности Адамара]] в задачу определения изоморфизма графов предложено в [4]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Программа nauty позволяет выбирать между разреженными и плотными структурами данных и предлагает специальные варианты для некоторых конкретных сложных классов графов. В следующих примерах лучшие результаты были получены на единичном процессоре Intel Core-duo с тактовой частотой 2,4 ГГц. | Программа nauty позволяет выбирать между разреженными и плотными структурами данных и предлагает специальные варианты для некоторых конкретных сложных классов графов. В следующих примерах лучшие результаты были получены на единичном процессоре Intel Core-duo с тактовой частотой 2,4 ГГц. | ||
1. Граф произвольного вида с 10 000 вершин, p = | 1. Граф произвольного вида с 10 000 вершин, p = 1/2: 0,014 с. только для групп, 0,4 с. – с учетом канонической разметки. | ||
2. Произвольный кубический граф с 100 000 вершин: 8 с. | 2. Произвольный кубический граф с 100 000 вершин: 8 с. | ||
3. 1-мерный остов 20- | 3. 1-мерный остов 20-мерного куба (1 048 576 вершин, размер группы <math>2,5 \times 10^{24}</math>): 92 с. | ||
4. 3-мерная сетка размера 50 (125 000 вершин): 0,7 с. | 4. 3-мерная сетка размера 50 (125 000 вершин): 0,7 с. | ||
| Строка 91: | Строка 93: | ||
Примеры более сложных графов можно найти в документации программы nauty. | Примеры более сложных графов можно найти в документации программы nauty. | ||
== Ссылка на код == | == Ссылка на код == | ||
Исходный код nauty доступен по адресу http://cs.anu. edu.au/~bdm/nauty/. Еще одна реализация фрагмента nauty, посвященного группам автоморфизмов и оптимизированного для больших разреженных графов, доступна под названием saucy [ ]. Nauty входит в состав множества пакетов общего назначения, включая GAP, Magma и MuPad. | Исходный код nauty доступен по адресу http://cs.anu.edu.au/~bdm/nauty/. Еще одна реализация фрагмента nauty, посвященного группам автоморфизмов и оптимизированного для больших разреженных графов, доступна под названием saucy [2]. Nauty входит в состав множества пакетов общего назначения, включая GAP, Magma и MuPad. | ||
== См. также == | == См. также == | ||
| Строка 118: | Строка 118: | ||
8. Toran, J.: On the hardness of graph isomorphism. SIAM J. Comput. 33,1093-1108 (2004) | 8. Toran, J.: On the hardness of graph isomorphism. SIAM J. Comput. 33,1093-1108 (2004) | ||
[[Категория: Совместное определение связанных терминов]] | |||