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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ясно, что,

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

так что

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

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

Неравенство Чигера[править | править вики-текст]

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

Смотрите также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Donetti, L., Neri, F., and Muñoz, M. Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that // J. Stat. Mech.. — 2006. — В. 08. — Т. 2006. — DOI:10.1088/1742-5468/2006/08/P08007
  • Lackenby, M. Heegaard splittings, the virtually Haken conjecture and property (τ) // Invent. Math.. — 2006. — В. 2. — Т. 164. — С. 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.