4551
правка
Задача изоморфизма графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача изоморфизма графов (посмотреть исходный код)
Версия от 13:37, 21 апреля 2015
, 21 апреля 2015→Экспериментальные результаты
Irina (обсуждение | вклад) м (→Другие примеры) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
Программа 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: | Строка 91: | ||
Примеры более сложных графов можно найти в документации программы nauty. | Примеры более сложных графов можно найти в документации программы nauty. | ||
== Ссылка на код == | == Ссылка на код == | ||