Сильное произведение графиков

Граф короля , сильное произведение двух графов путей.

В теории графов сильное произведение — это способ объединения двух графов в один больший граф. Две вершины являются смежными в сильном произведении, если они происходят из пар вершин фактор-графов, которые либо смежны, либо идентичны. Сильное произведение — это одна из нескольких различных операций произведения графа , которые изучались в теории графов. Сильное произведение любых двух графов можно построить как объединение двух других произведений тех же двух графов: декартова произведения графов и тензорного произведения графов .

Примером сильного произведения является граф короля , граф ходов шахматного короля на шахматной доске, который можно построить как сильное произведение графов путей. Разложение плоских графов и связанных с ними классов графов в сильные произведения использовалось в качестве основного инструмента для доказательства многих других результатов об этих графах.

Следует проявлять осторожность при встрече с термином «сильное произведение» в литературе, поскольку он также используется для обозначения тензорного произведения графов.

Определение и пример

Сильное произведение G ⊠ H графов что G и H — это граф такой, множество вершин G ⊠ H является декартовым произведением V ( G ) × V ( H ) ; иразличные вершины ( u , u' ) и ( v , v' ) смежны в G ⊠ H тогда и только тогда, когда :

u = v и u' смежно с v' , или

u' = v' и u смежно с v , или

u соседствует с v , а u' соседствует с v' .

Это объединение декартова произведения и тензорного произведения .

Например, граф короля , граф, вершины которого являются квадратами шахматной доски , а ребра представляют возможные ходы шахматного короля, является сильным произведением двух графов путей . Его горизонтальные ребра происходят из декартова произведения, а диагональные ребра — из тензорного произведения тех же двух путей. Вместе эти два вида кромок составляют весь прочный продукт.

Свойства и применение

Каждый планарный граф является подграфом сильного произведения пути и графа с древовидной шириной не более шести. Этот результат был использован для доказательства того, что плоские графы имеют ограниченное число очередей . небольшие универсальные графы и краткие схемы разметки смежности , и ограниченное неповторяющееся хроматическое число и центрированное хроматическое число. Эту структуру продукта можно найти в линейном времени . Помимо плоских графов, расширение этих результатов было доказано для графов рода ограниченного графы с запрещенным минором , являющимся вершинным графом , графы ограниченной степени с любым запрещенным минором, и k-планарные графы .

Кликовое число сильного произведения любых двух графов равно произведению кликовых чисел двух графов. Если оба графа имеют ограниченную ширину близнеца и, кроме того, один из них имеет ограниченную степень, то их сильное произведение также имеет ограниченную ширину близнеца.

Мощность листьев — это граф, сформированный из листьев дерева путем объединения двух листьев, когда их расстояние в дереве ниже некоторого порога. $k$. Если $G$ это $k$- сила листьев дерева $T$, затем $T$ можно найти как подграф сильного произведения $G$ с $k$-вершинный цикл. Это встраивание использовалось в алгоритмах распознавания степеней листьев.

Сильное произведение графа циклов с 4 вершинами с 7 вершинами и полного графа , $C_{7}\boxtimes K_{4}$был предложен как возможность создания 10-хроматического бипланарного графа , который улучшил бы известные границы проблемы Земля-Луна ; другой предлагаемый пример — граф, полученный удалением любой вершины из $C_{5}\boxtimes K_{4}$. В обоих случаях количество вершин в этих графах более чем в 9 раз превышает размер их наибольшего независимого множества , а это означает, что их хроматическое число не менее 10. Однако неизвестно, являются ли эти графы бипланарными.