Введение

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

В теории графов компонентой неориентированного графа является связный подграф, который не является частью какого-либо большего связного подграфа. Компоненты любого графа разбивают его вершины на непересекающиеся множества и являются индуцированными подграфами этих множеств. Граф, который сам по себе связен, имеет ровно одну компоненту, состоящую из всего графа. Компоненты иногда называют связными компонентами. Количество компонент в заданном графе является важным инвариантом графа и тесно связано с инвариантами матроидов, топологических пространств и матриц. В случайных графах часто встречающимся явлением является появление гигантской компоненты – одной компоненты, значительно большей по размеру, чем остальные, а также порога перколяции – вероятности ребра, выше которой гигантская компонента существует, а ниже которой – нет. Компоненты графа могут быть построены за линейное время, а частный случай этой задачи, маркировка связных компонент, является базовым методом в анализе изображений. Алгоритмы динамической связности поддерживают компоненты при добавлении или удалении ребер в графе за короткое время на каждую операцию. В теории вычислительной сложности связные компоненты использовались для изучения алгоритмов с ограниченной пространственной сложностью, а алгоритмы с временем работы меньше линейного могут точно оценивать количество компонент.

Количество компонентов

Количество компонент данного конечного графа может быть использовано для подсчета количества ребер в его остовных лесах: в графе с *n* вершинами и *k* компонентами, каждый остовный лес будет иметь ровно *n* − *k* ребер. Это число является матроидным рангом графа и рангом его графического матроида. Ранг двойного кографического матроида равен круговому рангу графа, минимальному количеству ребер, которые необходимо удалить из графа, чтобы разорвать все его циклы. В графе с *m* ребрами, *n* вершинами и *k* компонентами, круговой ранг равен *m* − (*n* − *k*).

Граф можно интерпретировать как топологическое пространство несколькими способами, например, размещая его вершины как точки в общем положении в трехмерном евклидовом пространстве и представляя его ребра как отрезки прямых между этими точками. Компоненты графа можно обобщить через эти интерпретации как топологически связные компоненты соответствующего пространства; это классы эквивалентности точек, которые нельзя разделить парами непересекающихся замкнутых множеств. Так же, как число связных компонент топологического пространства является важным топологическим инвариантом, нулевым числом Бетти, число компонент графа является важным инвариантом графа, и в топологической теории графов его можно интерпретировать как нулевое число Бетти графа. Число компонент возникает и в других областях теории графов. В алгебраической теории графов оно равно кратности 0 как собственного значения матрицы Лапласа конечного графа. Оно также является индексом первого ненулевого коэффициента хроматического многочлена графа, и хроматический многочлен всего графа можно получить как произведение многочленов его компонент. Число компонент играет ключевую роль в теореме Тютте, характеризующей конечные графы, имеющие совершенное паросочетание, и связанной с ней формуле Тютте — Берге для размера максимального паросочетания, а также в определении устойчивости графа.

Алгоритмы

Проще всего вычислить компоненты связности конечного графа за линейное время (с точки зрения числа вершин и ребер графа) с помощью поиска в ширину или поиска в глубину. В любом случае, поиск, начинающийся с некоторой вершины, найдет всю компоненту связности, содержащую эту вершину (и ничего больше), прежде чем завершится. Все компоненты связности графа можно найти, последовательно перебирая его вершины и запуская новый поиск в ширину или в глубину каждый раз, когда перебор достигает вершины, которая еще не была включена в ранее найденную компоненту связности. По сути, этот алгоритм уже был известен. Построение меток компонент связности, являющееся базовой техникой в компьютерном анализе изображений, включает в себя построение графа на основе изображения и анализ компонент связности на этом графе. Вершинами графа являются подмножество пикселей изображения, выбранных как представляющие интерес или как потенциальные части изображаемых объектов. Ребра соединяют соседние пиксели, при этом соседство определяется либо ортогонально, в соответствии с окрестностью Фон-Ноймана, либо ортогонально и диагонально, в соответствии с окрестностью Мура. Определение компонент связности этого графа позволяет проводить дополнительную обработку для выявления большей структуры в этих частях изображения или для определения типа изображенного объекта. Исследователи разработали алгоритмы поиска компонент связности, специализированные для этого типа графа, позволяющие обрабатывать его в порядке пикселей, а не в более разрозненном порядке, который был бы получен при поиске в ширину или в глубину. Это может быть полезно в ситуациях, когда последовательный доступ к пикселям более эффективен, чем произвольный доступ, либо потому, что изображение представлено иерархически и не обеспечивает быстрого произвольного доступа, либо потому, что последовательный доступ обеспечивает более эффективные шаблоны доступа к памяти. Существуют также эффективные алгоритмы для динамического отслеживания компонент связности графа при добавлении вершин и ребер, использующие структуру данных "непересекающиеся множества" для отслеживания разбиения вершин на классы эквивалентности, заменяя любые два класса их объединением при добавлении ребра, соединяющего их. Эти алгоритмы требуют амортизированного времени за операцию, где добавление вершин и ребер, а также определение компоненты связности, содержащей вершину, являются операциями, а – очень медленно растущая обратная функция к очень быстро растущей функции Аккермана. Одним из применений такого рода инкрементального алгоритма связности является алгоритм Крускала для построения минимальных остовных деревьев, который добавляет ребра в граф в отсортированном порядке по длине и включает ребро в минимальное остовное дерево только в том случае, если оно соединяет две различные компоненты связности ранее добавленного подграфа. Когда разрешены как вставка, так и удаление ребер, алгоритмы динамической связности могут по-прежнему поддерживать ту же информацию за амортизированное время на изменение и время на запрос связности или за почти логарифмическое случайное ожидаемое время. Компоненты связности графов использовались в теории вычислительной сложности для изучения мощности машин Тьюринга с рабочей памятью, ограниченной логарифмическим числом битов, при этом гораздо больший вход доступен только через чтение, а не через изменение. Задачи, которые могут быть решены такими машинами, определяют класс сложности L. Долгое время было неясно, можно ли найти компоненты связности в этой модели, когда она была формализована как задача принятия решения о проверке того, принадлежат ли две вершины одной и той же компоненте связности, и в 1982 году был определен связанный класс сложности SL, чтобы включить эту задачу связности и любую другую задачу, эквивалентную ей при логарифмическом сокращении пространства. В 2008 году было окончательно доказано, что эту задачу связности можно решить за логарифмическое пространство, и, следовательно, в графе, представленном в виде списка смежности, с произвольным доступом к его вершинам, можно оценить количество компонент связности с постоянной вероятностью получения аддитивной (абсолютной) ошибки не более чем в сублинейное время.