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

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

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

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

Определения и примеры [ править ]

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

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

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

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

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

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

Количество компонентов [ править ]

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

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

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

Алгоритмы [ править ]

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

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

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

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

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

В случайных графиках [ править ]

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

Подкритический $p<(1-\varepsilon )/n$: В этом диапазоне $p$ , все компоненты простые и очень маленькие. Самый большой компонент имеет логарифмический размер. Граф представляет собой псевдолес . Большинство его компонентов являются деревьями: число вершин в компонентах, имеющих циклы, растет медленнее, чем любая неограниченная функция числа вершин. Каждое дерево фиксированного размера встречается линейно много раз. ^[29]
Критический $p\approx 1/n$: Наибольшая компонента связности имеет число вершин, пропорциональное $n^{2/3}$ . Может существовать несколько других крупных компонентов; однако общее количество вершин в недревесных компонентах снова пропорционально $n^{2/3}$ . ^[30]
сверхкритический $p>(1+\varepsilon )/n$: Существует один гигантский компонент , содержащий линейное количество вершин. Для больших значений $p$ его размер приближается ко всему графу: $|C_{1}|\approx yn$ где $y$ является положительным решением уравнения $e^{-pny}=1-y$ . Остальные компоненты небольшие, логарифмического размера. ^[31]

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

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1look-1] Кларк, Джон; Холтон, Дерек Аллан (1995), Первый взгляд на теорию графов , Allied Publishers, стр. 28, ISBN 9788170234630 , заархивировано из оригинала 8 января 2022 г. , получено 7 января 2022 г.

[jnp-2] Джойнер, Дэвид; Нгуен, Минь Ван; Филлипс, Дэвид (10 мая 2013 г.), «1.6.1 Объединение, пересечение и объединение» , Algorithmic Graph Theory and Sage (изд. 0.8-r1991), Google, стр. 34–35, заархивировано из оригинала 16 января. , 2016 , получено 8 января 2022 г.

[tutte-betti-3] Перейти обратно: ^а ^б Тутте, WT (1984), Теория графов , Энциклопедия математики и ее приложений, том. 21, Ридинг, Массачусетс: Аддисон-Уэсли, с. 15, ISBN 0-201-13520-5 , MR 0746795 , заархивировано из оригинала 07 января 2022 г. , получено 7 января 2022 г.

[thuswa-4] Перейти обратно: ^а ^б Туласираман, К.; Свами, MNS (2011), Графики: теория и алгоритмы , John Wiley & Sons, стр. 9, ISBN 978-1-118-03025-7 , заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.

[bollobas-5] Боллобас, Белла (1998), Современная теория графов , Тексты для аспирантов по математике, том. 184, Нью-Йорк: Springer-Verlag, с. 6, номер домена : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7 , MR 1633290 , заархивировано из оригинала 8 января 2022 г. , получено 8 января 2022 г.

[mcnosh-6] Макколл, ВФ; Ношита, К. (1986), «О количестве ребер в транзитивном замыкании графа», Discrete Applied Mathematics , 15 (1): 67–73, doi : 10.1016/0166-218X(86)90020-X , МР 0856101

[foldes-7] Фолдс, Стефан (2011), Фундаментальные структуры алгебры и дискретной математики , John Wiley & Sons, стр. 199, ISBN 978-1-118-03143-8 , заархивировано из оригинала 7 января 2022 г. , получено 7 января 2022 г.

[boost-8] Сик, Джереми; Ли, Ли-Куан; Ламсдейн, Эндрю (2001), «7.1 Связные компоненты: определения», Библиотека графиков повышения: Руководство пользователя и справочное руководство , Аддисон-Уэсли, стр. 97–98.

[knuth-9] Кнут, Дональд Э. (15 января 2022 г.), «Слабые компоненты», Искусство компьютерного программирования, том 4, предварительный выпуск 12A: Компоненты и обход (PDF) , стр. 11–14, заархивировано (PDF) из оригинал 18 января 2022 г. , получено 1 марта 2022 г.

[lewzax-10] Льюис, Гарри ; Закс, Рэйчел (2019), «Основная дискретная математика для информатики» , Princeton University Press, стр. 145, ISBN 978-0-691-19061-7 , заархивировано из оригинала 8 января 2022 г. , получено 8 января 2022 г.

[kozen-11] Козен, Декстер К. (1992), «4.1 Двусвязные компоненты» , Проектирование и анализ алгоритмов , тексты и монографии по информатике, Нью-Йорк: Springer-Verlag, стр. 20–22, номер документа : 10.1007/978-1- 4612-4400-4 , ISBN 0-387-97687-6 , MR 1139767 , S2CID 27747202 , заархивировано из оригинала 8 января 2022 г. , получено 8 января 2022 г.

[wilson-12] Уилсон, Р.Дж. (1973), «Введение в теорию матроидов», The American Mathematical Monthly , 80 (5): 500–525, doi : 10.1080/00029890.1973.11993318 , JSTOR 2319608 , MR 0371694

