Cтраница 2
Тогда, если каждый из двух остаточных графов Н и К бонда В допускает реберную раскраску, то и граф О допускает реберную раскраску. [16]
Удаляем это ребро, строим таблицу паросочетательных разрезов для нового графа, находим покрытия, состоящие из непересекающихся паросочетательных разрезов, и проверяем их на соответствие кубируемой реберной раскраске. Поскольку покрытию 1, 4, 12, 18, 2, 8, 17, ( 3, 7, 13, 5, 10, 15, 19, 6, 9, 14, 16 соответствует кубируемая реберная раскраска, полученный граф вложим в гиперкуб. [17]
Реберная раскраска называется правильной, если любые два смежных ребра имеют разные цвета. Реберная раскраска с минимальным числом цветов называется минимальной. [18]
Этот бесхитростно звучащий результат может нас сразу ввести в область реберных раскрасок - еще одну область многообразных и важных исследований в теории графов. Допустимой реберной раскраской произвольного графа G ( двудольного или нет) называют присваивание ( приписывание, назначение) целых чисел ( цветов, красок) ребрам графа G таким образом, чтобы никакие два смежных ребра не были одинакового цвета. [19]
Мы рассмотрим сейчас некоторый подход к задаче нахождения хроматического индекса, опирающийся на линейное программирование, а также взаимосвязь этой задачи с задачами о паросочетаниях. Очевидно, что реберную раскраску графа можно определить как некоторое разбиение множества его ребер на паросочетания. [20]
Далее, если этот индекс равен г, то в каждой оптимальной реберной раскраске каждый цвет соответствует совершенному па-росочетанию. Значит, такая реберная раскраска возможна только тогда, когда число вершин в графе четное. [21]
Показать, что С имеет ровно три гамильтоновых цикла и все его реберные раскраски определяются лишь этими тремя циклами. [22]
Реберной раскраской ( или раскраской по Тейту) графа О назовем отображение множества Е ( 0) в Т, при котором ребра, инцидентные одной и той же вершине, отображаются в три различных цвета. Из определения следует, что граф, содержащий петлю, не допускает реберной раскраски. [23]
Оказывается, гипотеза четырех красок для планарных графов эквивалентна некоторой гипотезе, касающейся реберной раскраски кубически карт. [24]
Значит, каждый подграф G - состоит из непересекающихся ребер и изолированных вершин. Xe ( G) - Д и мы вновь получаем теорему Кенига о реберной раскраске. В этом и состоит свойство самоулучшения, о котором говорилось выше. [25]
Напомним, что реберная раскраска графа G - это такая раскраска его ребер, при которой любые два смежных ребра имеют разные цвета. Хроматическим индексом Xe ( G) графа G называется наименьшее число красок в его реберных раскрасках. [26]
В случае 5 3 переставим ( если необходимо) цвета раскраски таким образом, чтобы каждое ребро бонда В имело в раскраске / такой же цвет, как и в раскраске &. Приписывая всем ребрам графа О те цвета, которые они имеют в раскрасках 5 и I, получаем реберную раскраску графа О. [27]
Пусть некоторый граф является частичным подграфом гиперкуба. Тогда, сопоставив каждому разряду гиперкуба краску и окрасив каждое ребро графа краской, соответствующей разряду, в котором отличаются двоичные векторы, приписанные вершинам, коинцидент-ным данному ребру, получим кубируемую реберную раскраску графа. Действительно, для каждого цикла С графа функция Ф ( С) 0, поскольку каждой вершине гиперкуба приписан только один двоичный вектор. [28]
Если построенная таблица Т не содержит ни одного покрытия, которому соответствовала бы кубируемая реберная окраска, исходный граф невложим в гиперкуб. Для приведения графа к кубируемому виду может быть использована итерационная процедура, осуществляющая на каждом шаге итерации построения таблицы паросочетательных разрезов для частичных графов исходного графа, поиск и проверку покрытий на соответствие их кубируемой реберной раскраске. При получении кубируемой раскраски частичного графа ребра, дополняющие его до исходного графа, либо заменяются цепями длины два или три, либо устраняются в зависимости от предметной интерпретации задачи. [29]
Удаляем это ребро, строим таблицу паросочетательных разрезов для нового графа, находим покрытия, состоящие из непересекающихся паросочетательных разрезов, и проверяем их на соответствие кубируемой реберной раскраске. Поскольку покрытию 1, 4, 12, 18, 2, 8, 17, ( 3, 7, 13, 5, 10, 15, 19, 6, 9, 14, 16 соответствует кубируемая реберная раскраска, полученный граф вложим в гиперкуб. [30]