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

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

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

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

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

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

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

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

Компонент данного неориентированного графа может быть определен как связный подграф, который не является частью какого-либо большего связного подграфа. Например, граф, показанный на первой иллюстрации, имеет три компонента. Каждая вершина графа принадлежит одному из компонентов графа, который может быть найден как индуцированный подграф множества вершин, достижимых из . ^[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, заархивировано из оригинала 2022-01-08 , извлечено 2022-01-07
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, Рединг, Массачусетс: Addison-Wesley, стр. 15, ISBN 0-201-13520-5, MR  0746795, архивировано из оригинала 2022-01-07 , извлечено 2022-01-07
4. Туласираман, К.; Свами, МНС (2011), Графы: Теория и алгоритмы, John Wiley & Sons, стр. 9, ISBN 978-1-118-03025-7, заархивировано из оригинала 2022-01-07 , извлечено 2022-01-07
5. Боллобаш, Бела (1998), Современная теория графов, Graduate Texts in Mathematics, т. 184, Нью-Йорк: Springer-Verlag, стр. 6, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR  1633290, архивировано из оригинала 2022-01-08 , извлечено 2022-01-08
6. Макколл, У. Ф.; Ношита, К. (1986), «О числе ребер в транзитивном замыкании графа», Дискретная прикладная математика , 15 (1): 67–73, doi :10.1016/0166-218X(86)90020-X, MR  0856101
7. Фолдес, Стефан (2011), Фундаментальные структуры алгебры и дискретной математики, John Wiley & Sons, стр. 199, ISBN 978-1-118-03143-8, заархивировано из оригинала 2022-01-07 , извлечено 2022-01-07
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, заархивировано из оригинала 2022-01-08 , извлечено 2022-01-08
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, заархивировано из оригинала 2022-01-08 , извлечено 2022-01-08
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) из оригинала 2022-01-08 , извлечено 2022-01-08
14. Cioabă, Sebastian M. (2011), «Некоторые приложения собственных значений графов», в Dehmer, Matthias (ред.), Structural Analysis of Complex Networks , Нью-Йорк: Birkhäuser/Springer, стр. 357–379, doi :10.1007/978-0-8176-4789-6_14, ISBN 978-0-8176-4788-9, г-н  2777924; см. доказательство леммы 5, стр. 361 Архивировано 08.01.2022 на Wayback Machine
15. Рид, Рональд К. (1968), «Введение в хроматические многочлены», Журнал комбинаторной теории , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0 , MR  0224505; см. теорему 2, стр. 59, и следствие, стр. 65
16. Tutte, 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. Chvátal, Václav (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 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, заархивировано из оригинала 2022-01-07 , извлечено 2022-01-07
23. Wulff-Nilsen, Christian (2013), «Быстрая детерминированная полностью динамическая связность графов», в Khanna, Sanjeev (ред.), Труды двадцать четвертого ежегодного симпозиума 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), «Симметричное пространственно-ограниченное вычисление», Теоретическая информатика , 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. Фриз и Каронски (2016), 2.3 Фазовый переход, стр. 39–45
31. Frieze & Karoński (2016), 2.2 Сверхкритическая фаза, стр. 33; см. особенно теорему 2.14, стр. 33–39
32. Фриз и Каронски (2016), 4.1 Связность, стр. 64–68
33. Коэн, Реувен; Хавлин, Шломо (2010), «10.1 Перколяция в сложных сетях: Введение», Комплексные сети: структура, надежность и функция , Cambridge University Press, стр. 97–98, ISBN 978-1-139-48927-0, заархивировано из оригинала 2022-01-10 , извлечено 2022-01-10

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

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