[wood-13] Вуд, Дэвид Р. (2014), «Рисование трехмерных графов», Као, Мин-Янг (редактор), Энциклопедия алгоритмов (PDF) , Springer, стр. 1–7, doi : 10.1007/978-3 -642-27848-8_656-1 , заархивировано (PDF) из оригинала 8 января 2022 г. , получено 8 января 2022 г.

[cioaba-14] Чиоабэ, Себастьян М. (2011), «Некоторые применения собственных значений графов», в Демере, Маттиасе (редактор), « Структурный анализ сложных сетей» , Нью-Йорк: Birkhäuser/Springer, стр. 357–379, doi : 10.1007/ 978-0-8176-4789-6_14 , МР 2777924 ; см. доказательство леммы 5, с. 361. Архивировано 8 января 2022 г. в Wayback Machine.

[read-15] Рид, Рональд К. (1968), «Введение в хроматические полиномы», Журнал комбинаторной теории , 4 : 52–71, doi : 10.1016/S0021-9800(68)80087-0 , MR 0224505 ; см. теорему 2, с. 59 и следствие, с. 65

[tutte-matching-16] Тутте, WT (1947), «Факторизация линейных графов», Журнал Лондонского математического общества , 22 (2): 107–111, doi : 10.1112/jlms/s1-22.2.107 , MR 0023048

[berge-17] Берже, Клод (1958), «О максимальной связи графа», Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences , 247 : 258–259, MR 0100850

[chvatal-18] Хватал, Вацлав (1973), «Жесткие графы и гамильтоновы схемы», Дискретная математика , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR 0316301

[hoptar-19] Хопкрофт, Джон ; Тарьян, Роберт (июнь 1973 г.), «Алгоритм 447: эффективные алгоритмы манипулирования графами», Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272 , S2CID 14772567

[dst-20] Дилленкур, Майкл Б.; Самет, Ханан ; Тамминен, Маркку (1992), «Общий подход к маркировке связных компонентов для произвольных представлений изображений», Журнал ACM , 39 (2): 253–280, CiteSeerX 10.1.1.73.8846 , doi : 10.1145/128749.128750 , MR 1160258 , S2CID 1869184

[bengalloun-21] Бенгеллун, Сафван Абдельмаджид (декабрь 1982 г.), Аспекты инкрементальных вычислений (докторская диссертация), Йельский университет, стр. 12, ПроКвест 303248045

[skiena-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 г.

[wulff-nilsen-23] Вульф-Нильсен, Кристиан (2013), «Быстрая детерминированная полностью динамическая связность графов», Ханна, Санджив (редактор), Труды двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2013, Новый Орлеан, Луизиана , США, 6–8 января 2013 г. , стр. 1757–1769, arXiv : 1209.5608 , doi : 10.1137/1.9781611973105.126 , S2CID 13397958

[hhkp-24] Хуан, Шан-Эн; Хуан, Давэй; Копеловиц, Цви; Петти, Сет (2017), «Полностью динамическое подключение в $O{\bigl (}\log n(\log \log n)^{2}{\bigr )}$ амортизированное ожидаемое время», Кляйн, Филип Н. (ред.), Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, Hotel Porta Fira, 16–19 января , стр. 510. –520, arXiv : 1609.05867 , doi : 10.1137/1.9781611974782.32 , S2CID 15585534

[lewpap-25] Льюис, Гарри Р .; Пападимитриу, Христос Х. (1982), «Симметричные вычисления в пространстве», Theoretical Computer Science , 19 (2): 161–187, doi : 10.1016/0304-3975(82)90058-5 , MR 0666539

[reingold-26] Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): A17:1–A17:24, doi : 10.1145/1391289.1391291 , MR 2445014 , S2CID 207168478

[berkramal-27] Беренбринк, Петра; Крайенхофф, Брюс; Маллманн-Тренн, Фредерик (2014), «Оценка количества связанных компонентов в сублинейное время», Information Processing Letters , 114 (11): 639–642, doi : 10.1016/j.ipl.2014.05.008 , MR 3230913

[frikar-28] Фриз, Алан ; Каронски, Михал (2016), «1.1 Модели и отношения», Введение в случайные графы , Cambridge University Press, Кембридж, стр. 3–9, doi : 10.1017/CBO9781316339831 , ISBN 978-1-107-11850-8 , МР 3675279

[subcritical-29] Frieze & Karoński (2016) , 2.1 Подкритическая фаза, стр. 10-11. 20–33; см. особенно теорему 2.8, с. 26, теорема 2.9, с. 28 и лемма 2.11, с. 29

[critical-30] Frieze & Karoński (2016) , 2.3 Фазовый переход, стр. 39–45.

[supercritical-31] Frieze & Karoński (2016) , 2.2 Сверхкритическая фаза, стр. 33; см. особенно теорему 2.14, с. 33–39

[random-connectivity-32] Frieze & Karoński (2016) , 4.1 Связь, стр. 64–68.

[cohav-33] Коэн, Реувен; Хэвлин, Шломо (2010), «10.1 Проникновение в сложные сети: Введение» , Сложные сети: структура, надежность и функции , Cambridge University Press, стр. 97–98, ISBN 978-1-139-48927-0 , заархивировано из оригинала 10 января 2022 г. , получено 10 января 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]