Эксперт по сдаче вступительных испытаний в ВУЗах
Примеры связности графов
Пример 1:
На рисунке 1 граф является связным. Однако, скажем, если удалить ребро между вершинами 4 и 5, то связным он не будет — из вершины 5 нельзя будет попасть ни в какую другую вершину.
Рис.1
Если свойство связности не выполняется, граф называется несвязным.
Далее мы не рассматриваем мультиграфы, то есть графы, у которых две вершины могут быть соединены двумя и более рёбрами. Ограничимся рассмотрением графов, в которых каждая пара вершин либо не соединена, либо соединена единственным ребром.
Чтобы граф с n вершинами был связным, он должен иметь не менее (n-1) рёбер.
Если граф имеет не менее (n*n — 3n + 4)/2 рёбер, то он гарантированно связный.
Если граф связный, у него обязательно есть вершины степени не менее 2, то есть вершины, каждая из которых имеет не менее двух смежных вершин.
Если граф связный и без циклов (то есть это дерево), то удаление любого ребра приведёт к потере связности.
Несвязный граф состоит из компонент связности. Компонента связности — множество вершин такое, что из любой вершину этого множества есть путь в любую другую вершину этого множества, но ни из какой вершины этого множества нельзя попасть в некоторую вершину вне этого множества. Очевидно, что сумма количеств вершин компонент связности равна количеству вершин графа.
На рисунке 2 приведён граф с двумя компонентами связности.
Рис.2
Заметим, что компонента связности может состоять из одной вершины. Если у графа n вершин, то он не может состоять из более чем n компонент связности. У связного графа компонента связности единственная.
У несвязного графа любая компонента связности состоит не более, чем из n-1 вершин. Если известно, что у графа k компонент связности, то даём ещё более строгую оценку: любая компонента связности состоит из не более, чем из n-k+1 вершин.
Если у несвязного графа k компонент связности, то для получения связного графа нужно добавить в граф как минимум k-1 ребро.
Как определить, является ли граф связным?
Выбираем некоторую вершину A и помечаем её как посещённую (1), остальные соответственно полагаются ещё не посещёнными (0) (рис.3):
Рис. 3
A полагаем текущей вершиной. Дальше действуем следующим образом. Пометка непосещённых смежных вершин: для текущей вершины ищем смежные с ней, ещё не непосещённые, и помечаем их как посещённые (рис.4).
Рис.4
Пусть у нас оказалось k новопомеченных вершин (на рисунке 4 их 3). По очереди выбираем одну из них текущей и рекурсивно выполняем пометку непосещённых смежных с ней вершин. Для текущей вершины не выполняется рекурсия, если у данной вершины нет смежных вершин, которые всё ещё не помечены как посещённые.
Если после таких действий все вершины окажутся помечены как посещённые, граф связный, иначе несвязный.
Пример 2:
Рис.5
На рисунке 5 натуральное число у вершины означает, какой по счёту она была помечена как посещённая, зелёный цвет числа означает, что для данной вершины был выполнен рекурсивный вызов.
Выбрали некоторую вершину (1). Дальше помечаются три смежных с ней вершины (2, 3, 4). Текущей вершиной теперь становится (2). Рекурсия: помечаем две ещё не посещённые смежные вершины (номера 5 и 6). Для (5) рекурсия не нужна — у неё нет непосещённых смежных вершин, для (6) рекурсия нужна: помечаем номер 7. У номера 7 есть ещё не посещённый «сосед» — номер 8, а вот у номера 8 нет непосещённых смежных вершин. Все рекурсивные вызовы, порождённые из вершины (2), завершены. Теперь на очереди вершина (3), но тут нет необходимости рекурсии. Осталась вершина (4). Одна из её смежных вершин (9) ещё не помечена, исправляем это.
Итого:
Рис.6
Вывод: не все вершины посетили, граф оказался несвязным (рис.6).
Ссылка на первоисточник:
https://mephi.ru
