В теории графов компонент, иногда называемый связным компонентом, неориентированного графа - это подграф, в котором любые две вершины равны соединены друг с другом путями и не связаны ни с какими дополнительными вершинами в суперграфе. Например, график, показанный на иллюстрации, состоит из трех компонентов. Вершина без инцидентных ребер сама по себе является компонентом. Граф, который сам является связным, имеет ровно одну компоненту, состоящую из всего графа.
Альтернативный способ определения компонентов включает классы эквивалентности отношения эквивалентности, которое определено в вершинах графа. В неориентированном графе вершина v достижима из вершины u, если существует путь от u до v. В этом определении одна вершина считается путем нулевой длины, и одна и та же вершина может встречаться более одного раза в пределах путь. Достижимость - это отношение эквивалентности, так как:
Компоненты тогда являются индуцированными подграфами, образованными эквивалентностью классы этого отношения.
Количество компонентов является важным топологическим инвариантом графа. В теории топологических графов его можно интерпретировать как нулевое число Бетти графа. В теории алгебраических графов он равен кратности 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.
В случайных графах размеры компонентов задаются случайной величиной, которая, в свою очередь, зависит от конкретной модели.
Модель имеет три области с кажущимся разным поведением:
субкритический : Все компоненты простые и очень маленькие, самый большой компонент имеет размер ;
критический : ;
сверхкритический : где - положительное решение уравнения
где и соответственно являются наибольшим и вторым по величине компонентами. Все остальные компоненты имеют размер порядка