Cтраница 3
Далее, если этот индекс равен г, то в каждой оптимальной реберной раскраске каждый цвет соответствует совершенному па-росочетанию. Значит, такая реберная раскраска возможна только тогда, когда число вершин в графе четное. [31]
Снарком будем называть связный кубический граф, который не имеет реберной раскраски и бонда, содержащего меньше четырех ребер. Простейшим примером снарка является граф Петерсена. Если граф не допускает реберной раскраски, но имеет бонд В из двух или трех ребер, то этот граф легко редуцируется к меньшему, являющемуся остаточным графом бонда В. Указанный случай очень прост и мы его детально не рассматриваем. [32]
В данной главе мы сначала обсудим возможность получения решения задачи построения двудольного паросочетания как следствия теоремы двойственности. Пользуясь тем, что эта теорема может быть истолкована как некая характеризация так называемого дробного хроматического индекса, мы предпримем краткое посещение области реберных раскрасок и докажем известную теорему Визинга. Описания политопа паросочетаний и политопа дробных паросочетаний имеют много других тонких приложений; некоторые из них мы рассмотрим. [33]
Сформулированные теоремы представляют собой конструктивный критерий распознавания условий кубируемости графа. Для вложения произвольного графа в гиперкуб строится двоичная матрица паросочетательных разрезов Т, каждой строке которой взаимно однозначно соответствует паросо-четательный разрез, столбцу - ребро графа, и элемент таблицы T ( i, j) равен 1, если у - е ребро входит в z - й паросочетательный разрез, и равен 0 в противном случае. Ейлделяются те покрытия столбцов строками таблицы, которым соответствуют непересекающиеся паросочетательные разрезы. Каждое такое покрытие определяет реберную раскраску исходного графа. Если при этом хотя бы одному покрытию соответствует кубируемая реберная раскраска, то граф вложим в гиперкуб. [34]
Сформулированные теоремы представляют собой конструктивный критерий распознавания условий кубируемости графа. Для вложения произвольного графа в гиперкуб строится двоичная матрица паросочетательных разрезов Т, каждой строке которой взаимно однозначно соответствует паросо-четательный разрез, столбцу - ребро графа, и элемент таблицы T ( i, j) равен 1, если у - е ребро входит в z - й паросочетательный разрез, и равен 0 в противном случае. Ейлделяются те покрытия столбцов строками таблицы, которым соответствуют непересекающиеся паросочетательные разрезы. Каждое такое покрытие определяет реберную раскраску исходного графа. Если при этом хотя бы одному покрытию соответствует кубируемая реберная раскраска, то граф вложим в гиперкуб. [35]