Константа Чигера (теория графов)

Пусть граф G — конечный неориентированный граф с множеством вершин V(G) и множеством рёбер E(G). Для подмножества вершин A ⊆ V(G) пусть ∂A — множество всех рёбер, соединяющих вершину из A с вершиной вне A (иногда называется рёберной гранью множества A):

${\displaystyle \partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.}$

Заметим, что рёбра неориентированы, то есть ${\displaystyle \{x,y\}=\{y,x\}}$. Константа Чигера графа G, обозначаемая как h(G), определяется следующим образом^[1]:

${\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}$

Константа Чигера строго положительна в том и только в том случае, если G — связный граф. Интуитивно: если константа Чигера мала, но положительна, то существует «узкое место» — две большие группы вершин соединены малым числом рёбер. Константа Чигера «велика», если любое разбиение множества вершин на два подмножества приводит к большому числу рёбер между этими подмножествами.

В теоретической информатике стремятся создавать такие топологии сетей, для которых константа Чигера велика (или, по крайней мере, ограничена снизу ненулевой величиной), даже если |V(G)| (число компьютеров в сети) велико.

Например, рассмотрим кольцевую сеть из N ≥ 3 компьютеров, представленную графом G_N. Пронумеруем компьютеры 1, 2, ..., N по кольцу. Тогда множество вершин и множество рёбер задаются так:

${\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}$

Возьмём A — цепочку из ${\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }$ подряд идущих компьютеров:

${\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}$

Тогда

${\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}$

а

${\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\rightarrow 0{\mbox{ при }}N\rightarrow \infty .}$

Этот пример даёт верхнюю оценку для константы Чигера h(G_N), которая также стремится к нулю при N \rightarrow \infty. Следовательно, кольцевая сеть при большом N считается сильно «узкой» (имеет бутылочное горлышко), что крайне нежелательно на практике. Достаточно отказа одного компьютера на кольце, чтобы сильно снизить производительность сети. Если два не соседних компьютера выйдут из строя, сеть разделится на две несвязанные части.

Константа Чигера особенно важна для экспандерных графов, поскольку она характеризует рёберную экспансию графа. Так называемые неравенства Чигера связывают спектральный разрыв графа с его константой Чигера. Более конкретно:

${\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}$

где ${\displaystyle \Delta (G)}$ — максимальная степень вершин графа ${\displaystyle G}$, а ${\displaystyle \lambda }$ — спектральный разрыв матрицы Лапласа графа^[2]. Неравенство Чигера — фундаментальный результат и мотивация для исследования спектральной теории графов.