Loading AI tools
числова характеристика графа, яка показує, чи має він «вузьке місце» З Вікіпедії, вільної енциклопедії
У математиці сталою Чіґера (також числом Чіґера або ізопериметричним числом) графа називають числову характеристику графа, яка показує, має граф «вузьке місце» чи ні. Константа Чигера як спосіб вимірювання наявності «вузького місця» становить інтерес у багатьох галузях, наприклад, для створення сильно зв'язаних комп'ютерних мереж, для тасування карт і в топології малих розмірностей (зокрема, при вивченні гіперболічних 3-вимірних многовидів[1]). Названа на честь математика Джефа Чіґера.
Нехай — ненапрямлений граф із множиною вершин та дуг . Нехай для набору вершин означає набір всіх дуг, що з'єднують вершини набору з вершинами, які не належать [2]:
Нагадаємо, що дуги не напрямлені, тож дуга — це та сама дуга, що й .
Тоді стала Чіґера графа (позначається ) визначається як
Стала Чіґера строго додатна тоді й лише тоді, коли граф зв'язний. Інтуїтивно зрозуміло, що якщо стала Чіґера мала, але додатна, граф має «вузьке місце» в тому сенсі, що є дві «великі» множини вершин з «невеликим» числом зв'язків (дуг) між ними. Стала Чіґера «велика», якщо будь-який поділ множини вершин на дві підмножини залишає «багато» зв'язків між цими підмножинами.
Уявімо, що необхідно розробити мережеву конфігурацію, в якій стала Чіґера велика (принаймні, істотно відрізняється від нуля), навіть якщо (число комп'ютерів у мережі) велике.
Наприклад, є комп'ютерів, об'єднаних у кільце, утворюючи граф . Пронумеруємо комп'ютери числами 1, 2, …, N у кільці за годинниковою стрілкою. З математичної точки зору є граф із множиною вершин
і множина дуг
Візьмемо як множину цих комп'ютерів, що в ланцюжку:
Зрозуміло, що
так що
Цей приклад показує верхню межу константи Чіґера , і вона прямує до нуля при пямуванні до нескінченності. Отже, ми можемо розглядати мережу комп'ютерів, об'єднаних у кільце, що складається зі суцільних «вузьких місць» для великих , і це зрозуміло в практичному сенсі. Варто одному комп'ютеру в кільці вийти з ладу і швидкість обміну різко впаде. При виході з ладу двох не з'єднаних між собою комп'ютерів мережа розпадеться на дві незв'язані частини.
Стала Чіґера особливо важлива в контексті графів-експандерів, оскільки є мірою охоплення графа його дугами. Так звана нерівність Чіґера пов'язана зі спектральним зазором і містить сталу Чіґера.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.