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

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

Константа Чигера названа в честь математика Джеффа Чигера .

Определение

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

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

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

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

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

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

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

Например, рассмотрим кольцевую сеть из $N \geq 3$ компьютеров, рассматриваемую как граф $G N$ . Пронумеруйте компьютеры $1, 2, ..., N$ по часовой стрелке по кольцу. Математически набор вершин и набор ребер определяются как:

{\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$ как совокупность этих компьютеров в связанной цепочке: $\left\lfloor {\tfrac {N}{2}}\right\rfloor$

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

Так,

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

{\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .

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

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

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

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

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

Смотрите также

Примечания