WikiDer > Гипотеза диница

В комбинаторика, то Теорема Диница (ранее известный как Гипотеза диница) - это утверждение о расширении массивов до частичных Латинские квадраты, предложенный в 1979 г. Джефф Диниц,^[1] и доказано в 1994 г. Фред Гэлвин.^[2][3]

Теорема Диница состоит в том, что с учетом п × п квадратный массив, набор м символы с м ≥ п, а для каждой ячейки массива п- набор элементов из пула м символов, можно выбрать способ пометить каждую ячейку одним из этих элементов таким образом, чтобы ни одна строка или столбец не повторяли символ. Это также может быть сформулировано в результате теория графов, что список хроматического индекса из полный двудольный граф ${ displaystyle K_ {n, n}}$ равно ${ displaystyle n}$. То есть, если каждому ребру полного двудольного графа назначен набор ${ displaystyle n}$ цветов, можно выбрать один из назначенных цветов для каждого ребра, так что никакие два ребра, инцидентные одной и той же вершине, не имеют одинакового цвета.

Доказательство Галвина обобщает утверждение, что для любой двудольной мультиграф, хроматический индекс списка равен его хроматический индекс. Более общий Гипотеза о раскраске списка ребер утверждает, что то же самое верно не только для двудольных графов, но и для любого мультиграфа без петель. Еще более общая гипотеза утверждает, что список хроматических чисел из графы без когтей всегда равняется их хроматическое число.^[4] Теорема Диница также связана с Базисная гипотеза Роты.^[5]

Рекомендации

внешняя ссылка

• Вайсштейн, Эрик В. «Проблема Диница». MathWorld.

Этот комбинаторика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е