Теорема Грэма – Поллака. - Graham–Pollak theorem

Разбиение ребер полного графа ${ displaystyle K_ {6}}$ на пять полных двудольных подграфов: ${ displaystyle K_ {2,2}}$ (светло-красный), ${ displaystyle K_ {2,3}}$ (светло-синий), ${ displaystyle K_ {1,3}}$ (желтый) и две копии ${ displaystyle K_ {1,1}}$ (темно-красный и темно-синий). Согласно теореме Грэма – Поллака, разбиение менее чем на пять полных двудольных подграфов невозможно.

В теория графов, то Теорема Грэма – Поллака. утверждает, что края ${ displaystyle n}$-вертекс полный график не может быть разделено на менее чем ${ displaystyle n-1}$ полные двудольные графы.^[1] Впервые он был опубликован Рональд Грэм и Генри О. Поллак в двух статьях в 1971 и 1972 годах в связи с приложением к схемам телефонной коммутации.^[2][3]

С тех пор теорема стала хорошо известной и неоднократно изучалась и обобщалась в теории графов, отчасти из-за ее элегантного доказательства с использованием техники из алгебраическая теория графов.^{[4][5][6][7][8]} Сильнее, Айгнер и Циглер (2018) напишите, что все доказательства так или иначе основаны на линейная алгебра: "комбинаторное доказательство этого результата неизвестно".^[1]

Построение оптимальной перегородки

Разделение ровно на ${ displaystyle n-1}$ полные двудольные графы легко получить: просто упорядочите вершины и для каждой вершины, кроме последней, сформируйте звезда соединяя его со всеми последующими вершинами в порядке.^[1] Возможны и другие перегородки.

Доказательство оптимальности

Доказательство теоремы Грэма – Поллака, описанное Айгнер и Циглер (2018) (следующий Тверберг 1982 ) определяет реальная переменная ${ displaystyle x_ {i}}$ для каждой вершины ${ displaystyle v_ {i} in V}$, где ${ displaystyle V}$ обозначает множество всех вершин в графе. Пусть левая и правая стороны ${ displaystyle k}$-й двудольный граф обозначим ${ displaystyle L_ {k}}$ и ${ displaystyle R_ {k}}$соответственно и для любого набора ${ displaystyle S}$ вершин определяют ${ Displaystyle X (S)}$ быть суммой переменных для вершин в ${ displaystyle S}$:

${ Displaystyle X (S) = sum _ {v_ {i} in S} x_ {i}.}$

Тогда, используя эти обозначения, тот факт, что двудольные графы разбивают ребра полного графа, можно выразить уравнением

${ displaystyle sum _ {i$

Теперь рассмотрим система линейных уравнений это устанавливает ${ Displaystyle X (V) = 0}$ и ${ displaystyle X (L_ {k}) = 0}$ для каждого ${ displaystyle k}$. Любое решение этой системы уравнений также подчиняется нелинейным уравнениям

${ displaystyle { begin {align} 0 & = X (V) ^ {2} = { Bigl (} sum _ {i} x_ {i} { Bigr)} ^ {2} & = { Bigl (} sum _ {i} x_ {i} ^ {2} { Bigr)} + ​​{ Bigr (} 2 sum _ {i$

Но сумма квадратов действительных переменных может быть равна нулю только в том случае, если все отдельные переменные равны нулю, что является тривиальным решением системы линейных уравнений. ${ displaystyle n-1}$ полных двудольных графов, система уравнений имела бы меньше чем ${ displaystyle n}$ уравнения в ${ displaystyle n}$ неизвестных и будет иметь нетривиальное решение; противоречие. Таким образом, количество полных двудольных графов должно быть не менее ${ displaystyle n-1}$.^[1][4]

Связанные проблемы

Маркировка расстояний

Грэм и Поллак изучают более общий маркировка графиков задача, в которой вершины графа должны быть помечены строками одинаковой длины из символов «0», «1» и «✶» таким образом, чтобы расстояние между любыми двумя вершинами равнялось количеству позиций строки где одна вершина помечена 0, а другая - 1. Такая маркировка без символов "✶" дала бы изометрическое вложение в гиперкуб, то, что возможно только для графов, частичные кубики, а в одной из своих статей Грэм и Поллак называют маркировку, которая позволяет символам «✶» встраивать в «сжатый куб».^[3]

Для каждой позиции строк меток можно определить полный двудольный граф, в котором одна сторона двудольного графа состоит из вершин с меткой 0 в этой позиции, а другая сторона состоит из вершин с меткой 1, исключая вершины с меткой «». ". Для полного графа каждые две вершины находятся на расстоянии друг от друга, поэтому каждое ребро должно принадлежать ровно одному из этих полных графов. Таким образом, разметка этого типа для полного графа соответствует разбиению его ребер на полные двудольные графы, причем длины меток соответствуют количеству графов в разбиении.^[3]

Гипотеза Алона – Сакса – Сеймура.

Нога Алон, Майкл Сакс, и Пол Сеймур сформулировали в начале 1990-х годов гипотезу, которая, если она верна, значительно обобщит теорему Грэма – Поллака: они предположили, что всякий раз, когда граф хроматическое число ${ displaystyle k + 1}$ ребра разбиты на полные двудольные подграфы, по крайней мере, ${ displaystyle k}$ подграфы нужны. Эквивалентно, их гипотеза утверждает, что непересекающиеся по ребрам объединения ${ displaystyle k}$ полные двудольные графы всегда можно раскрасить не более чем ${ displaystyle k + 1}$ цвета. Гипотеза была опровергнута Хуангом и Судаковым в 2012 году, которые построили семейства графов, образованные как реберно-непересекающиеся объединения ${ displaystyle k}$ полные двудольные графы, требующие ${ Displaystyle Omega (к ^ {6/5})}$ цвета.^[9]

Бикликовая перегородка

Задача бикликового разбиения принимает на вход произвольный неориентированный граф и требует разбиения его ребер на минимальное количество полных двудольных графов. это NP-жесткий, но управляемый с фиксированными параметрами. Лучшее алгоритм аппроксимации известная проблема имеет коэффициент аппроксимации из ${ Displaystyle О (п / журнал п)}$.^[10][11]

использованная литература