Сума на кліку
Сума на кліці— теоретико-графова операція, що забезпечує комбінацію двох графів шляхом склеювання їх на кліці, аналогічно зв'язковій сумі в топології. Якщо два графи G і H містять кліки однакового розміру, сума по кліку утворюється з незв'язаного об'єднання графів шляхом ототожнення пар вершин з клік так, щоб утворити одну кліку з подальшим видаленням деяких ребер [1] . Сума по k -кліку - це сума по кліку, що містить не більше k вершин. Можна утворити суму по клікам і суму по -клікам більш ніж двох графів шляхом повторення операції суми.
Зміст
Суми за кліками важливі в структурній теорії графів, де вони використовуються для опису деяких сімейств графів як графів, утворених сумою за кліками менших графів. Першим результатом такого типу [3] була теорема Вагнера [4] , який довів, що графи, які не містять повних графів з п'ятьма вершинами як мінор, є сумою за 3-кликами планарних графів з графом Вагнера. За допомогою цієї структурної теореми можна показати, що проблема чотирьох фарб еквівалентна випадку k = 5 гіпотези Хадвігер. Хордальні графи - це точно графи, які можна утворити як суми клік по кліках без видалення ребер, а стислі графи - це графи, які можна утворити як суми без видалення ребер по клікам клік і максимальних планарних графів [en] [5] . Графи, в яких будь-який породжений цикл довжини чотири або більше утворює мінімальний розділяючий підграф (після його видалення граф розпадається на дві або більше незв'язні компоненти, і ніяке підмножина циклу не має те ж властивостей), є точно сумами по клікам клік і максимальних планарних графів , знову без видалення ребер [6] . Джонсон і Маккі [7] використовували суми на клікихордальних графів та паралельно-послідовних графів для опису частково визначених [8] матриць, що мають позитивно визначене довизначення.
Можна отримати розкладання за сумами за кліками для будь-якого сімейства графів, замкненого щодо операції мінора — графи в будь-якому мінорно-замкнутому сімействі можуть бути утворені із сум за кліками графів, які «майже вкладені» на поверхні кінцевого роду, що означає, що вкладення дозволено у уникнення невеликого числадахів(вершин, які можна з'єднати з довільним число інших вершин) іворонок(графи з вузькою колійною шириною, що замінюють грані при вкладенні на поверхню) [9] . Ці описи використовувалися як важливий засіб при побудові апроксимаційних алгоритмів та субекспоненційних за часом точних алгоритмів для NP-повних завдань оптимізації на мінорно-замкнутих сімействах графів [10] [11] [12] .
Теорію сум за кліками можна узагальнити від графів до матроїдів. Теорема розкладання Сеймура описує регулярні матроїди [en] (матроїди, що представляють цілком унімодулярні матриці) як 3-суми графічних матроїдів (матроїди, що представляють кістяки), графічні матроїди і деякі 10-елементні матроїди [13] .