Константа Чигера (теория графов) - Cheeger constant (graph theory)
Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты.Февраль 2013) (Узнайте, как и когда удалить этот шаблон сообщения) ( |
В математика, то Постоянная Чигера (также Число Чигера или же изопериметрическое число) из график - это числовая мера того, есть ли у графа «узкое место». Константа Чигера как мера «узких мест» представляет большой интерес во многих областях: например, при построении хорошо связанных сети компьютеров, тасование карт. Теоретические представления о графах возникли после Изопериметрическая константа Чигера из компактный Риманово многообразие.
Константа Чигера названа в честь математик Джефф Чигер.
Определение
Позволять грамм - неориентированный конечный граф с множеством вершин V(грамм) и набор кромок E(грамм). Для набора вершин А ⊆ V(грамм), позволять ∂А обозначим совокупность всех ребер, выходящих из вершины в А в вершину вне А (иногда называют граница края из А):
Обратите внимание, что края неупорядочены, т.е. . В Постоянная Чигера из грамм, обозначенный час(грамм), определяется[1]
Постоянная Чигера строго положительна если и только если грамм это связный граф. Интуитивно, если константа Чигера мала, но положительна, то существует «узкое место» в том смысле, что есть два «больших» набора вершин с «несколькими» связями (ребрами) между ними. Константа Чигера является «большой», если любое возможное разделение набора вершин на два подмножества имеет «много» связей между этими двумя подмножествами.
Пример: компьютерная сеть
В приложениях к теоретической информатике желательно разработать сетевые конфигурации, для которых константа Чигера высока (по крайней мере, отделена от нуля), даже если |V(грамм)| (количество компьютеров в сети) большое.
Например, рассмотрим кольцевая сеть из N ≥ 3 компьютеры, представленные в виде графика граммN. Пронумеруйте компьютеры 1, 2, ..., N по часовой стрелке по кольцу. Математически набор вершин и набор ребер задаются следующим образом:
Брать А быть собранием этих компьютеров в связанной цепочке:
Так,
и
В этом примере приводится верхняя граница постоянной Чигера. час(граммN), который также стремится к нулю при N → ∞. Следовательно, мы будем рассматривать кольцевую сеть как «узкое место» для больших N, а это крайне нежелательно с практической точки зрения. Нам понадобится только один из компьютеров в кольце, чтобы выйти из строя, и производительность сети значительно снизится. В случае выхода из строя двух несмежных компьютеров сеть разделится на два отключенных компонента.
Cheeger Inequalities
Константа Чигера особенно важна в контексте графики расширения так как это способ измерить рёбер графа. Так называемой Неравенства Чигера свяжите разрыв собственных значений графа с его постоянной Чигера. Более подробно
в котором - максимальная степень для узлов в и это спектральный промежуток из Матрица лапласа графа.[2]
Смотрите также
- Алгебраическая связность
- Чигер связан
- Проводимость (график)
- Связность (теория графов)
- График расширителя
Рекомендации
- ^ Мохар, Боян (Декабрь 1989 г.). «Изопериметрические числа графиков». Журнал комбинаторной теории, серия B. 47 (3): 274–291. Дои:10.1016/0095-8956(89)90029-4. HDL:10338.dmlcz / 128408.
- ^ Черногория, Рави; Тетали, Прасад (2006). «Математические аспекты времен перемешивания в цепях Маркова». Найденный. Trends Theor. Comput. Sci: 90–94. Цитировать журнал требует
| журнал =
(помощь)
- Donetti, L .; Нери Ф. и Муньос М. (2006). «Оптимальные сетевые топологии: расширители, клетки, графы Рамануджана, запутанные сети и все такое». J. Stat. Мех. 2006 (08): P08007. arXiv:cond-mat / 0605565. Bibcode:2006JSMTE..08..007D. Дои:10.1088 / 1742-5468 / 2006/08 / P08007.
- Лакенби, М. (2006). «Расщепления Хегора, фактически гипотеза Хакена и свойство (τ)». Изобретать. Математика. 164 (2): 317–359. arXiv:математика / 0205327. Bibcode:2006InMat.164..317L. Дои:10.1007 / s00222-005-0480-х.