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

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

ОпределениеПравить

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

$\mathrm{\partial <!--\; \partial \; -->}A:=\{(x,y)\in <!--\; \in \; -->E(G)\mid <!--\; \mid \; -->x\in <!--\; \in \; -->A,y\in <!--\; \in \; -->V(G)\setminus <!--\; \setminus \; -->A\}.$$\partial A:=\{(x,y)\in E(G)\mid x\in A,y\in V(G)\setminus A\}.$ 

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

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

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

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

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

 

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

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

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

$V(G_N):=\{1,2,\dots <!--\; \dots \; -->,N\}$$V(G_{N}):=\{1,2,\dots ,N\}$ 

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

$E(G_N):=\{(1,2),(2,3),\dots <!--\; \dots \; -->,(N-<!--\; -\; -->1,N),(N,1)\}.$$E(G_{N}):=\{(1,2),(2,3),\dots ,(N-1,N),(N,1)\}.$ 

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

$A:=\{1,2,\dots <!--\; \dots \; -->,\lfloor <!--\; \lfloor \; -->N/2\rfloor <!--\; \rfloor \; -->\}.$$A:=\{1,2,\dots ,\lfloor N/2\rfloor \}.$ 

Ясно, что

$\mathrm{\partial <!--\; \partial \; -->}A=\{(\lfloor <!--\; \lfloor \; -->N/2\rfloor <!--\; \rfloor \; -->,\lfloor <!--\; \lfloor \; -->N/2\rfloor <!--\; \rfloor \; -->+1),(N,1)\},$$\partial A=\{(\lfloor N/2\rfloor ,\lfloor N/2\rfloor +1),(N,1)\},$ 

так что

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

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

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

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

См. такжеПравить

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

ЛитератураПравить

• Donetti, L., Neri, F., and Muñoz, M. Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that // J. Stat. Mech. — 2006. — Т. 2006, вып. 08. — doi:10.1088/1742-5468/2006/08/P08007.
• Lackenby, M. Heegaard splittings, the virtually Haken conjecture and property (τ) // Invent. Math. — 2006. — Т. 164, вып. 2. — С. 317—359. — doi:10.1007/s00222-005-0480-x.
• Mark Lackenby. Finite covering spaces of 3-manifolds // Proceedings of the International Congress of Mathematicians. Hyderabad, India. — 2010.
• Alexander Lubotzky. Expander Graphs in Pure and Applied Mathematics // This paper is based on notes prepared for the Colloquium Lectures at the Joint Annual Meeting of the American Mathematical Society (AMS) and the Mathematical Association of America (MAA). — 2011.