Сумма клик
-
Определение суммы по кликам
- Сумма по кликам объединяет два графа путем склеивания их клик.
- Операция аналогична суммированию по связям в топологии.
- Сумма k-клик имеет ровно k вершин в каждой клике.
-
Контексты и вариации
- В некоторых контекстах ребра не удаляются.
- В других контекстах удаляются все ребра.
- В некоторых случаях можно указывать удаленные ребра.
-
Связь с шириной дерева
- Сумма k-клик имеет ширину дерева не более k.
- Каждое дерево является суммой его ребер в 1 клик.
- Каждый граф с шириной дерева не более k может быть суммой клик с не более чем k + 1 вершинами.
-
Связь со связностью графа
- Граф, не связанный вершинами (k + 1), может быть представлен как сумма k клик меньшего размера.
- SPQR-дерево двусвязного графа является суммой двух кликов его трехсвязных компонентов.
-
Применение в теории структур графов
- Суммы кликов используются для характеристики семейств графов.
- Теорема Вагнера доказывает, что графы без полного графа с пятью вершинами являются 3-кликовыми суммами плоских графов.
- Хордовые графы и ущемленные графы могут быть сформированы без удаления ребер.
- Джонсон и Макки используют суммы клик для характеристики частных матриц.
-
Обобщения и записи
- Теория клик-сумм может быть обобщена на матроиды.
- Теорема Сеймура характеризует регулярные матроиды как 3-суммы графических матроидов.