В теории графов связный граф G называется k -вершинно-связным (или k -связным ), если он имеет более k вершин и остается связным всякий раз, когда удаляется менее k вершин.
Вершинная связность или просто связность графа — это наибольшее k , для которого граф является k -вершинно связным.
Граф (кроме полного графа ) имеет связность k, если k — размер наименьшего подмножества вершин, при котором граф становится несвязным, если вы их удаляете. [1] В полных графах не существует подмножества, удаление которого отключило бы граф. Некоторые источники изменяют определение связности для обработки этого случая, определяя его как размер наименьшего подмножества вершин, удаление которых приводит либо к отключению графа, либо к одной вершине. Для этого варианта связность полного графа равна . [2]
Эквивалентное определение состоит в том, что граф, имеющий по крайней мере две вершины, является k -связным, если для каждой пары его вершин можно найти k независимых от вершин путей , соединяющих эти вершины; см. теорему Менгера (Diestel 2005, стр. 55). Это определение дает тот же ответ, n − 1, для связности полного графа K n . [1] Очевидно, что согласно этому определению полный граф с n вершинами имеет связность n − 1.
1-связный граф называется связным ; 2-связный граф называется двусвязным . Трехсвязный граф называется трехсвязным.
Любой граф распадается на дерево 1-связных компонент . 1-связные графы разлагаются в дерево двусвязных компонент . 2-связные графы распадаются на дерево трехсвязных компонент .
1- скелет любого k -мерного выпуклого многогранника образует k -вершинно-связный граф ( теорема Балинского ). [3] В качестве частичного обратного утверждения теорема Стейница утверждает, что любой планарный граф, связанный с 3 вершинами, образует скелет выпуклого многогранника .
Связность вершин входного графа G можно вычислить за полиномиальное время следующим образом [4]: рассмотреть все возможные пары несмежных узлов для отключения, используя теорему Менгера для обоснования того, что сепаратор минимального размера для - это количество попарных вершин -независимые пути между ними, кодировать входные данные, удваивая каждую вершину как ребро, чтобы свести к вычислению количества попарных путей, независимых от ребер, и вычислять максимальное количество таких путей, вычисляя максимальный поток в графе между и с пропускная способность 1 для каждого ребра, отметив, что поток в этом графе соответствует, по теореме об интегральном потоке , попарным, независимым от ребра путям из в .
