1313
правок
Задача изоморфизма графов: различия между версиями
Материал из WEGA
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:15, 25 ноября 2024
, 25 ноября 2024→Ключевые слова и синонимы
Irina (обсуждение | вклад) м (→Применение) |
KVN (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
'''Задача изоморфизма графов''' --- ''Graph isomorphism problem'' | |||
Паросочетания в графах (''Graph matching''); Группы симметрии (''Symmetry group'') | |||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 29: | Строка 31: | ||
== Основные результаты == | == Основные результаты == | ||
Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем | Задача определения изоморфизма графов играет ключевую роль в современной теории сложности вычислений. Неизвестно, является ли она разрешимой за полиномиальное время, NP-полной или принадлежащей к классу co-NP. Подробнее об этом в работах [3] и [8]. Алгоритмы с полиномиальным временем выполнения известны для многих специальных классов графов – в частности, графов ограниченного рода, графов с ограниченной степенью, ограниченной древесной шириной и ограниченной кратностью собственного значения. Самый быстрый теоретический алгоритм для графов общего вида требует <math>exp(n^{1/2+o(1)}) \; </math> времени [1], однако нет сведений о его практичности. | ||
В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в статье [5]. Известно [7], что она имеет экспоненциальное время | В данном контексте наиболее практически полезным вариантом считается программа nauty. Брендан Маккей написал первую версию nauty в 1976 году, изложив метод ее работы в статье [5]. Известно [7], что она имеет экспоненциальное время выполнения в наихудшем случае, но на практике этот наихудший случай встречается редко. | ||
| Строка 75: | Строка 77: | ||
== Другие примеры == | == Другие примеры == | ||
Несколько примеров применения таких операций эквивалентности, как изотопия, имеющих важное значение для латинских квадратов и квазигрупп, можно найти в [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 с. | ||
| Строка 92: | Строка 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. | ||
== См. также == | == См. также == | ||
| Строка 119: | Строка 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) | ||
[[Категория: Совместное определение связанных терминов]] | |||
