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

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

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

Определение

Пусть $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\}.

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

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)}}

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

См. также

Примечания

^ Мор 1989 , с. 274–291.
^ Черногория и Тетали 2006 , стр. 237–354.

Ссылки

Мохар, Боян (1989). «Изопериметрические числа графов» . Журнал комбинаторной теории, серия B. 47 (3): 274–291. дои : 10.1016/0095-8956(89)90029-4 .
Черногория, Рави; Тетали, Прасад (2006). «Математические аспекты времен смешивания в цепях Маркова». Основы и тенденции теоретической информатики . 1 (3): 237–354. дои : 10.1561/0400000003 . ISSN 1551-305X .
Донетти, Лука; Нери, Франко; Муньос, Мигель А. (7 августа 2006 г.). «Оптимальные топологии сетей: расширители, клетки, графы Рамануджана, запутанные сети и все такое». Журнал статистической механики: теория и эксперимент . 2006 (08): P08007–P08007. arXiv : cond-mat/0605565 . Бибкод : 2006JSMTE..08..007D . дои : 10.1088/1742-5468/2006/08/P08007 . ISSN 1742-5468 . S2CID 16192273 .
Лакенби, Марк (2006). «Расщепление Хигора, практически гипотеза Хакена и свойство (τ)». Математические изобретения . 164 (2): 317–359. arXiv : math/0205327 . Бибкод : 2006InMat.164..317L . дои : 10.1007/s00222-005-0480-x . ISSN 0020-9910 . S2CID 12847770 .

[FOOTNOTEMohar1989274–291-1] Мор 1989 , с. 274–291.

[FOOTNOTEMontenegroTetali2006237–354-2] Черногория и Тетали 2006 , стр. 237–354.

[1]

[2]