Связность графа

Свя́зность гра́фа, одна из топологических характеристик графа. Граф называется связным, если для любых его вершин ${\displaystyle u}$ и ${\displaystyle v}$ существует цепь, соединяющая эти вершины. Числом вершинной связности графа ${\displaystyle G}$ (обозначение ${\displaystyle \varkappa (G)}$) называется наименьшее число вершин, удаление которых (вместе с инцидентными им рёбрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом рёберной связности (обозначение ${\displaystyle \lambda (G)}$) называется наименьшее число рёбер графа ${\displaystyle G}$, удаление которых приводит к несвязному графу. Граф ${\displaystyle G}$ называется ${\displaystyle k}$-связным, если ${\displaystyle \varkappa (G)\geqslant k}$, и ${\displaystyle k}$-рёберно связным, если ${\displaystyle \lambda (G)\geqslant k}$. Максимальный по включению ${\displaystyle k}$-связный подграф графа ${\displaystyle G}$ называется его ${\displaystyle k}$-связной компонентой; 1-связная компонента называется компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надёжности этих сетей.

В теории графов изучаются способы установления связности графов, условия, при которых граф является ${\displaystyle k}$-связным или ${\displaystyle k}$-рёберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если ${\displaystyle \delta (G)}$ – минимальная степень вершин графа ${\displaystyle G}$, то справедливы следующие неравенства: ${\displaystyle \varkappa (G)\leqslant \lambda (G)\leqslant \delta (G)}$.

Для любых целых ${\displaystyle a,b,c}$ (${\displaystyle 0<a\leqslant b\leqslant c}$) существует граф ${\displaystyle G}$, у которого ${\displaystyle \varkappa (G)=a}$, ${\displaystyle \lambda (G)=b}$, ${\displaystyle \delta (G)=c}$. Если граф ${\displaystyle G}$ имеет ${\displaystyle n}$ вершин и ${\displaystyle \delta (G)\geqslant \left[{\dfrac {n}{2}}\right]}$, то ${\displaystyle \lambda (G)=\delta (G)}$. Говорят, что множество ${\displaystyle S}$ вершин, рёбер или вершин и рёбер разделяет вершины ${\displaystyle u}$ и ${\displaystyle v}$, если ${\displaystyle u}$ и ${\displaystyle v}$ принадлежат разным компонентам связности графа ${\displaystyle G-S}$, полученного из ${\displaystyle G}$ удалением элементов множества ${\displaystyle S}$. Справедливы следующие утверждения.

Наименьшее число вершин, разделяющих две несмежные вершины ${\displaystyle u}$ и ${\displaystyle v}$, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих ${\displaystyle u}$ и ${\displaystyle v}$. Граф ${\displaystyle G}$ является ${\displaystyle k}$-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере ${\displaystyle k}$ вершинно непересекающимися цепями. Аналогичные теоремы справедливы и для рёберной связности. Граф ${\displaystyle k}$-рёберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере ${\displaystyle k}$-рёберно непересекающимися цепями. Множество рёбер, удаление которых приводит к несвязному графу, называется разрезом. В каждом графе наибольшее число рёберно непересекающихся разрезов, разделяющих вершины ${\displaystyle u}$ и ${\displaystyle v}$, равно наименьшему числу рёбер простой цепи, соединяющей ${\displaystyle u}$ и ${\displaystyle v}$, т. е. расстоянию ${\displaystyle d(u,v)}$ между ${\displaystyle u}$ и ${\displaystyle v}$.