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

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

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

Отношение эквивалентности

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

это рефлексивный: Существует тривиальный путь нулевой длины от любой вершины к самой себе.
это симметричный: Если есть путь из ты к v, эти же ребра образуют путь из v к ты.
это переходный: Если есть путь из ты к v и путь от v к ш, два пути могут быть объединены вместе, чтобы сформировать путь из ты к ш.

Компоненты тогда индуцированные подграфы сформированный классы эквивалентности этого отношения.

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

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

Алгоритмы

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

Существуют также эффективные алгоритмы для динамического отслеживания компонентов графа по мере добавления вершин и ребер, как простое применение непересекающиеся структуры данных. Эти алгоритмы требуют амортизированный O (α(п)) время на операцию, где добавление вершин и ребер и определение компонента, в который попадает вершина, являются обеими операциями, и α(п) - очень медленно растущая инверсия очень быстро растущей Функция Аккермана. Связанная проблема заключается в отслеживании компонентов, поскольку все ребра удаляются из графа одно за другим; существует алгоритм, позволяющий решить эту проблему с постоянным временем на запрос, и O (|V||E|) время поддерживать структуру данных; это амортизированная стоимость O (|V|) за удаление края. За леса, стоимость может быть уменьшена до O (q + |V| журнал |V|) или O (журнал |V|) амортизированная стоимость за удаление кромки (Шилоах и Эвен 1981 ).

Исследователи также изучили алгоритмы поиска компонентов в более ограниченных моделях вычислений, таких как программы, в которых рабочая память ограничена логарифмический количество бит (определяется класс сложности L ). Льюис и Пападимитриу (1982) спросил, можно ли проверить в пространстве журнала, принадлежат ли две вершины одному и тому же компоненту неориентированного графа, и определил класс сложности SL проблем в журнале, эквивалентном подключению. Ну наконец то Рейнгольд (2008) удалось найти алгоритм решения этой проблемы связности в логарифмическом пространстве, показывающий, что L = SL.

Компоненты в случайных графах

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

В ${ Displaystyle G (п, р)}$ Модель имеет три области с кажущимся разным поведением:

Субкритический ${ displaystyle np <1}$ : Все компоненты простые и очень маленькие, самый большой компонент имеет размер ${ displaystyle | C_ {1} | = O ( log n)}$ ;

Критический ${ displaystyle np = 1}$ : ${ Displaystyle | C_ {1} | = O (п ^ {2/3})}$ ;

Сверхкритический ${ displaystyle np> 1}$ : ${ displaystyle | C_ {1} | приблизительно yn}$ куда ${ Displaystyle у = у (нп)}$ положительное решение уравнения ${ displaystyle e ^ {- pny} = 1-y.}$

куда ${ displaystyle C_ {1}}$ и ${ displaystyle C_ {2}}$ являются соответственно наибольшим и вторым по величине компонентами. Все остальные комплектующие имеют размеры на заказ. ${ displaystyle O ( log n).}$

Смотрите также

Гигантский компонент
Сильносвязная компонента, родственная концепция для ориентированные графы
Двусвязный компонент
Модульная декомпозиция, для правильного обобщения компонентов на неориентированных графах
Маркировка подключенных компонентов, базовый метод компьютерного анализа изображений на основе компонентов графиков
Теория перколяции, теория, описывающая поведение компонентов в случайных подграфах сеточных графов
Центральность
Мост (теория графов)

внешняя ссылка

Код MATLAB для поиска компонентов в неориентированных графах, Обмен файлами MATLAB.
Подключенные компоненты, Стивен Скиена, Репозиторий алгоритмов Стоуни-Брук