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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Количество компонентов данного конечного графа можно использовать для подсчета количества ребер в его остовных лесах : в графе с вершинами и компонентами каждый остовный лес будет иметь ровно ребра. Это число является теоретико- матроидным рангом графа и рангом его графического матроида . Ранг двойственного кографического матроида равен схемному рангу графа, минимальному количеству ребер, которое необходимо удалить из графа, чтобы разорвать все его циклы. В графе с ребрами, вершинами и компонентами ранг схемы равен . ^[12] ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle n-c}$ ${\displaystyle n-c}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle m-n+c}$

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. Кларк, Джон; Холтон, Дерек Аллан (1995), Первый взгляд на теорию графов, Allied Publishers, стр. 28, ISBN 9788170234630, заархивировано из оригинала 8 января 2022 г. , получено 7 января 2022 г.
2. Джойнер, Дэвид; Нгуен, Минь Ван; Филлипс, Дэвид (10 мая 2013 г.), «1.6.1 Объединение, пересечение и объединение», Algorithmic Graph Theory and Sage (изд. 0.8-r1991), Google, стр. 34–35, заархивировано из оригинала 16 января. , 2016 , получено 8 января 2022 г.
3. Tutte, WT (1984), Теория графов, Энциклопедия математики и ее приложений, том. 21, Ридинг, Массачусетс: Аддисон-Уэсли, с. 15, ISBN 0-201-13520-5, MR  0746795, заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.
4. Туласираман, К.; Свами, MNS (2011), Графики: теория и алгоритмы, John Wiley & Sons, стр. 9, ISBN 978-1-118-03025-7, заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.
5. Боллобас, Бела (1998), Современная теория графов, Тексты для выпускников по математике, том. 184, Нью-Йорк: Springer-Verlag, с. 6, номер домена : 10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR  1633290, заархивировано из оригинала 08 января 2022 г. , получено 8 января 2022 г.
6. Макколл, WF; Ношита, К. (1986), «О количестве ребер в транзитивном замыкании графа», Discrete Applied Mathematics , 15 (1): 67–73, doi : 10.1016/0166-218X(86)90020-X, МР  0856101
7. Фолдс, Стефан (2011), Фундаментальные структуры алгебры и дискретной математики, John Wiley & Sons, стр. 199, ISBN 978-1-118-03143-8, заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.
8. Сик, Джереми; Ли, Ли-Куан; Ламсдейн, Эндрю (2001), «7.1 Связные компоненты: определения», Библиотека Boost Graph: Руководство пользователя и справочное руководство , Addison-Wesley, стр. 97–98.
9. Кнут, Дональд Э. (15 января 2022 г.), «Слабые компоненты», Искусство компьютерного программирования, Том 4, Предвыпуск 12A: Компоненты и обход (PDF) , стр. 11–14, заархивировано (PDF) с сайта оригинал 18 января 2022 г. , получено 1 марта 2022 г.
10. Льюис, Гарри ; Закс, Рэйчел (2019), «Основная дискретная математика для информатики», Princeton University Press, стр. 145, ISBN 978-0-691-19061-7, заархивировано из оригинала 08 января 2022 г. , получено 8 января 2022 г.
11. Козен, Декстер К. (1992), «4.1 Двусвязные компоненты», Проектирование и анализ алгоритмов , тексты и монографии по информатике, Нью-Йорк: Springer-Verlag, стр. 20–22, doi : 10.1007/978-1 -4612-4400-4, ISBN 0-387-97687-6, MR  1139767, S2CID  27747202, заархивировано из оригинала 8 января 2022 г. , получено 8 января 2022 г.
12. Уилсон, Р.Дж. (1973), «Введение в теорию матроидов», The American Mathematical Monthly , 80 (5): 500–525, doi : 10.1080/00029890.1973.11993318, JSTOR  2319608, MR  0371694
13. Вуд, Дэвид Р. (2014), «Рисование трехмерного графа», в Као, Мин-Янг (редактор), Энциклопедия алгоритмов (PDF) , Springer, стр. 1–7, doi : 10.1007/978- 3-642-27848-8_656-1, ISBN 978-3-642-27848-8, заархивировано (PDF) из оригинала 8 января 2022 г. , получено 8 января 2022 г.
14. Чиоабэ, Себастьян М. (2011), «Некоторые применения собственных значений графов», в Демере, Маттиасе (ред.), Структурный анализ сложных сетей , Нью-Йорк: Birkhäuser/Springer, стр. 357–379, doi : 10.1007 /978-0-8176-4789-6_14, ISBN 978-0-8176-4788-9, МР  2777924; см. доказательство леммы 5, с. 361. Архивировано 8 января 2022 г. в Wayback Machine.
15. Рид, Рональд К. (1968), «Введение в хроматические полиномы», Журнал комбинаторной теории , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0 , MR  0224505; см. теорему 2, с. 59 и следствие, с. 65
16. Тутте, WT (1947), «Факторизация линейных графов», Журнал Лондонского математического общества , 22 (2): 107–111, doi : 10.1112/jlms/s1-22.2.107, MR  0023048
17. Берж, Клод (1958), «Sur le couplage Maximum d'un Grape», Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences , 247 : 258–259, MR  0100850
18. Хватал, Вацлав (1973), «Жесткие графики и гамильтоновы схемы», Дискретная математика , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR  0316301
19. Хопкрофт, Джон ; Тарьян, Роберт (июнь 1973 г.), «Алгоритм 447: эффективные алгоритмы манипулирования графами», Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272 , S2CID  14772567
20. Дилленкур, Майкл Б.; Самет, Ханан ; Тамминен, Маркку (1992), «Общий подход к маркировке связанных компонентов для произвольных представлений изображений», Журнал ACM , 39 (2): 253–280, CiteSeerX 10.1.1.73.8846 , doi : 10.1145/128749.128750, MR  1160258, S2CID  1869184 
21. Бенгеллон, Сафван Абдельмаджид (декабрь 1982 г.), Аспекты дополнительных вычислений (докторская диссертация), Йельский университет, стр. 12, ПроКвест  : 303248045
22. Скиена, Стивен (2008), «6.1.2 Алгоритм Краскала», Руководство по разработке алгоритмов , Springer, стр. 196–198, Bibcode : 2008adm..book.....S, doi : 10.1007/978-1- 84800-070-4, ISBN 978-1-84800-069-8, заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.
23. Вульф-Нильсен, Кристиан (2013), «Быстрая детерминированная полностью динамическая связность графов», Ханна, Санджив (редактор), Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2013, Новый Орлеан, Луизиана, США, 6–8 января 2013 г. , стр. 1757–1769, arXiv : 1209.5608 , doi : 10.1137/1.9781611973105.126, ISBN. 978-1-61197-251-1, S2CID  13397958
24. Хуан, Шан-Эн; Хуан, Давэй; Копеловиц, Цви; Петти, Сет (2017), «Полностью динамическое соединение в амортизированное ожидаемое время», Кляйн, Филип Н. (ред.), Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, Отель Porta Fira, 16–19 января , стр. 510–520, arXiv : 1609.05867 , doi : 10.1137/1.9781611974782.32, S2CID  15585534 ${\displaystyle O{\bigl (}\log n(\log \log n)^{2}{\bigr )}}$
25. Льюис, Гарри Р .; Пападимитриу, Христос Х. (1982), «Симметричные вычисления в пространстве», Theoretical Computer Science , 19 (2): 161–187, doi : 10.1016/0304-3975(82)90058-5 , MR  0666539
26. Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): A17:1–A17:24, doi : 10.1145/1391289.1391291, MR  2445014, S2CID  207168478
27. Беренбринк, Петра; Крайенхофф, Брюс; Маллманн-Тренн, Фредерик (2014), «Оценка количества связанных компонентов в сублинейное время», Information Processing Letters , 114 (11): 639–642, doi : 10.1016/j.ipl.2014.05.008, MR  3230913
28. Фриз, Алан ; Каронски, Михал (2016), «1.1 Модели и отношения», Введение в случайные графы , Cambridge University Press, Кембридж, стр. 3–9, doi : 10.1017/CBO9781316339831, ISBN 978-1-107-11850-8, МР  3675279
29. Frieze & Karoński (2016), 2.1 Подкритическая фаза, стр. 20–33; см. особенно теорему 2.8, с. 26, теорема 2.9, с. 28 и лемма 2.11, с. 29
30. Frieze & Karoński (2016), 2.3 Фазовый переход, стр. 39–45.
31. Frieze & Karoński (2016), 2.2 Сверхкритическая фаза, стр. 33; см. особенно теорему 2.14, с. 33–39
32. Frieze & Karoński (2016), 4.1 Связь, стр. 64–68.
33. Коэн, Реувен; Хэвлин, Шломо (2010), «10.1 Проникновение в сложные сети: Введение», Сложные сети: структура, надежность и функции , Cambridge University Press, стр. 97–98, ISBN 978-1-139-48927-0, заархивировано из оригинала 10 января 2022 г. , получено 10 января 2022 г.

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

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