Сума за клікою

Сума за клікою — теоретико-графова операція, що забезпечує комбінацію двох графів склеюванням їх за клікою, подібно до зв'язної суми в топології. Якщо два графи $G$ і $H$ містять кліки однакового розміру, сума за клікою утворюється з незв'язаного об'єднання графів ототожненням пар вершин із клік так, щоб утворити одну кліку, з подальшим видаленням деяких ребер^[1]. Сума за $k$ -клікою — це сума за клікою, яка містить не більше $k$ вершин. Можна утворити суму за кліками і суму за $k$ -кліками більше ніж двох графів повторенням операції суми.

Пов'язані концепції

Суми за клікою тісно пов'язані з деревною шириною — якщо деревна ширина двох графів не перевершує $k$ , то сума за $k$ -клікою буде мати таку саму властивість. Будь-яке дерево є сумою за 1-кліками його ребер. Будь-який паралельно-послідовний граф, або, узагальнено, будь-який граф з деревною шириною, що не перевищує двох, можна побудувати як суму за 2-кліками трикутників. Той самий результат узагальнюється для великих $k$ — будь-який граф, деревна ширина якого не перевершує $k$ , можна побудувати як суму за кліками графів з не більше ніж $k + 1$ вершинами, і в цьому випадку використовуються суми за $k$ -клікамиШаблон:Sfn.

Існує також близький зв'язок між сумами за кліками і зв'язністю графу — якщо граф не $(k + 1)$ -зв'язний вершинно (так що існує множина з $k$ вершин, видалення яких призводить до втрати зв'язності), то граф можна подати у вигляді суми за $k$ -кліками дрібніших графів. Наприклад, SPQR-дерево двозв'язного графу є поданням графу як суми за 2-кліками його тризв'язних компонент.

Застосування в структурній теорії графів

Суми за кліками важливі в структурній теорії графів, де вони використовуються для опису деяких родин графів як графів, утворених сумою за кліками графів меншого розміру. Першим результатом такого типу^[2] була теорема Вагнера Шаблон:Sfn, який довів, що графи, які не містять мінорами повних графів з п'ятьма вершинами, є сумою за 3-кліками планарних графів з графом Вагнера. За допомогою цієї структурної теореми можна показати, що проблема чотирьох фарб еквівалентна випадку $k = 5$ гіпотези Хадвігера. Хордальні графи — це точно графи, які можна утворити як суми клік за кліками без видалення ребер, а стиснуті графи — це графи, які можна утворити як суми без видалення ребер за кліками клік і найбільших планарних графів Шаблон:Sfn. Графи, в яких будь-який породжений цикл довжини чотири або більше утворює мінімальний розділювальний підграф (після його видалення граф розпадається на дві або більше незв'язних компонент, і жодна підмножина циклу не має такої ж властивості), є точно сумами за кліками клік і максимальних планарних графів, знову без видалення реберШаблон:Sfn. Джонсон і МаккіШаблон:Sfn використовували суми за кліками хордальних графів і паралельно-послідовних графів для опису частково визначених^[3] матриць, які мають додатно означене довизначення.

Можна отримати розклад за сумами за кліками для будь-якого сімейства графів, замкнутого відносно операції мінора — графи в будь-якому мінорно-замкнутому сімействі можна утворити з сум за кліками графів, які «майже вкладені» на поверхні скінченного роду, що означає, що вкладення дозволено щоб уникнути невеликого числа дахів (вершин, які можна з'єднати з довільним число інших вершин) і лійок (графи з малою шляховою шириною, які замінюють грані при вкладанні на поверхню)Шаблон:Sfn. Ці описи використовувалися як важливий засіб під час побудови апроксимаційних алгоритмів і субекспоненціальних за часом точних алгоритмів для NP-повних задач оптимізації на мінорно-замкнутих сімействах графівШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Узагальнення

Теорію сум за кліками можна узагальнити від графів до матроїдів. Теорема розкладання Сеймура описує Шаблон:Не перекладено (матроїди, які представляють цілком унімодулярні матриці) як 3-суми графічних матроїдів (матроїди, що представляють головні дерева), кографічні матроїди і деякі 10-елементні матроїдиШаблон:Sfn.

Примітки

Шаблон:Reflist

Література

↑ Тут є деяка невизначеність. У книзі Окслі (Шаблон:Sfn0) йдеться, що слід видалити всі ребра клік. Д. Епштейн (у поясненнях до англійського варіанта статті) стверджує, що в деяких застосуваннях можна вибирати, які ребра видаляти, а які можна залишити, а в деяких застосуваннях можна видаляти взагалі.
↑ Як зазначили Криж і Томас (Шаблон:Sfn0), які перелічили деякі додаткові описи сімейств графів, що спираються на суми за кліками.
↑ Частково визначена матриця — це матриця, не всі клітинки якої заповнено. Такі матриці використовують у теорії експертних оцінок, в рекомендаційних системах.

[1] Тут є деяка невизначеність. У книзі Окслі (Шаблон:Sfn0) йдеться, що слід видалити всі ребра клік. Д. Епштейн (у поясненнях до англійського варіанта статті) стверджує, що в деяких застосуваннях можна вибирати, які ребра видаляти, а які можна залишити, а в деяких застосуваннях можна видаляти взагалі.

[2] Як зазначили Криж і Томас (Шаблон:Sfn0), які перелічили деякі додаткові описи сімейств графів, що спираються на суми за кліками.

[3] Частково визначена матриця — це матриця, не всі клітинки якої заповнено. Такі матриці використовують у теорії експертних оцінок, в рекомендаційних системах.

[1]

[2]

[3]

Сума за клікою

Зміст

Пов'язані концепції

Застосування в структурній теорії графів

Узагальнення

Примітки

Література

Навігаційне меню

Сума за клікою

Пов'язані концепції

Застосування в структурній теорії графів

Узагальнення

Примітки

Література

Навігаційне меню

Пошук