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