Сумма по клике

Сумма по клике двух планарных графов и графа Вагнера. В результате получаем граф без K₅.

Сумма по клике — теоретико-графовая операция, обеспечивающая комбинацию двух графов путём склеивания их по клике, аналогично связной сумме в топологии. Если два графа ${\displaystyle G}$ и ${\displaystyle H}$ содержат клики одинакового размера, сумма по клике образуется из несвязанного объединения графов путём отождествления пар вершин из клик так, чтобы образовать одну клику, с последующим удалением некоторых рёбер[1]. Сумма по ${\displaystyle k}$-клике — это сумма по клике, содержащей не более ${\displaystyle k}$ вершин. Можно образовать сумму по кликам и сумму по ${\displaystyle k}$-кликам более чем двух графов путём повторения операции суммы.

Связанные концепции

Суммы по клике имеют тесную связь с древесной шириной — если два графа имеют древесную ширину, не превосходящую ${\displaystyle k}$, то у сумма по ${\displaystyle k}$-клике будет иметь то же свойство. Любое дерево является суммой по 1-кликам его рёбер. Любой параллельно-последовательный граф, или, обобщённо, любой граф с древесной шириной, не превосходящей двух, может быть построен как сумма по 2-кликам треугольников. Тот же результат обобщается для больших ${\displaystyle k}$ — любой граф с древесной шириной, не превосходящей ${\displaystyle k}$, может быть построен как сумма по кликам графов с максимум ${\displaystyle k+1}$ вершинами, и в этом случае используются суммы по ${\displaystyle k}$-кликам[2].

Существует также близкая связь между суммами по кликам и связностью графа — если граф не ${\displaystyle (k+1)}$-связан вершинно (так что существует множество из ${\displaystyle k}$ вершин, удаление которых приводит к потере связности), то граф можно представить в виде суммы по ${\displaystyle k}$-кликам более мелких графов. Например, SPQR-дерево двусвязного графа является представлением графа как суммы по 2-кликам его трёхсвязных компонент.

Приложение к структурной теории графов

Сжатый граф как сумма по кликам максимального планарного графа (жёлтый) и двух хордальных графов (красный и голубой)

Суммы по кликам важны в структурной теории графов, где они используются для описания некоторых семейств графов как графов, образованных суммой по кликам графов меньшего размера. Первым результатом такого типа[3] была теорема Вагнера[4], который доказал, что графы, не содержащие полных графов с пятью вершинами в качестве минора, являются суммой по 3-кликам планарных графов с графом Вагнера. С помощью этой структурной теоремы можно показать, что проблема четырёх красок эквивалентна случаю ${\displaystyle k=5}$ гипотезы Хадвигера. Хордальные графы — это в точности графы, которые можно образовать как суммы клик по кликам без удаления рёбер, а сжатые графы — это графы, которые можно образовать как суммы без удаления рёбер по кликам клик и максимальных планарных графов^[англ.][5]. Графы, в которых любой порождённый цикл длины четыре или больше образует минимальный разделяющий подграф (после его удаления граф распадается на две или более несвязные компоненты, и никакое подмножество цикла не имеет то же свойств), являются в точности суммами по кликам клик и максимальных планарных графов, снова без удаления рёбер[6]. Джонсон и Макки[7] использовали суммы по кликам хордальных графов и параллельно-последовательных графов для описания частично определённых[8] матриц, имеющих положительно определённое доопределение.

Можно получить разложение по суммам по кликам для любого семейства графов, замкнутого относительно операции минора — графы в любом минорно-замкнутом семействе могут быть образованы из сумм по кликам графов, которые «почти вложены» на поверхности конечного рода, что означает, что вложение разрешено во избежание небольшого числа крыш (вершин, которые можно соединить с произвольным число других вершин) и воронок (графы с узкой путевой шириной, заменяющие грани при вложении на поверхность)[9]. Эти описания использовались как важное средство при построении аппроксимационных алгоритмов и субэкспоненциальных по времени точных алгоритмов для NP-полных задач оптимизации на минорно-замкнутых семействах графов[10][11][12].

