WikiSort.ru - Не сортированное

Константа Чигера

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

Формально, константа Чигера ${\displaystyle h(G)}$ графа ${\displaystyle G}$ с ${\displaystyle n}$ вершинами определяется как

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

где минимум берётся по всем непустым множествам ${\displaystyle S}$ с максимум ${\displaystyle n/2}$ вершинами и ${\displaystyle \partial (S)}$ — рёберная граница множества ${\displaystyle S}$ , то есть множество рёбер, имеющих в точности одну конечную вершину в ${\displaystyle S}$ ^[6].

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

Если граф ${\displaystyle G}$ является ${\displaystyle d}$ -регулярным, существует связь между ${\displaystyle h(G)}$ и спектральным промежутком ${\displaystyle d-\lambda _{2}}$ графа ${\displaystyle G}$ . Неравенство Чигера исследовали Таннер, Алон и Мильман^[7]. Неравенство утверждает, что^[8]

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

Это неравенство тесно связано с границей Чигера^[en] для цепей Маркова и его можно рассматривать как дискретную версию неравентства Чигера в римановой геометрии.