АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Связность

Известны два классических алгоритма установления связности обыкновенный графов.

Алгоритм Крускала (Kruskal)

Пусть имеем граф g=(V,X). Пусть Т – подмножество ребер графа g, которое вначале пустое. Добавим к Т первое попавшееся ребро, если оно не образует цикл с уже имеющимися в Т ребрами. Продолжим процесс до исчерпания подходящих ребер. Если после завершения процесса число ребер в Т равно n-1, тогда граф g связный.

Алгоритм Прима (Prim)

Пусть имеем граф g=(V,X). Пусть Т – подмножество его ребер вместе с конечными вершинами, которое вначале пустое. Добавим к Т первое попавшееся ребро. Далее, будем добавлять к Т ребро, одна вершина котрого находится в Т, а другая за пределами Т. Если по завершении процесса число ребер в Т равно n-1, граф связный.

Определение связности на основе волнового процесса

Процедуру определения связности графа можно построить на основе первого волнового процесса. Выберем произвольную вершину a и будем считать, что V₀={a}. Выполним разметку (индексирование) вершин на основе волнового процесса 1. Если размеченными оказались все вершины, то граф является связным.

Пусть <V₀,V₁,..., V_s> - разбиение множества вершин графа, получемое в результате волнового процесса и пусть v_i – вершина номер i графа g, а v_ik – вершина, имеющая номер k в пределах подмножества V_i. Тогда анализ процедуры волнового процесса дает следующее соотношение для времени его выполнения:

,

где n – число вершин, r – число ребер, p(v_ik), p(v_i) – степень вершины, s – количество подмножеств, порождаемых волновым процессом. Отсюда для нашего алгоритма получаем:

t = F(n) = O(r).

Таким образом, по времени выполнения, последний алгоритм имеет такую же эффективность, как и алгоритмы Крускала и Прима.

Определение компонент связности

Следующий алгоритм позволяет определить все компоненты связности графа.

1. Выбрать произвольно вершину a заданного графа g = (V,X). Полагая V₀={a}выполнить волновой процесс с индексированием вершин и пусть V₀,V₁,..., V_s­ - полученная при этом последовательность подмножеств. Разделим множество вершин V на два подмножества:
U₁ = V₀ÈVÈ,..., ÈV_s­ и U₂ = V - U₁.

2. Выделить подграф g₁ на подмножестве вершин U₁ и подграф g₂ на подмножестве вершин U₂. Подграф g₁ – полученный компонент связности графа g.

3. Если U₂ ¹ Æ выполнить п.1 для подграфа g₂, иначе – алгоритм завершить.

Дата добавления: 2015-09-27 | Просмотры: 379 | Нарушение авторских прав