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

У этого термина существуют и другие значения, см. Константа Чигера.

В математике константой Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий^[1]). Названа в честь математика Джефа Чигера^[англ.].

Определение

Пусть ${\displaystyle G}$ — ненаправленный граф со множеством вершин ${\displaystyle V(G)}$ и дуг ${\displaystyle E(G)}$. Пусть для набора вершин ${\displaystyle A\subseteq V(G)}$ ${\displaystyle \partial A}$ означает набор всех дуг, соединяющих вершины набора ${\displaystyle A}$ с вершинами, не принадлежащими ${\displaystyle A}$^[2]:

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

Напомним, что дуги не направлены, так что дуга ${\displaystyle (x,y)}$ — это та же дуга, что и ${\displaystyle (y,x)}$.

Тогда константа Чигера графа ${\displaystyle G}$ (обозначается ${\displaystyle h(G)}$) определяется как

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

Константа Чигера строго положительна тогда и только тогда, когда граф ${\displaystyle G}$ связен. Интуитивно понятно, что если константа Чигера мала, но положительна, в графе есть «узкое место», в том смысле, что имеются два «больших» множества вершин с «небольшим» числом связей (дуг) между ними. Константа Чигера «велика», если любое деление множества вершин на два подмножества оставляет «большое» число связей между этими подмножествами.

Пример: компьютерная сеть

Сеть компьютеров «кольцо»

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

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

${\displaystyle V(G_{N}):=\{1,2,\dots ,N\}}$

и множество дуг

${\displaystyle E(G_{N}):=\{(1,2),(2,3),\dots ,(N-1,N),(N,1)\}.}$

Возьмём в качестве множества A ${\displaystyle \lfloor N/2\rfloor }$ этих компьютеров, находящихся в цепочке:

${\displaystyle A:=\{1,2,\dots ,\lfloor N/2\rfloor \}.}$

Ясно, что

${\displaystyle \partial A=\{(\lfloor N/2\rfloor ,\lfloor N/2\rfloor +1),(N,1)\},}$

так что

${\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\lfloor N/2\rfloor }}\to 0}$ при ${\displaystyle N\to \infty .}$

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

Неравенство Чигера

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

См. также

• Алгебраическая связность
• Граница Чигера^[англ.]*
• Проводимость графа
• Связность
• Экспандер (теория графов)