Компонент (теория графов)

График с тремя компонентами

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

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

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

Определения и примеры

Кластерный граф с семью компонентами

Компонент данного неориентированного графа может быть определен как связный подграф, который не является частью какого-либо более крупного связного подграфа. Например, график, показанный на первой иллюстрации, состоит из трех компонентов. Каждая вершина $v$ графа принадлежит одному из компонентов графа, который можно найти как индуцированный подграф множества вершин, достижимых из $v$. Любой граф представляет собой дизъюнктное объединение его компонентов. Дополнительные примеры включают следующие особые случаи:

• В пустом графе каждая вершина образует компоненту с одной вершиной и нулевым ребром. В более общем смысле компонент этого типа формируется для каждой изолированной вершины любого графа.
• В связном графе есть ровно один компонент: весь граф.
• В лесу каждый компонент является деревом .
• В кластерном графе каждый компонент является максимальной кликой . Эти графы могут быть созданы как транзитивные замыкания произвольных неориентированных графов, для которых нахождение транзитивного замыкания является эквивалентной формулировкой идентификации связных компонентов.

Другое определение компонентов включает классы эквивалентности отношения эквивалентности , определенного в вершинах графа.В неориентированном графе вершина $v$ достижима ​ из вершины $u$ если есть путь из $u$ к $v$или , что то же самое, обход (путь, допускающий повторяющиеся вершины и ребра).Достижимость является отношением эквивалентности, поскольку:

• Это рефлексивно : существует тривиальный путь нулевой длины из любой вершины в себя.
• Симметрично из : если есть путь $u$ к $v$, те же ребра в обратном порядке образуют путь из $v$ к $u$.
• Он транзитивен : если существует путь из $u$ к $v$ и путь из $v$ к $w$, два пути могут быть объединены вместе, чтобы сформировать путь от $u$ к $w$.

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

Подобные определения, включающие классы эквивалентности, использовались для определения компонентов для других форм связности графов , включая слабые компоненты. и сильно связные компоненты графов ориентированных и двусвязные компоненты неориентированных графов.

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

Число компонентов данного конечного графа можно использовать для подсчета количества ребер в его остовных лесах : В графе с $n$ вершины и $c$ компоненты, каждый связующий лес будет иметь ровно $n-c$ края. Этот номер $n-c$ — матроидный теоретико- ранг графа и ранг его графического матроида . Ранг двойственного кографического матроида равен рангу схемы графа, минимальному количеству ребер, которое необходимо удалить из графа, чтобы разорвать все его циклы. На графике с $m$ края, $n$ вершины и $c$ компоненты, ранг схемы $m-n+c$.

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

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

Алгоритмы

Компоненты конечного графа легко вычислить за линейное время (в терминах количества вершин и ребер графа), используя либо поиск в ширину , либо поиск в глубину . В любом случае поиск, начинающийся в некоторой конкретной вершине $v$ найдет весь компонент, содержащий $v$ (и не более) перед возвращением. Все компоненты графа можно найти, пройдя по его вершинам, начиная новый поиск в ширину или в глубину каждый раз, когда цикл достигает вершины, которая еще не была включена в ранее найденный компонент. Хопкрофт и Тарьян (1973) описывают по существу этот алгоритм и заявляют, что он уже «хорошо известен».

Маркировка связанных компонентов — базовый метод компьютерного анализа изображений — включает в себя построение графика на основе изображения и анализ компонентов на графике.Вершины — это подмножество пикселей изображения , выбранных как представляющие интерес или которые могут быть частью изображаемых объектов. Края соединяют соседние пиксели , при этом смежность определяется либо ортогонально в соответствии с окрестностью фон Неймана , либо одновременно ортогонально и по диагонали в соответствии с окрестностью Мура . Идентификация связанных компонентов этого графа позволяет провести дополнительную обработку, чтобы найти дополнительную структуру в этих частях изображения или определить, какой объект изображен. Исследователи разработали алгоритмы поиска компонентов, специально предназначенные для этого типа графиков, позволяющие обрабатывать их в порядке пикселей, а не в более разбросанном порядке, который генерируется при поиске в ширину или в глубину. Это может быть полезно в ситуациях, когда последовательный доступ к пикселям более эффективен, чем произвольный доступ, либо потому, что изображение представлено иерархическим способом, который не допускает быстрого произвольного доступа, либо потому, что последовательный доступ обеспечивает лучшее качество изображения. шаблоны доступа к памяти .

