Стала Чігера (теорія графів)

У математиці сталою Чіґера (також числом Чіґера або ізопериметричним числом) графа називають числову характеристику графа, яка показує, має граф «вузьке місце» чи ні. Константа Чигера як спосіб вимірювання наявності «вузького місця» становить інтерес у багатьох галузях, наприклад, для створення сильно зв'язаних комп'ютерних мереж, для тасування карт і в топології малих розмірностей (зокрема, при вивченні гіперболічних 3-вимірних многовидів). Названа на честь математика Джефа Чіґера.

Визначення

Нехай ${\displaystyle G}$ — ненапрямлений граф із множиною вершин ${\displaystyle V(G)}$ та дуг ${\displaystyle E(G)}$. Нехай для набору вершин ${\displaystyle A\subseteq V(G)}$${\displaystyle \partial A}$ означає набір всіх дуг, що з'єднують вершини набору ${\displaystyle A}$ з вершинами, які не належать ${\displaystyle A}$:

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

Нагадаємо, що дуги не напрямлені, тож дуга ${\displaystyle (x,y)}$ — це та сама дуга, що й ${\displaystyle (y,x)}$.

Тоді стала Чіґера графа ${\displaystyle G}$ (позначається ${\displaystyle h(G)}$) визначається як

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

Стала Чіґера строго додатна тоді й лише тоді, коли граф ${\displaystyle G}$ зв'язний. Інтуїтивно зрозуміло, що якщо стала Чіґера мала, але додатна, граф має «вузьке місце» в тому сенсі, що є дві «великі» множини вершин з «невеликим» числом зв'язків (дуг) між ними. Стала Чіґера «велика», якщо будь-який поділ множини вершин на дві підмножини залишає «багато» зв'язків між цими підмножинами.

Приклад: комп'ютерна мережа

Мережа комп'ютерів «кільце»

Уявімо, що необхідно розробити мережеву конфігурацію, в якій стала Чіґера велика (принаймні, істотно відрізняється від нуля), навіть якщо ${\displaystyle |V(G)|}$ (число комп'ютерів у мережі) велике.

Наприклад, є ${\displaystyle N\geq 3}$ комп'ютерів, об'єднаних у кільце, утворюючи граф ${\displaystyle G_{N}}$. Пронумеруємо комп'ютери числами 1, 2, …, N у кільці за годинниковою стрілкою. З математичної точки зору є граф із множиною вершин

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

і множина дуг

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

Візьмемо як множину ${\displaystyle A}$ ${\displaystyle \lfloor N/2\rfloor }$ цих комп'ютерів, що в ланцюжку:

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

Зрозуміло, що

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

так що

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

Цей приклад показує верхню межу константи Чіґера ${\displaystyle h(G_{N})}$, і вона прямує до нуля при пямуванні ${\displaystyle N}$ до нескінченності. Отже, ми можемо розглядати мережу комп'ютерів, об'єднаних у кільце, що складається зі суцільних «вузьких місць» для великих ${\displaystyle N}$, і це зрозуміло в практичному сенсі. Варто одному комп'ютеру в кільці вийти з ладу і швидкість обміну різко впаде. При виході з ладу двох не з'єднаних між собою комп'ютерів мережа розпадеться на дві незв'язані частини.

Нерівність Чіґера

Докладніше: (Спектральна_теорія_графів#Нерівність_Чігера)

Стала Чіґера особливо важлива в контексті графів-експандерів, оскільки є мірою охоплення графа його дугами. Так звана (нерівність Чіґера) пов'язана зі спектральним зазором і містить сталу Чіґера.

Див. також

• Стала Чіґера
• Алгебрична зв'язність
• ^[en]
• Провідність графа
• Зв'язний граф
• Збільшувач (теорія графів)

Примітки

1. Lackenby, 2010, §7 The behaviour of geometric and topological invariants in finite covers, p. 13.
2. Lubotzky, 2011, Глава 1. Expander graphs. 1.1 Basic definitions. P. 5.

Література

• 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.