![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Отметим простые связи, существующие между матро-идными разложениями графов и раскрасками. Напомним, что матроидным разложением графа G называется представление его в виде объединения
G = G1 U G2 U... U Gμ
М-графов, т. е. графов, все связные компоненты которых суть полные графы; минимальное число μкомпонент в матроидных разложениях графа G — матроидное число μ (G).
![]() |
Очевидно, что граф Gi для которого VGi = VG, EGi = Ei, является M -графом, и
G = G1 U G2 U... U Gk (2)
— матроидное разложение. Итак, разбиение на цветные классы (1) определяет матроидное разложение (2) графа G. Тем самым доказано
Утверждение 57.1. Для любого графа G верно неравенство
μ(G)<χ’(G)
Учитывая это неравенство и теорему 56.3, получаем
Утверждение 57.2. Если граф G не содержит треугольников, то
μ(G)<χ’(G)
Для любого двудольного графа G верно равенство
μ(G) = Δ(G).
Если граф G не содержит треугольников, то его реберный граф L(G) и граф клик Q(G) могут различаться только изолированными вершинами. Следовательно, если χ q(G) —хроматическое число графа Q(G), то χ q(G) = χ’ (G), так что для графа G без треугольников μ(G)= χ q(G) = χ’ (G). Применяя теорему 56.3, получим второе равенство.
Для матроидного числа произвольного графа хроматическое число его графа клик является верхней границей. А именно, верно
![]() |
Подграф, порожденный в G объединением клик, входящих в один цветной класс при правильной вершинной раскраске графа клик Q(G), является M -графом, поскольку все его связные компоненты — полные графы. Следовательно, если
V1U V2 U...U Vk = VQ(G)
— разбиение на цветные классы множества вершин графа клик, a Gi получается из порожденного подграфа G(Vi) в результате присоединения всех вершин из VG\ Vi как изолированных, то G = G1 U G2 U... U Gk — матроидное разложение. Тем самым неравенство (3) доказано.
В качестве иллюстрации рассмотрим граф G, изображенный на рис. 57.1; для него Q(G) = K4, χ q(G) = χ’ (G)= 4, μ(G) =3.
Утверждение 57.4. Для произвольного графа G равенства μ(G) = 2 и χ q(G) = 2 равносильны.
Если χ q(G) = 2, то μ(G) ≤ 2. Но при μ(G) =1 никакие две максимальные клики графа G не пересекаются, и потому Q(G) —пустой граф, χ q(G) =1. Итак, при χ (G) = 2и μ(G) = 2.
![]() |
Доказательство основано на следующей очевидной комбинаторной лемме.
Лемма 57.5. Пусть S — конечное множество, каждому из элементов которого приписан один из двух фиксированных цветов или оба эти цвета. Если для любой пары элементов множества S существует общий приписанный им цвет, то тогда и все элементы множества имеют общий приписанный им цвет.
Пусть теперь
G = G1 U G2 (5)
— матроидное разложение графа G. Достаточно доказать, что любой полный подграф графа G целиком содержится в каком-либо из Gi; если это так, то разложение (5) определяет правильную 2-раскраску графа клик и истинность импликации (4) доказана.
Каждому из ребер графа G следующим образом припишем один из цветов {1, 2} или оба эти цвета. Именно, всем ребрам графа Gi (i = l, 2) приписывается цвет i. Пусть теперь Q — клика графа G, eue2 € EG(Q).
Если ребра е1 и е2 смежны, то в порожденном подграфе G(Q) существует третье ребро е, смежное с ними обоими. Какие-то два из этой тройки ребер имеют общий цвет, поскольку цветов только два. Но концы этих трех ребер вместе входят в одну из связных компонент графа Gi, являющихся полными графами, следовательно, а третье ребро имеет тот же цвет. Итак, для любой пары смежных ребер графа G(Q) существует общий приписанный им цвет.
Если же ребра е1 = u1v1 и е2 = u2v2 не смежны, то в графе G(Q) есть еще четыре ребра е3 = u1u2, е4 = v1v2, е5 = u1v2, е6= v1u2. Для каждой пары смежных из этих ребер существует общий цвет, откуда очевидно вытекает, что существует цвет, общий для ребер е1 и е2.
Доказано, что любые два ребра графа G(Q) имеют общий цвет. В силу леммы 57.5 существует общий цвет, например 1, приписанный всем ребрам графа G(Q). Последнее означает, что G(Q) содержится в одной из компонент графа G1.
Из утверждения 57.4 вытекает
Следствие 57.6. Если χ(G) = 3, то и μ(G) = 3.
§ 58. Раскраска планарных графов
Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов. Возникшая в середине прошлого века, она до сих пор привлекает внимание специалистов и любителей.
Первоначально вопрос формулировался в следующем виде: достаточно ли четырех красок для такой раскраски произвольной географической карты, при которой любые две соседние страны окрашены в различные цвета? При этом рассматриваются лишь те карты, в которых граница любой страны состоит из одной замкнутой линии, а соседними считаются страны, имеющие общую границу ненулевой длины.
Позднее понятия карты и ее раскраски были формализованы следующим образом. Связный плоский мульти-граф без мостов называется картой. Грани карты, имеющие общее ребро, называются смежными. Функция ƒ, ставящая в соответствие каждой грани Г карты натуральное число ƒ(Г) € { 1, 2,..., k) — цвет грани Г— называется k-раскраской, если цвета смежных граней различны. Карта называется k-раскрашиваемой, если для нее существует k-раскраска.
В 1879 году британский математик А. Кэли опубликовал в первом томе Трудов Лондонского географического общества статью, посвященную проблеме раскраски карт, в которой сформулировал гипотезу четырех красок (сама задача была известна и ранее).
Гипотеза четырех красок: всякая карта 4-раскрашиваема.
Часто пользуются другой формулировкой гипотезы четырех красок: всякий планарный граф 4-раскрашиваем.
Поскольку планарный граф по определению изоморфен некоторому плоскому, то эквивалентность этих двух формулировок гипотезы четырех красок вытекает из следующей теоремы.
Теорема 58.1. Карта G является k-раскрашиваемой тогда и только тогда, когда геометрически двойственный граф G* вершинно k-раскрашиваем.
Поскольку граф G плоский и не имеет мостов, то двойственный граф G* — плоский граф (без петель), пусть задана некоторая правильная k -раскраска карты G. Построим k -раскраску графа G*, приписав каждой его вершине цвет той грани, в которой находится эта вершина. Так как вершины графа G* смежны тогда и только тогда, когда смежны содержащие их грани, то полученная раскраска оказывается правильной.
Аналогичным образом можно перейти от правильной ракраски графа G* к правильной раскраске карты G.
Заметим, что существуют плоские графы, которые зльзя раскрасить правильно менее чем четырьмя цветами. Таков, например, граф К4.
Первоначально гипотеза четырех красок не показалась слишком сложной и появилось несколько ее «доказательств», в которых позднее были обнаружены пробелы.
В дальнейшем эту проблему, сбивающую с толку простотой формулировки, пытались решить многие известные математики. Большой интерес к теории графов, возникший в связи с гипотезой четырех красок, способствовал открытию многих важных результатов, поскольку они казались полезными для решения проблемы. До сих пор эта проблема остается мощным стимулом исследования различных свойств графов.
Сначала рассмотрим раскраски планарных графов двумя и тремя цветами.
Согласно теореме Кёнига χ (G) = 2 для непустого графа G тогда и только тогда, когда он не содержит циклов нечетной длины, откуда несложно получить следующее утверждение.
Утверждение 58.2. Плоский двусвязный граф является бихроматическим тогда и только тогда, когда граница каждой его грани содержит четное число ребер.
Достаточно доказать, что плоский двусвязный граф, граница каждой грани которого состоит из четного числа ребер, является двудольным. Рассмотрим произвольный простой цикл С такого графа. Этот цикл делит плоскость на две части — внутреннюю (по отношению к циклу) и внешнюю. Считаем, что сам цикл принадлежит каждой из частей.
Пусть внутренняя часть плоскости содержит грани Г1,Г2,..., Гk с числом ребер в их границах l1, l2,..., lk соответственно. Так как любое из чисел li четное, то их сумма также четная. Но каждое ребро, не принадлежащее циклу С, входит в эту сумму дважды, откуда следует, что длина цикла С четная. Из теоремы 9.1 следует, что рассматриваемый граф является двудольным.
Аналогичное утверждение верно и для односвязных графов, только в этой ситуации каждый мост, входящий в границу грани, учитывается дважды.
Утверждение 58.3. Карта G является 2-раскрашиваемой тогда и только тогда, когда граф G эйлеров.
Учитывая теорему 58.1, нужно лишь доказать, что геометрически двойственный граф G* является двудольным тогда и лишь тогда, когда граф G эйлеров. Последнее оставлено читателю.
Теорема 58.4 (М. Крол, 1973 г.). Плоский граф 3-раскрашиваем тогда и только тогда, когда он является подграфом плоской триангуляции с четными степенями вершин.
Необходимость. Будем считать, что порядок рассматриваемого графа более трех (для К3 утверждение тривиально). Пусть вершины плоского графа G правильно раскрашены тремя цветами 1, 2, 3. Рассмотрим произвольную отличную от треугольника грань Г этого графа. Возможны следующие случаи.
1) Границей грани Г является цикл четной длины, вершины которого окрашены в два цвета, например, 1 и 2. Тогда поместим внутри Г вершину w, соединив ее ребрами с каждой из вершин этого цикла, и окрасим эту вершину в третий цвет 3 (рис. 58.1, а).
2) Границей грани Г является 4-цикл C = (v1, v2 , v3 , v4 , v1), вершины которого окрашены в три цвета, например, v1 — в цвет 1, v2 — в 2, v3 — в 3, v4 — в 2. В этом
случае поместим внутри грани Г цепь L = (v1 , w1,w2, v3), связывающую несмежные вершины цикла С, имеющие различные цвета. Соединим w1 и w2 с вершинами этого
цикла, окрашенными в один цвет. Для получения правильной раскраски остается каждой из вершин w1 и w2 приписать цвет 1 или 3, однозначно определенный (см.рис. 58.1, б).
![]() |
Рис. 58.1
Будут треугольники и 4 -циклы (рис. 58.1, в). С последними поступим так же, как в предыдущих случаях.
Проделав описанные построения для выбранной грани Г, отличной от треугольника, получим новый правильно 3 -раскрашенный граф, в котором Г уже разбита на треугольники. Выполнив эти операции для всех таких граней, придем к правильно 3 -раскрашенной плоской триангуляции, подграфом которой и будет исходный граф. Покажем, что степени всех вершин этой триангуляции четны. Пусть v — произвольная вершина, имеющая, для определенности, цвет 1. Поскольку G ≠ K3, то вершины; смежные с v, образуют цикл. Так как для их раскраски достаточно двух цветов 2 и 3, то этот цикл имеет четную длину и, следовательно, степень вершины v четная.
Достаточность. Пусть граф G является подграфом плоской триангуляции Т с четными степенями вершин. Покажем, что он 3-раскрашиваем.
Поскольку Т — эйлеров граф, то согласно утверждению 58.3 его грани можно раскрасить двумя цветами, например, красным и синим. Ориентируем ребра, ограничивающие каждую красную грань, так, чтобы при; движении по ориентированному ребру грань оставалась справа. Произвольную вершину v графа Т окрасим в цвет 1 и для каждой вершины w рассмотрим любую простую (v, w)-цепь Р. Пусть α(Р) и β(Р) — числа ребер этой цепи, ориентация которых совпадает и, соответственно, не совпадает с направлением цепи от v к w. Припишем вершине w цвет c(w)= 1 + α(Р)— β(Р) (mod3).
Покажем, чтовыполненная таким образом раскраска окажется правильной. Сперва докажем, что окраска любой вершины w не зависит от выбора цепи Р. Рассмотрим произвольный простой цикл С в графе Т, ограничивающий некоторую область F. Если при движении по ориентированному ребру, принадлежащему С, от его начала к концу область находится справа от ребра, то назовем это ребро a-ребром, в противном случае — b-ребром. Пусть α и β — числа а -ребер и, соответственно, b -ребер в С, а k и s — числа красных и синих внутренних граней в области F. Каждое а -ребро принадлежит красной внутренней грани, а b -ребро — синей внутренней грани.
Вычислим число р ребер, находящихся внутри цикла. С одной стороны, они принадлежат красным граням, поэтому р = 3 k — α. С другой стороны, эти ребра принадлежат синим граням, так что р = 3s — β. Отсюда Зk — α = = 3s-β, или α-β = 3k-3s = 0 (mod3).
![]() |
Вначале рассмотрим случай, когда цепи Р1 и Р2 не имеют общих вершин, отличных от v и w (см. рис. 58.2, на котором красные грани обозначены буквой К, а синие — С).
![]() |
Если цепи Р1 и Р2 имеют общие вершины, отличные от v и w, то объединение этих цепей разбиваем на простые циклы и цепи, а далее проводим доказательство так, как для случая одного цикла.
![]() |
(знак последнего слагаемого зависит от ориентации ребра wu). В случае, когда v = w, последнее соотношение принимает вид с(и)= 1 ± 1.
Отсюда следует, что c(w)≠ с(и), и раскраска графа Т является правильной.
Поскольку G — подграф 3-раскрашиваемого графа Г, то он также 3-раскрашиваем.
Утверждение 58.2 и теорема 58.4 дают необходимые и достаточные условия существования правильной раскраски вершин плоского графа двумя и тремя цветами. Однако между этими утверждениями есть принципиальная разница: условие утверждения 58.2 легко проверяемо, но не известно эффективных способов проверки условий теоремы 58.4. Приведем без доказательства одно легко проверяемое достаточное условие 3-раскрашиваемости плоского графа.
Теорема 58.5. Любой плоский граф, содержащий менее четырех 3-циклов, 3-раскрашиваем.
Дата публикования: 2015-01-23; Прочитано: 352 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!