Обобщения

Теорию сумм по кликам можно обобщить от графов к матроидам. Теорема разложения Сеймура описывает регулярные матроиды^[англ.] (матроиды, представляющие вполне унимодулярные матрицы) как 3-суммы графических матроидов (матроиды, представляющие остовные деревья), кографические матроиды и некоторые 10-элементные матроиды[13].

Примечания

1. Здесь есть некоторая неопределённость. В книге Оксли Oxley, 1992 говорится, что должны быть удалены все рёбра клик. Д. Эпштейн (в пояснениях к английскому варианту статьи) утверждает, что в некоторых приложениях можно выбирать, какие рёбра удалять, а какие можно оставить, а в некоторых приложениях нельзя удалять вообще
2. Lovász, 2006.
3. Как указали Криж и Томас Kříž, Thomas, 1990, которые перечислили некоторые дополнительные описания семейств графов, опирающиеся на суммы по кликам.
4. Wagner, 1937.
5. Seymour, Weaver, 1984.
6. Diestel, 1987.
7. Johnson, McKee, 1996.
8. Частично определённая матрица — это матрица, не все клетки которой заполнены. Такие матрицы используются в теории экспертных оценок, в рекомендательных системах
9. Robertson, Seymour, 2003.
10. Demaine (1), 2004.
11. Demaine (2), 2005.
12. Demaine (3), 2005.
13. Seymour, 1980.

Литература

• Erik D. Demaine, Fedor V. Fomin, MohammedTaghi Hajiaghayi, Dimitrios Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs // Journal of the ACM. — 2005. — Т. 52, вып. 6. — С. 866—893. — doi:10.1145/1101821.1101823.
• Erik D. Demaine, MohammedTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors // Journal of Computing and Systems Sciences. — 2004. — Т. 69, вып. 2. — С. 166—195. — doi:10.1016/j.jcss.2003.12.001.
• Erik D. Demaine, Mohammed Taghi Hajiaghayi, Ken-ichi Kawarabayashi. Proc. 46th IEEE Symp. Foundations of Computer Science. — 2005. — С. 637—646. — doi:10.1109/SFCS.2005.14.
• A separation property of planar triangulations // Journal of Graph Theory. — 1987. — Т. 11, вып. 1. — С. 43—52. — doi:10.1002/jgt.3190110108.
• Igor Kříž, Robin Thomas. Clique-sums, tree-decompositions and compactness // Discrete Mathematics. — 1990. — Т. 81, вып. 2. — С. 177–185. — doi:10.1016/0012-365X(90)90150-G.
• Charles R. Johnson, Terry A. McKee. Structural conditions for cycle completable graphs // Discrete Mathematics. — 1996. — Т. 159, вып. 1–3. — С. 155–160. — doi:10.1016/0012-365X(95)00107-8.
• László Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вып. 1. — С. 75–86. — doi:10.1090/S0273-0979-05-01088-8.
• N. Robertson, P. D. Seymour. Graph minors XVI. Excluding a non-planar graph // Journal of Combinatorial Theory, Series B. — 2003. — Т. 89, вып. 1. — С. 43–76. — doi:10.1016/S0095-8956(03)00042-X.
• P. D. Seymour. Decomposition of regular matroids // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28, вып. 3. — С. 305–359. — doi:10.1016/0095-8956(80)90075-1.
• P. D. Seymour, R. W. Weaver. A generalization of chordal graphs // Journal of Graph Theory. — 1984. — Т. 8, вып. 2. — С. 241–251. — doi:10.1002/jgt.3190080206.
• Klaus Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114. — С. 570–590. — doi:10.1007/BF01594196.
• James G. Oxley. Matroid Theory. — New York, Tokyo: Oxford University Press, 1992. — С. 420. — ISBN 0-19-853563-5.