В теории графов для k-связного графа G = (V, E) подмножество реберсчитается свидетельством k-связности графа G тогда и только тогда, когда подграф G '= (V, E') k-связен . [1]
Редкие сертификаты
Для к-связного графа с п вершинами , всегда существует к -связности сертификат с не более чем к (N-1) ребер. Сертификаты K-связности считаются разреженными, если они содержат O ( kn ) ребер. [2] На этом рисунке граф справа также является разреженным сертификатом для графа G слева.
Поиск с первым сканированием
Scan-First - это алгоритм параллельного построения сертификатов k-связности для графов. Он был представлен в статье Джозеф Чериян, Минг-Ян Као и Рамакришна Туримелла в статье «Поиск с первым сканированием и разреженные сертификаты: улучшенный параллельный алгоритм для K-Vertex Connectivity ». [2] Алгоритм поиска с первым сканированием сокращает время создания разреженного сертификата для k-связности с использованием модели параллельных вычислений.
Мы можем найти разреженный сертификат для k-связности, итеративно выполняя поиск с первым сканированием k раз на подграфах нашего входного графа. Наш вход - это граф G = (V, E) и корневая вершина r. Для каждой итерации поиска по первому сканированию мы сначала вычисляем остовное дерево T нашего входного графа G и назначаем всем вершинам порядковую нумерацию, которую мы будем использовать в качестве нашего порядка сканирования. От нашего корня r мы сначала просматриваем r, что включает в себя пометку всех его соседних вершин.
Для связного неориентированного графа и указанной вершины поиск с первым сканированием в графе, начиная с указанной вершины, является систематическим способом пометки вершин. Основной этап маркировки называется сканированием : сканировать отмеченную вершину означает пометить всех ранее не отмеченных соседей этой вершины. В начале поиска помечается только указанная начальная вершина. Затем поиск итеративно сканирует отмеченную и не просканированную вершину, пока не будут просканированы все вершины.
Поиск с первым сканированием в связном неориентированном графе дает связующее дерево, определяемое следующим образом. В начале поиска дерево пусто. Затем для каждой вершины x в графе, когда x просматривается, все ребра между x и его ранее немаркированными соседями добавляются к дереву; ребра между x и его ранее отмеченными соседями не добавляются в дерево.
Все ранее немаркированные вершины составляют конечную точку ребра из текущей сканируемой вершины, поэтому, если мы начинаем с некоторой вершины v, и у нее есть соседи w и x, то, если и w, и x не отмечены, мы создаем ребра (v , w) и (v, x) и добавляем их в наше выходное дерево T '. Если ранее были отмечены w или x, мы не добавляем ребро, которое включает эту вершину, в T '. С этими новыми ребрами в T 'мы переходим к следующей вершине с наименьшим порядковым номером для сканирования, что включает в себя непрерывную пометку ранее немаркированных вершин и добавление ребер из текущей вершины к этим вершинам в наше выходное дерево.
Мы используем поиск с первым сканированием, чтобы генерировать сертификаты для k-соединения, выполняя его для k итераций. Важное замечание в дальнейшем заключается в том, что для каждого ребра, добавленного к некоторому выходному дереву T 'на каждой итерации, мы удаляем ребра из исходного графа G, чтобы они не могли быть включены в некоторый остовный лес для следующей итерации. Однако мы можем рассматривать отметки на вершинах как сброшенные, поэтому на следующей итерации вершины не помечаются.
После того, как мы исчерпали все вершины, у нас есть набор ребер для первой итерации, E 1 . Затем мы удаляем E 1 из G = G 0 и делаем это G 1 , и переходим ко второй итерации, используя граф G 1 . В конце каждой итерации у нас есть:
- E i : набор ребер, с которыми мы столкнулись во время поиска при первом сканировании.
- F i : Лес поиска с первым сканированием, группировка ребер в отдельные деревья на каждом шаге.
- G i : получившийся граф от удаления E i из графа G i-1, который мы использовали для начала этой итерации.
- H i : объединение ребер с каждой итерации до настоящего момента, E 1 ∪ E 2 ∪ ... ∪ E i .
Мы говорим, что H k - разреженный сертификат для графа G.
Основная теорема о сертификате
Для неориентированного графа G = ( V , E ) с n вершинами, пусть k - некоторое натуральное число. Для всех i = 1, 2,. . . , k , пусть E i будет набором ребер, сгенерированным i-й итерацией поиска с первым сканированием, соответствующего графу G i −1 = ( V , E - ( E 1 ∪ ... ∪ E i −1 )). Таким образом, для каждой итерации поиска с первым сканированием, как указано выше, мы будем удалять ребра из графа G, чтобы создать новый граф G i, который будет получен в конце i- й итерации. Для каждой итерации i наш лес поиска с первым сканированием строится из графа G i −1 , где G = G 0 . Утверждение основной сертификатной теоремы состоит в том, что объединение E 1 ∪. . . ∪ E k - это свидетельство о связности k- вершин группы G и о том, что она имеет не более k ( n - 1) ребер. [2]
Вычислительная сложность
Наиболее важным является время работы алгоритма, работающего параллельно, в данном случае с использованием модели CRCW PRAM. Наше первое остовное дерево T может быть найдено за время O (log n ) с использованием C ( n , m ) процессоров. Наши номера предварительных заказов и соседи также могут быть рассчитаны за время O (log n), потому что параллельные методы [3] с O (( n + m ) / log n ) процессорами, наше значение C ( n , m ). По этой причине мы можем сгенерировать одно простое число T &, соответствующее одной итерации за время O (log n ).
Используя подход распределенного поиска в ширину, мы можем найти наш покрывающий лес за O ( d log 3 n ) времени на графе с диаметром d, используя O ( m + n log 3 n ) сообщений. Последовательный подход - это просто время выполнения поиска в ширину, O ( m + n ) .
Смотрите также
Рекомендации
- ^ Эвен, С. (1975-09-01). «Алгоритм для определения того, является ли связность графа по крайней мере k» (PDF) . SIAM Journal on Computing . 4 (3): 393–396. DOI : 10.1137 / 0204034 . ЛВП : 1813/6027 . ISSN 0097-5397 .
- ^ а б в Cheriyan, J .; Kao, M .; Туримелла, Р. (1 февраля 1993 г.). «Поиск с первым сканированием и разреженные сертификаты: улучшенный параллельный алгоритм для подключения k-вершин» (PDF) . SIAM Journal on Computing . 22 (1): 157–174. DOI : 10.1137 / 0222013 . hdl : 1813/8878 . ISSN 0097-5397 .
- ^ Карп, Ричард М .; Рамачандран, Виджая (01.01.1990). ван Леувен, Ян (ред.). Справочник по теоретической информатике (том А) . Кембридж, Массачусетс, США: MIT Press. С. 869–941. ISBN 978-0-444-88071-0.