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

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

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

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

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

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

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

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

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

Алгоритмы

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

Существуют также эффективные алгоритмы для динамического отслеживания компонентов графа по мере добавления вершин и ребер, как простое применение структур данных с непересекающимися наборами . Эти алгоритмы требуют амортизированного времени O ( α ( n )) на операцию, где добавление вершин и ребер и определение компонента, в который попадает вершина, являются обеими операциями, а α ( n ) - очень медленно растущая инверсия очень быстро растущей Функция Аккермана . Связанная проблема заключается в отслеживании компонентов, поскольку все ребра удаляются из графа одно за другим; существует алгоритм, позволяющий решить эту проблему с постоянным временем на запрос и временем $O (| V || E |)$ для поддержания структуры данных; это амортизированная стоимость $O (| V |)$ за удаление ребра. Для лесов стоимость может быть уменьшена до $O (q + | V | log | V |)$ или до $O (log | V |)$ амортизированной стоимости на удаление ребра ( Shiloach & Even 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 File Exchange.
Связанные компоненты , Стивен Скиена, The Stony Brook Algorithm Repository

Languages

In other projects