Русская Википедия:Константа Чигера (теория графов)
Шаблон:Другие значения В математике константой Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразийШаблон:Sfn). Названа в честь математика Шаблон:Не переведено 5.
Определение
Пусть <math>G</math> — ненаправленный граф со множеством вершин <math>V(G)</math> и дуг <math>E(G)</math>. Пусть для набора вершин <math>A \subseteq V(G)</math> <math>\partial A</math> означает набор всех дуг, соединяющих вершины набора <math>A</math> с вершинами, не принадлежащими <math>A</math>Шаблон:Sfn:
- <math>\partial A := \{ (x, y) \in E(G) \mid x \in A, y \in V(G) \setminus A \}.</math>
Напомним, что дуги не направлены, так что дуга <math>(x, y)</math> — это та же дуга, что и <math>(y, x)</math>.
Тогда константа Чигера графа <math>G</math> (обозначается <math>h(G)</math>) определяется как
- <math>h(G) := \min \left\{ \left. \frac{| \partial A |}{| A |} \right| A \subseteq V(G), 0 < | A | \leqslant \frac{| V(G) |}{2} \right\}.</math>
Константа Чигера строго положительна тогда и только тогда, когда граф <math>G</math> связен. Интуитивно понятно, что если константа Чигера мала, но положительна, в графе есть «узкое место», в том смысле, что имеются два «больших» множества вершин с «небольшим» числом связей (дуг) между ними. Константа Чигера «велика», если любое деление множества вершин на два подмножества оставляет «большое» число связей между этими подмножествами.
Пример: компьютерная сеть
Представим себе, что необходимо разработать сетевую конфигурацию, в которой константа Чигера велика (по меньшей мере, существенно отличается от нуля), даже если |V(G)| (число компьютеров в сети) велико.
Например, имеется N ≥ 3 компьютеров, объединённых в кольцо, образуя граф GN. Пронумеруем компьютеры числами 1, 2, ..., N в кольце по часовой стрелке. C математической точки зрения имеется граф с множеством вершин
- <math>V(G_{N}) := \{ 1, 2, \dots, N \}</math>
и множество дуг
- <math>E(G_{N}) := \{ (1, 2), (2, 3), \dots, (N - 1, N), (N, 1) \}.</math>
Возьмём в качестве множества A <math>\lfloor N / 2 \rfloor</math> этих компьютеров, находящихся в цепочке:
- <math>A := \{ 1, 2, \dots, \lfloor N / 2 \rfloor \}.</math>
Ясно, что
- <math>\partial A = \{ (\lfloor N / 2 \rfloor, \lfloor N / 2 \rfloor + 1), (N, 1) \},</math>
так что
- <math>\frac{| \partial A |}{| A |} = \frac{2}{\lfloor N / 2 \rfloor} \to 0</math> при <math>N \to \infty.</math>
Этот пример показывает верхнюю границу константы Чигера h(GN), и она стремится к нулю при стремлении N к бесконечности. Следовательно, мы можем рассматривать сеть компьютеров, объединённых в кольцо, как состоящую из сплошных «узких мест» для больших N, и это понятно в практическом смысле. Стоит одному компьютеру в кольце выйти из строя, и скорость обмена резко упадёт. При выходе из строя двух не соединённых друг с другом компьютеров сеть распадётся на две несвязанные части.
Неравенство Чигера
Константа Чигера особенно важна в контексте графов-экспандеров, поскольку служит мерилом охвата графа его дугами. Так называемое неравенство Чигера связано со спектральным зазором и содержит константу Чигера.
См. также
- Алгебраическая связность
- Шаблон:Не переведено 5
- Проводимость графа
- Связность
- Экспандер (теория графов)
Примечания
Литература