Существуют также эффективные алгоритмы для динамического отслеживания компонентов графа по мере добавления вершин и ребер с использованием структуры данных с непересекающимся набором для отслеживания разделения вершин на классы эквивалентности, заменяя любые два класса их объединением, когда добавляется ребро, соединяющее их. Эти алгоритмы требуют амортизированного времени $O(\alpha (n))$ за операцию, где добавление вершин и ребер и определение компонента, в который попадает вершина, являются обеими операциями, и $\alpha$ является очень медленно растущей функцией, обратной очень быстро растущей функции Аккермана . Одним из применений этого типа алгоритма инкрементной связности является алгоритм Крускала для минимальных остовных деревьев , который добавляет ребра в граф в отсортированном порядке по длине и включает ребро в минимальное остовное дерево только тогда, когда оно соединяет два разных компонента ранее добавленного дерева. подграф. Когда разрешены как вставка ребер, так и удаление ребер, алгоритмы динамического соединения могут по-прежнему сохранять ту же информацию в амортизированном времени. $O(\log ^{2}n/\log \log n)$ за смену и время $O(\log n/\log \log n)$ за запрос на подключение, близком к логарифмическому или в рандомизированном ожидаемом времени, .

Компоненты графов использовались в теории сложности вычислений для изучения возможностей машин Тьюринга , рабочая память которых ограничена логарифмическим числом битов, при этом гораздо больший объем входных данных доступен только через доступ для чтения, а не подлежит изменению. Задачи, которые могут быть решены ограниченными таким образом машинами, определяют сложности L. класс В течение многих лет было неясно, можно ли найти связные компоненты в этой модели, когда она была формализована как задача проверки принадлежности двух вершин одному и тому же компоненту, и в 1982 году был определен связанный класс сложности SL , включающий эту проблему связности. и любая другая задача, эквивалентная ей при логарифмическом сокращении . В 2008 году было окончательно доказано, что эту проблему связности можно решить в логарифмическом пространстве и, следовательно, SL = L.

В графе, представленном в виде списка смежности , при случайном доступе к его вершинам, можно оценить количество компонент связности, с постоянной вероятностью получения аддитивной (абсолютной) ошибки не более $\varepsilon n$, в сублинейное время $O(\varepsilon ^{-2}\log \varepsilon ^{-1})$.

В случайных графах

Основная статья: Гигантский компонент

Случайный граф Эрдеша – Реньи – Гилберта с 1000 вершинами с вероятностью ребра. $p=1/(n-1)$ (в критическом диапазоне), показывая большой компонент и множество мелких

В случайных графах размеры компонентов задаются случайной величиной , которая, в свою очередь, зависит от конкретной модели выбора случайных графов. В $G(n,p)$ версия модели Эрдеша-Реньи-Гилберта , график на $n$ вершин генерируется путем случайного и независимого выбора для каждой пары вершин, включать ли ребро, соединяющее эту пару, с вероятностью $p$ включения ребра и вероятности $1-p$ оставить эти две вершины без соединяющего их ребра. Возможности подключения этой модели зависят от $p$, и существует три различных диапазона $p$ с очень отличающимся поведением друг от друга. В приведенном ниже анализе все исходы происходят с высокой вероятностью , что означает, что вероятность исхода сколь угодно близка к единице для достаточно больших значений $n$. Анализ зависит от параметра $\varepsilon$, положительная константа, независимая от $n$ может быть сколь угодно близко к нулю.

Подкритический $p<(1-\varepsilon )/n$

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

Критический $p\approx 1/n$

Наибольшая компонента связности имеет число вершин, пропорциональное $n^{2/3}$. Может существовать несколько других крупных компонентов; однако общее количество вершин в недревесных компонентах снова пропорционально $n^{2/3}$.

сверхкритический $p>(1+\varepsilon )/n$

Существует единственный гигантский компонент, содержащий линейное количество вершин. Для больших значений $p$ его размер приближается ко всему графу: $|C_{1}|\approx yn$ где $y$ является положительным решением уравнения $e^{-pny}=1-y$. Остальные компоненты небольшие, логарифмического размера.

В одной и той же модели случайных графов с высокой вероятностью будет существовать несколько компонент связности для значений $p$ ниже значительно более высокого порога, $p<(1-\varepsilon )(\log n)/n$и один связный компонент для значений выше порога, $p>(1+\varepsilon )(\log n)/n$. Это явление тесно связано с проблемой сборщика купонов : для связности случайному графу необходимо достаточное количество ребер, чтобы каждая вершина была инцидентна хотя бы одному ребру. Точнее, если в граф по одному добавляются случайные ребра, то с большой вероятностью первое ребро, добавление которого соединяет весь граф, коснется последней изолированной вершины.

Для различных моделей, включая случайные подграфы сеточных графов, связные компоненты описываются теорией перколяции . Ключевым вопросом в этой теории является существование порога перколяции — критической вероятности, выше которой гигантский компонент (или бесконечный компонент) существует, а ниже — нет.

Внешние ссылки

• Код MATLAB для поиска компонентов в неориентированных графах , MATLAB File Exchange.
• Связные компоненты , Стивен Скиена, Репозиторий алгоритмов Стоуни-Брука