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

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

Определение

Пусть — ненаправленный граф со множеством вершин и дуг . Пусть для набора вершин означает набор всех дуг, соединяющих вершины набора с вершинами, не принадлежащими [2]:

Напомним, что дуги не направлены, так что дуга — это та же дуга, что и .

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

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

Пример: компьютерная сеть

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

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

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

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

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

Ясно, что

так что

при

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

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

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

См. также

Примечания

  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.