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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ясно, что

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

так что

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

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

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

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

См. также

• Алгебраическая связность
• Шаблон:Не переведено 5
• Проводимость графа
• Связность
• Экспандер (теория графов)

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья