Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Связный неориентированный граф. Компонента связности. Алгоритм распознавания связности (несвязности)

На главную Математический раздел Криптография и т.д. Новости

Связный граф, несвязный граф, компонента связности, свойства

Неориентированный граф считается связным, если из любой вершины есть путь в любую другую вершину (путь может состоять из любого количества рёбер). Пример: на рисунке чуть ниже граф является связным. Однако, скажем, если удалить ребро между вершинами 4 и 5, то связным он не будет - из вершины 5 нельзя будет попасть ни в какую другую вершину.

Если свойство связности не выполняется, граф называется несвязным.

Далее мы не рассматриваем мультиграфы, то есть графы, у которых две вершины могут быть соединены двумя и более рёбрами. Ограничимся рассмотрением графов, в которых каждая пара вершин либо не соединена, либо соединена единственным ребром.

Чтобы граф с n вершинами был связным, он должен иметь не менее (n-1) рёбер.

Если граф имеет не менее (n*n - 3n + 4)/2 рёбер, то он гарантированно связный.

Если граф связный, у него обязательно есть вершины степени не менее 2, то есть вершины, каждая из которых имеет не менее двух смежных вершин.

Если граф связный и без циклов (то есть это дерево), то удаление любого ребра приведёт к потере связности.

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

На рисунке приведён граф с двумя компонентами связности.

Заметим, что компонента связности может состоять из одной вершины. Если у графа n вершин, то он не может состоять из более чем n компонент связности. У связного графа компонента связности единственная.

У несвязного графа любая компонента связности состоит не более, чем из n-1 вершин. Если известно, что у графа k компонент связности, то даём ещё более строгую оценку: любая компонента связности состоит из не более, чем из n-k+1 вершин.

Если у несвязного графа k компонент связности, то для получения связного графа нужно добавить в граф как минимум k-1 ребро.

Как определить, является ли граф связным?

Выбираем некоторую вершину A и помечаем её как посещённую (1), остальные соответственно полагаются ещё не посещёнными (0):

A полагаем текущей вершиной. Дальше действуем следующим образом. Пометка непосещённых смежных вершин: для текущей вершины ищем смежные с ней, ещё не непосещённые, и помечаем их как посещённые.

Пусть у нас оказалось k новопомеченных вершин (на рисунке чуть выше их 3). По очереди выбираем одну из них текущей и рекурсивно выполняем пометку непосещённых смежных с ней вершин. Для текущей вершины не выполняется рекурсия, если у данной вершины нет смежных вершин, которые всё ещё не помечены как посещённые.

Если после таких действий все вершины окажутся помечены как посещённые, граф связный, иначе несвязный.

Разберём небольшой пример:

Здесь натуральное число у вершины означает, какой по счёту она была помечена как посещённая, зелёный цвет числа означает, что для данной вершины был выполнен рекурсивный вызов.

Выбрали некоторую вершину (1). Дальше помечаются три смежных с ней вершины (2, 3, 4). Текущей вершиной теперь становится (2). Рекурсия: помечаем две ещё не посещённые смежные вершины (номера 5 и 6). Для (5) рекурсия не нужна - у неё нет непосещённых смежных вершин, для (6) рекурсия нужна: помечаем номер 7. У номера 7 есть ещё не посещённый "сосед" - номер 8, а вот у номера 8 нет непосещённых смежных вершин. Все рекурсивные вызовы, порождённые из вершины (2), завершены. Теперь на очереди вершина (3), но тут нет необходимости рекурсии. Осталась вершина (4). Одна из её смежных вершин (9) ещё не помечена, исправляем это. Итого:

Вывод: не все вершины посетили, граф оказался несвязным.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X