 |
|
АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология |
Изоморфность графов
Изоморфизм Графы g1(V1,X1) и g2(V2,X2) называются изоморфными, если существует биективное отображение j: V1®V2, сохраняющее смежность, т.е. { a,b} Î X1 Û { j(a), j(b) } Î X2. Если два некоторых графа являются изоморфными, они имеют одинаковую структуру. Можно говорить о том, что изоморфные графы отличаются лишь нумерацией (или обозначениями) вершин. Имеют место следующие утверждения. 1° Необходимым условием изоморфности графов A и B является одинаковое число вершин и одинаковое число ребер. 2° Графы изоморфны в том и только в том случае, если изоморфны их дополнительные графы. 3° Отношение изоморфности на множестве графов является отношением эквивалентности. Проблема изоморфизма состоит в построении эффективного алгоритма установления изоморфности двух заданных графов. Решение проблемы важно для многих практических приложений. Ни один из известных алгоритмов установления изоморфности не является полиномиальным по времени выполнения. Существует два пути строгого установления изоморфности графов: использование полных инвариантов и прямая проверка изоморфности графов. Рассмотрим 3 алгоритма проверки изоморфности: - полный перебор; - ПНВ-алгоритм; - модифицированный ПНВ-алгоритм.
Полный перебор Осуществляется перебор и проверка всех возможных функций подстановки j(v). Эта функция ставит в соответствие каждой вершине v графа A некоторую вершину графа B (значение функции j(v)). Т.к. функция j(v) определена на дискретном множестве с числом элементов n и функция является биективной, то всего разных функций подстановки j(v) существует n!. Для проверки одной подстановки требуется сравнить поэлементно две матрицы смежности размером n´n. Операция сравнения одной пары элементов двух матриц смежности включает в себя два этапа: вычисление значения функции j(v) и собственно сравнение двух значений. Из приведенных фактов следует, что время установления изоморфности будет равно: t £ Const n! n2. Символ "£" появляется от того, что при обнаружении первого изоморфизма выполнение алгоритма завершается. Однако, если исходные графы не изоморфны, будут проверены все возможное варианты функций j(v). Т.о. функция сложности для рассматриваемого алгоритма равна: Ft(n) = O(n2n!). Программная реализация Для перечисления функций подстановок j(v) можно использовать функцию permut: int permut(int n, int* p) При каждом вызове эта функция формирует очередную перестановку для последовательности целых чисел, сохраняемой в массиве p. Возвращаемое значение: номер полученной перестановки.
ПНВ-алгоритм Рассмотрим ПНВ-алгоритм, он относится к разряду т.н. back-tracking (поиск с возвратом). Суть алгоритма состоит в последовательном наложении (установлении соответствия) вершин графа A на вершины графа B таким образом, чтобы формируемые подмножества вершин в одном и другом графах имели одинаковые отношения смежности. Таким образом, в A и B строится общий, с точностью до изоморфизма, подграф, число вершин в котором на каждом шаге увеличивается. При этом, если на очередном шаге никакая из оставшихся вершин графа B не подходит для включения ее в выделенное подмножество, делается шаг назад и выполняется попытка заменить последнюю вершину из включенных в указанное подмножество на другую. Алгоритм завершается если формируемое подмножество покрывает все вершины графа (с выдачей результата "ДА") либо при исчерпании всех возможных вариантов наложения (с выдачей результата "НЕТ"). Ниже приведено описание алгоритма в виде С++-функции iso(A,B).
int iso(graf& A, graf& B) { int i, j, k, s, sp, n = A.nv; int f[n], st[n]; for (i = 0; i < n; i++) { f[i] = i; st[i] = 0; } matad MA = A, MB = B; for (k = 0; k < n; k++) // k - позиция стартовой вершины в Bv { swp(f[0], f[k]); // f[k] - номер стартовой вершины в B for (sp = 1; sp < n; sp++) // sp - число вершин найденного общего подграфа { s = sp; mmm: for (i = s; i< n; i++) // i - вершина-кандидат на включение в ОП { for (j = 0; j < sp; j++) // проверка вершины-кандидата if (MB.s[f[i]][f[j]]!= MA.s[sp][j]) break; if (j == sp) { swp(f[sp], f[i]); st[sp] = i; break; } // найденная вершина ставится на место в массиве f и запоминается в массиве st } if (i == n) { sp--; // если i==n, успешная вершина не найдена if (sp == 0) break; swp(f[sp], f[st[sp]]); // восстановление f s = st[sp] + 1; goto mmm; // возврат на пред. уровень } } if (sp == n) break; // если sp==n, изоморфизм найден } return k < n? 1: 0; // если k==n, изоморфизм не существует } Основные обозначения, используемые в программе: A,B - исходные графы; graf, matad - классовые типы, представляющие граф в виде таблицы связей и матрицы смежности, соответственно; A.nv - число вершин графа A (предполагается A.nv==B.nv); A.p[i] - степень i-той вершины графа A; M.s[i][k] - элемент матрицы смежности M с индексами i,k; f[] - массив, представляющий искомую подстановку; st[] - рабочий массив, используемый для восстановления информации в случае возврата; sp - текущее число вершин общего подграфа; Функция iso(A,B) возвращает 1, если графы изоморфны, и 0 - если нет. Работа функции завершается после отыскания первой изоморфной подстановки.
Модифицированный ПНВ-алгоритм Исследование функции iso1 на случайных графах выявило ее существенный недостаток: при малом или наоборот большом относительном реберном заполнении время выполнения функции многократно (на несколько порядков!) возрастает. На рис. показана зависимость среднего времени выполнения функции iso1 от относительного реберного заполнения для случайных графов с n = 40. Эффективность алгоритма можно улучшить, если очередную вершину включать в ОП только в том случае, если она имеет соотв. степень. Однако радикально улучшить эффективность алгоритма можно, если использовать предварительную перенумерацию вершин проверяемых графов. Фрагменты <1>,<2> выполняют упорядочивание номеров вершин в массивах Av, Bv, соответственно, по убыванию их степеней. Фрагмент <3> выполняет дополнительное упорядочивание вершин в массиве Av по такому принципу: на очередную позицию с номером k выбирается номер вершины из одной из последующих позиций так, чтобы соответствующая ей вершина имела максимальное число связей с вершинами, записанными в позициях 0, 1,..., k-1. Такое упорядочивание может значительно уменьшать средний коэффициент ветвления дерева поиска.
Библиотечный вариант приведенной функции при тестировании показывает такой результат: при использовании процессора Pentium 3.0 Ггц для случайных графов при n=2000 и половинном реберном заполнении (r=999500) время счета в среднем составляет 3.3 с.
Дата добавления: 2015-09-27 | Просмотры: 1357 | Нарушение авторских прав |