Число - незалежність - Велика Енциклопедія Нафти та Газа, стаття 2
Число – незалежність
Якщо кінцевий граф з п вершинами має невелике число ребер, слід очікувати, що його число незалежності буде відносно великим. [16]
Перше питання еквівалентне визначенню числа домінування човнів на дошці п X п X п, а друге - визначенню числа незалежності. [17]
Враховуючи класичну рівність з теорії графів: а0 р р cXj p, укладаємо, що потрібно лише згадати задачі перерахування графів з даним вершинним числом незалежності Ро і з даним числом рх. Перерахування графів за цими параметрами здається інтуїтивно легшим, ніж перерахування графів із даними числами покриттів; однак із наведеної вище рівності це не випливає. [18]
Нехай G – довільний граф, дводольний чи ні, v (G) – реберне число незалежності (або, в іншій термінології, число паро-поєднання) графа G, т (С) – число вершинного покриття, a (G) – вершинне число незалежності і p(G) - число реберного покриття. [19]
Важливо відразу помітити, що у разі числа незалежності існує значне різницю між отриманням верхньої і нижньої оцінок. Нижня оцінка числа незалежності означає існування незалежної множини вершин досить великого розміру. Один спосіб знайти таку нижню оцінку полягає в тому, щоб дати алгоритм, який породжує велику (хоча не обов'язково найбільшу) незалежну множину у будь-якому графі. Такий алгоритм часто називають евристикою для задачі про вершинні упаковки. [20]
Для найменших значень п, 2, 3, 4 вона легко перевіряється безпосередньо. При видаленні ребра з графа число незалежності може лише зрости на одиницю. [21]
Для найменших значень п1, 2, 3, 4 легко перевіряється безпосередньо. Привидалення ребра з графа число незалежності може хіба що зрости на одиницю. [22]
Безліч вершин графа G називається незалежним, якщо жодні з них не суміжні. Найбільше вершин у таких множинах називається вершинним числом незалежності графа G і позначається P0 (G) або рс. G) p / 2 і тоді, коли G має 1-фактор. [23]
Кожній шахівці можна поставити у відповідність граф, вершини якого розташовані на всіх 64 полях дошки, а ребра відповідають ходам цієї фігури. Тепер легко переконатись у тому, що наша перша проблема полягає у визначенні числа незалежності для графа даної фігури, а друга проблема – у визначенні числа домінування. [24]
Тоді, образно кажучи, у щільного графа число кліків буде, ймовірно, більше, а число незалежності менше, у той час як у розрідженого графа, ймовірно, матиме місце протилежне співвідношення між цими числами. [25]
Безліч вершин (ребер) називається незалежним, якщо жодні два його елементи є суміжними. Реберне число незалежності (Зг визначається аналогічно. Числом вершинного покриття а графа G називається найменша кількість вершин, що покривають усі ребра графа; число реберного покриття al графа G визначається подібним чином. [26]
Безліч вершин (ребер) називається незалежним, якщо жодні два його елементи є суміжними. Реберна кількість незалежності р визначається аналогічно. Числом вершинного покриття а графа G називається найменша кількість вершин, що покривають усі ребра графа; число реберного покриття at графа G визначається так. [27]
Ми завершуємо цей розділ розглядом ще однієї з еквівалентних теорем про дводольне паросомовчання, що також належить Кенігу (пор. Нагадаємо, щореберне покриття графа G - це безліч ребер, що покривають (в сукупності) кожну вершину в G, і що p (G є найменша з потужностей реберних покриттів графа G. Як і раніше, через a (G) позначається (вершинне) число незалежності. Галлаї (див. 1.0.1 та 1.0.2) разом з теоремою Кеніга дозволяють нам легко встановити наступний результат.[28]
Встановлений зв'язок між суто математичними об'єктами - графами і завданнями про шахові постаті, як ми бачили, досить природна, чим і пояснюється більша популярність шахових термінів і завдань у літературі з теорії графів. Багато завдань про графи, дуже складні у випадку, вдається вирішити для графів шахових постатей. Саме така справа і з завданнями про незалежність і домінування HI шахівниці. Нижче ми знайдемо числа незалежності та домінування для графів усіх шахових постатей і, отже, вирішимо для них обидві наші проблеми. [29]
Тепер накидаємо ідею алгоритму, який доведеться розглянути. Насамперед ми маємо описати дві локальні конфігурації, такі, що й будь-яка їх зустрічається, ми можемо легко звести завдання одному меншому графу. Нирок таких локальних конфігурацій та виконання відомості можуть бути зроблені за поліноміальний час, і тому такі відомості призводять до поліноміального за часом алгоритму. Читачеві слід зауважити, що зведення цієї проблеми до знаходження числа незалежності двох менших графів є досить тривіальним. Однак така інформація веде до алгоритму з експоненційним часом виконання, в чому читач може легко переконатися. [30]