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

редактировать

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

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

Содержание

1 Отношение эквивалентности
2 Количество компонентов
3 Алгоритмы
4 Компоненты в случайных графах
5 См. Также
6 Ссылки
7 Внешние ссылки

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

Альтернативный способ определения компонентов включает классы эквивалентности отношения эквивалентности, которое определено в вершинах графа. В неориентированном графе вершина 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 проблем logspace- эквивалент подключения. Наконец, Рейнгольд (2008) сумел найти алгоритм для решения этой проблемы связности в логарифмическом пространстве, показав, что L = SL.

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

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

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

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

критический $n p = 1 {\ displaystyle np = 1}$ ${\ displaystyle np = 1}$ : $| C 1 | Знак равно O (n 2/3) {\ displaystyle | C_ {1} | = O (n ^ {2/3})}$ ${\ displaystyle | C_ {1} | = O (n ^ {2/3})}$ ;

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

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

См. также

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

Ссылки

Hopcroft, J. ; Р. Тарьян (1973), «Алгоритм 447: эффективные алгоритмы для манипуляции с графами», Связь ACM, 16(6): 372–378, doi : 10.1145 / 362248.362272
Льюис, Гарри Р. ; Пападимитриу, Христос Х. (1982), «Симметричные вычисления с ограниченным пространством», Теоретическая информатика, 19(2): 161–187, doi : 10.1016 / 0304-3975 (82) 90058-5
Рейнгольд, Омер (2008), «Ненаправленное соединение в пространстве журнала», Журнал ACM, 55(4): Статья 17, 24 страницы, doi : 10.1145 / 1391289.1391291
Шилоах, Йоси; Эвен, Шимон (1981), «Онлайн-проблема удаления ребер», Журнал ACM, 28(1): 1–4, doi : 10.1145 / 322234.322235

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

Код MATLAB для поиска компонентов в неориентированных графах, Обмен файлами MATLAB.
Связанные компоненты, Стивен Скиена, The Stony Brook Algorithm Repository