Сума на клик
Сума чрез щракванее теоретико-графична операция, която осигурява комбинация от две графики чрез слепването им чрез щракване, подобно на свързана сума в топологията. Ако две графи G и H съдържат клики с еднакъв размер, сумата от клики се формира от несвързано обединение на графи чрез идентифициране на двойки върхове от клики, така че да образуват една клика, и след това премахване на някои ребра [1] . Сумата на k-щракване е сумата на клик, съдържаща не повече от k върха. Възможно е да се формира сума на клика и сума на k-клика на повече от две графики чрез повтаряне на операцията за сумиране.
Съдържание
Кликовите суми са важни в теорията на структурните графи, където се използват за описание на определени фамилии от графики като графики, образувани от кликовата сума на по-малки графи. Първият резултат от този тип [3] беше теоремата на Вагнер [4], която доказва, че графи, които не съдържат пълни графи с пет върха като второстепенни, са суми върху 3-клики от равнинни графи с граф на Вагнер. Използвайки тази структурна теорема, може да се покаже, че проблемът с четирите цвята е еквивалентен на случай k = 5 на хипотезата на Hadwiger. Хордовите графи са точно графиките, които могат да бъдат формирани като суми от клики върху клики без изтриване на ребра, а свитите графи са графики, които могат да бъдат формирани като суми без изтриване на ребра върху клики и максимални равнинни графи [en] [5] . Графиките, в които всеки генериран цикъл с дължина четири или повече формира минимален разделителен подграф (след премахването му, графиката се разделя на два или повече несвързани компонента и никое подмножество от цикъла няма същите свойства) са точно кликови суми на клики и максимални равнинни графи, отново без премахване на ръбове [6] . Johnson и McKee [7] използваха суми на кликваниятахордови графи и паралелно-последователни графи за описание на частично дефинирани [8] матрици с положително определено разширение.
Възможно е да се получи декомпозиция на сумата от клики за всяко семейство графи, затворено при малка операция - графите във всяко второстепенно затворено семейство могат да бъдат формирани от суми от клики на графи, които са "почти вложени" върху повърхности от краен род, което означава, че влагането е разрешено, за да се избегнат малък бройпокриви(върхове, които могат да бъдат свързани с произволен брой други върхове) ифуния(тесни графики с ширина на пътя, които заместват лицата при лежане на повърхността) [9] . Тези описания са били използвани като важен инструмент при конструирането на алгоритми за приближение и времеви субекспоненциални точни алгоритми за NP-пълни оптимизационни проблеми на второстепенни затворени семейства от графики [10] [11] [12] .
Теорията на сумите върху кликите може да се обобщи от графики до матроиди. Теоремата за разлагане на Seymour описва регулярните матроиди [en] (матроиди, представляващи напълно унимодуларни матрици) като 3-сума на графични матроиди (матроиди, представляващи обхващащи дървета), кографични матроиди и някои 10-елементни матроиди [13] .