![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Поскольку задачу правильной раскраски точно решить трудно, то актуальны оценки хроматического числа, выражаемые в терминах более или менее просто вычислимых параметров графа. Рассмотрим несколько оценок громатического числа, связанных со степенями вершин графа.
Обозначим через F множество всех порожденных подграфов графа G, а через δ(G), как обычно,—минимальную из степеней вершин графа G.
![]() |
Е> Утверждение теоремы очевидно для пустых графов, [усть G — произвольный χ –хроматический граф χ ≥ 2, а H — его минимальный порожденный подграф, удовлетворяющий условию χ (Н) = χ. В этом случае χ (H — v) ≤ χ -1. Для любой вершины v графа Н.
![]() |
Как и ранее, через Δ(G) обозначим наибольшую из степеней вершин графа G.
![]() |
Некоторое улучшение последней оценки дает следующая
Теорема Брукса (1941 г.). Если G — связный граф не являющийся полным, и Δ (G)≥3, то χ (G) ≤ Δ (G).
Пусть Δ (G) — m>3. Очевидно, что максимальная степень вершин каждого блока графа G не превосходит m. Поэтому, с учетом теоремы 53.2, достаточно, не теряя общности, провести доказательство для двусвязных графов.
Пусть G — двусвязный граф. Сначала покажем существование в графе G таких вершин и и v, что расстояние d(u, v) равно 2 и граф G — u — v связен. Это очевидно, если χ (G) ≥ 3.
Допустим, что χ (G)=2. Пусть D — множество всех доминирующих вершин графа G. Поскольку G не является полным графом, то I VG\D\ ≥ 2. Если D ≠ 0, то в качестве вершин и и v можнр взять любые две несмежные вершины из VG\D.
Пусть D≠ 0. Выберем в графе G вершину z степени не менее трех. Если граф G — z 2-связный, то в качестве вершины и возьмем z, а в качестве v — любую вершину, находящуюся от z на расстоянии 2.
Пусть χ(G — z) = 1, А и В — два концевых блока графа G — z. Существуют две вершины и € А и v € B, не являющиеся точками сочленения графа G — z смежные с вершиной z, иначе оказалось бы, что χ (G)=l.
Легко видеть, что граф G — u — v связен. Действительно, удаление вершин и и v не нарушает связности блоч в A и B, поэтому граф G — u — v — z связен. Из того, deg z ≥ 3, следует теперь связность графа G — u — v. Итак, показано существование нужных вершин и и смежных с некоторой вершиной z'. Поскольку граф G — u — v связен, то его вершины можно так занумеровать числами 1, 2,..., п — 2, что каждая вершина, кроме =z' ', будет смежна по крайней мере с одной вершиной, имеющей меньший номер.
Теперь окрасим несмежные вершины и и v в цвет 1. Затем будем последовательно приписывать вершинам 2, zn-3,..., z1 один из цветов 1, 2,..., т по следующему правилу. Пусть к > 1 и вершины и, v, zn-2, zn-3 ,..., z1 уже окрашены. Так как zk смежна хотя бы с одной из вершин с меньшим номером, то степень вершины zk в порожденном подграфе G(u, v, zn-2,..., zn+1,zk) меньше т. Вершине zh присвоим любой цвет, не использованный при раскраске смежных с ней вершин. Так же поступим и с вершиной z1. Так как deg z1 ≤ m и хотя бы две вершины из окружения верны z1 (и и v) окрашены в один цвет, то в множестве цветов (1, 2,..., т)существует цвет, не использованный в раскраске вершин из этого окружения. Этот цвет и припишем вершине z1. Очевидно, что получена правильная m-раскраска графа G.
Оценка, устанавливаемая теоремой Брукса, достижима. Так, для кубического графа G, изображенного на 54.1, существует правильная 3-раскраска, а правильная 2-раскраска невозможна, ибо это не двудольный граф. Следовательно, χ(G)=3=Δ(G). Однако теорема может дать и завышенную оценку матического числа. Например, из этой теоремы следует, что χ (K1,n)≤n, в то время как χ(K1,n )=2. Две вершины графа называются соцветными относительно некоторой правильной раскраски, если при этой краске они имеют один цвет.
Следствие 54.3. При любой минимальной раскраске связного неполного графа существуют две соцветные относительно этой раскраски вершины, расстояние между орыми равно 2.
Пусть G — связный неполный граф. При χ = χ(G) =2 утверждение тривиально, так как в этом случае G является связным двудольным графом, имеющим не менее трех вершин.
Если χ ≥ 3, то из предыдущей теоремы следует, что граф содержит хотя бы одну вершину v, для которой deg v ≥ χ Поэтому среди смежных с v вершин найдутся по крайней мере две вершины, имеющие один цвет.
Следующая теорема связывает хроматическое число графа с числами его вершин и ребер.
![]() |
(Напомним, что пара [ ] квадратных скобок означает целую часть числа, а пара { } фигурных скобок —дробную часть.);
Докажем только правое неравенство (доказательство левого громоздко).
Если G — полный граф, то неравенство проверяется непосредственно.
Пусть граф G не является полным и χ(G) = χ. Согласно следствию 54.3 при любой минимальной раскраске граф имеет пару соцветных вершин v1 и v2, для которых d(v1, v2) = 2. Построим граф G1, слив v1 и v2 в вершину v. Граф G1 имеет на одну вершину и по крайней мере на одно ребро меньше, чем граф G. Очевидно, что χ (G1)= χ В противном случае, правильно раскрасив χ1 цветами (χ1 < χ) Граф G1, можно было бы построить и χ 1-раскраску графа G. Для этого нужно было бы окрасить вершины v1 и v2 в цвет вершины v, а для остальных вершин сохранить их цвета в графе G1.
Операции слияния соцветных вершин будем производить до тех пор, пока не получим полный граф K1 Пусть таких слияний потребуется s. Так как по-прежнему χ(К1) = χ, то l = χ = n-s.
![]() |
![]() |
![]() |
Существуют графы, для которых оценки, установленные предыдущей теоремой, достигаются. Таковы, напримep, полные графы.
Ниже рассматриваются оценки хроматического числа, имеющие скорее теоретический интерес, поскольку параметры графа, с которыми они связаны, вычисляются столь же сложно, как и само хроматическое число.
Тривиальной нижней границей для хроматического числа является плотность. Очевидно, что χ(G) ≥φ (G) для любого графа G. На первый взгляд может показаться, что плотность графа тесно связана с его хроматическим числом, и если плотность φ (G) невелика, то невелико и χ(G). Однако на самом деле разность χ (G) — φ (G) может быть сколь угодно большим числом. А именно, верна следующая
Теорема 54.5 (А. А. Зыков, 1949 г.). Существуют графы без треугольников с произвольно большим хроматическим числом.
Для доказательства индуктивно построим последовательность S = (G2, G3 ,..., Gi,...) графов Gi без треугольников, таких, что χ (Gi) = i. Положим G2 = K2. Если граф Gi уже построен, i≥2 и VGi = {v1, v2,..., vn }, то граф Gi+1 определим по следующему правилу: VGi+1 = VGi U V' U v1, V'={v'1,v'2,...,vn}, VGi (\ Vf = ¢ v € VGi U V; каждую вершину vj соединим ребрами с теми вершинами из VGt, с которыми смежна vi, в графе Gt; вершину v соединим ребрами с каждой вершиной из V’ (см. рис. 54.2 и 54.3, где изображены графы G3 и G4). Полученный таким образом граф имеет 2n + 1 вершин.
Покажем, что Gi+1 — искомый граф. Так как вершина v не смежна ни с одной вершиной из множества VG{, а вершины из V’ попарпо не смежны, то никакой треугольник в Gi+1 не может содержать вершину v. По той же причине треугольник не может содержать более одной вершины из V’. Если же треугольник образовывали бы вершины v j, vk, vi то в графе Gi, вершины vj, vk, vi также составляли бы треугольник. Поскольку в графе Gi треугольники отсутствуют, отсюда следует, что в графе Gi+1 их также нет.
![]() |
раскраску вершин из V’ понадобилось бы не более i — 1 цветов (отличных от цвета вершины v). Изменив окраску вершин графа Gt так, чтобы каждая вершина vj получила тот же цвет, что и vj’, можно было бы построить правильную (i—1)-раскраску графа Gi+1 в то время как χ(Gi) = i
Таким образом, доказано, что граф Gi+1 не содержит треугольников и χ (Gi+1) = i + 1.
Заметим, что графы, существование которых гарантируется предыдущей теоремой, являются экзотическими, поскольку для почти каждого графа G верно следующее утверждение: если φ(G) ≤ k, то и χ (G) ≤:k (Ф.Колайтис, X.Прёмель, В.Ротшильд, 1987 г.).
Как показывает теорема 54.5, графы с плотностью, равной 2, могут иметь сколь угодно большое хроматическое число. Следующая теорема, приводимая здесь без доказательства, свидетельствует об отсутствии связей между хроматическим числом и обхватом графа.
Теорема 54.6 (П. Эрдёш, 1961 г.). Для любых натуральных чисел l и χ существует χ -хроматический граф, обхват которого превосходит l.
Оценим хроматическое число в терминах числа независимости.
![]() |
![]() |
откуда следует левое из неравенств (1).
Перейдем к доказательству правого неравенства. В графе G есть независимое множество вершин S, содержащее ровно ао элементов. Так как \G — S\=n — ао, то, (G — S) < п — ао и, следовательно, χ < n — ао + 1.
![]() |
![]() |
Первое из неравенств вытекает из предыдущей теоремы, а второе — из теоремы Брукса.
Дополнением теоремы 54.7 является
Теорема 54.9. Для любых натуральных чисел n, ао и χ, удовлетворяющих неравенствам (1), существует граф порядка п с числом вершинной независимости ао и хроматическим числом χ.
Рассмотрим отдельно три случая:
1) ао = 1; 2) ао>1 и n = aol, где l — целое число;3) п не кратно ао.
1) Из (1) следует, что χ = п, и Кп — нужный граф, так как ао(Кп)= 1 =а0, χ (Kn) = n = χ.
2) Пусть G — полный l- дольный граф, в каждой доле которого ровно ао вершин. Тогда i(G) = l = n/ao. Фиксируем некоторую долю U и каждую из не входящих в эту долю вершин будем последовательно превращать в доминирующую, добавляя недостающие ребра. На каждом таком шаге хроматическое число возрастает на 1. В результате придем к полному (п — ао+ 1) -дольному графу F, все доли которого, кроме доли U, одновершинные. Очевидно, что χ (F)= n — ao+i.
3) Если п не кратно ао, то в качестве исходного графа берется n-вершинный полный ([п/ао] + 1) –дольный граф, [п/ао] долей которого содержат по ао вершин. Выбрав в качестве U одну из таких долей, дальнейшие рассуждения проведем так же, как в случае 2. Естественный интерес вызывает стремление уточнить оценку хроматического числа, устанавливаемую теоремой Брукса. О. В. Бородин и А. В. Косточка в 1977 году выдвинули следующую гипотезу, пока не доказанную и не опровергнутую:
Гипотеза. Если Δ (G) ≥ 9 и φ(G) ≤ Δ (G), то χ (G) ≤ Δ (G)-1.
Приведем без доказательства теорему, дающую асимптотику хроматического числа.
![]() |
. § 55. Хроматический полином
Поскольку t-раскраской графа G является произвольное отображение вида VG->{1, 2,..., n}, то число попарно различных t-раскрасок этого графа равно числу всех таких отображений, т. е. tn, где n=\VG\. Но если ограничиться только правильными раскрасками, то вопрос о числе различных среди них становится сложным. Количество попарно различных правильных t-раскрасок графа G называется хроматической функцией графа G и обозначается через f(G, t).
Очевидно, что наименьшее из чисел t, для которых f(G, t)≠0, есть χ (G).
Для некоторых графов хроматическая функция определяется совсем легко. Например, f (О„, t) = tn, так как цвета всех вершин пустого графа можно выбирать независимо друг от друга. При правильной раскраске полного графа Кп первая вершина может иметь любой из t заданных цветов, а для окраски каждой из последующих вершин разрешается использовать
![]() |
В общем случае, как отмечалось выше, вычисление хроматической функции сопряжено с большими трудностями. Приведем несколько утверждений, позволяющих упрощать ее вычисление.
![]() |
Это утверждение вытекает из того, что раскраска каждой из компонент Gt может выбираться независимо.
![]() |
Фиксируем какую-либо правильную раскраску ƒ1 графа G1. Для продолжения ее до правильной раскраски графа G нужно взять такую правильную раскраску f2 графа G2, при которой цвет f1(v) вершины v, общей для графов G1 и G2, равен цвету f2(v). Поскольку число правильных t -раскрасок графа G2, при которых цвет вершины v фиксирован, не зависит от этого цвета, то для выбора раскраски f2 имеется f(G2, t)/t возможностей, откуда и следует равенство (1).
Утверждение 55.3. Пусть и и v — две несмежные вершины графа G. Если G1 = G + uv, a G2 получается из графа G в результате слияния вершин и и v, то f(G,t) = f(G1 t) + f(G2,t).
Число правильных t-раскрасок графа G, при которых цвета вершин и и v различны, не изменится, если к G присоединить ребро uv. Следовательно, это число равно f(G1, t). Аналогично, число правильных f-раскрасок графа G, при которых цвета вершин и и v совпадают, равно f{G2, t). Складывая эти два числа, получим число всех правильных f-раскрасок графа G, т. е. f(Gj).
Предыдущее утверждение позволяет свести вычисление функции f (G, t) произвольного графа G к вычислению хроматических функций графов с большим числом ребер или с меньшим числом вершин, и следовательно, в конце концов,— хроматических функций полных графов. К сожалению, число этих графов может оказаться катастрофически большим.
Очевидно
Следствие 55.4. Хроматическая функция любого графа G равна симме хроматических функций некоторого числа полных графов, порядки которых не больше, чем \G\.
Поскольку f(Kn, t) — полином от t, то верно
Следствие 55.5. Хроматическая функция f(G, t) любого графа является полиномом от t.
Поэтому хроматическую функцию f(G, t) обычно называют хроматическим полиномом графа G.
![]() |
![]() |
![]() |
Рис. 55.3
![]() |
где а{ —целые неотрицательные числа.
Несомненный интерес представляет следующий вопрос, ответ па который пока не получен: каким условиям должен удовлетворять полином, чтобы он был хроматическим полиномом некоторого графа? Любопытно было бы найти условия, при которых хроматические полиномы графов совпадают. Примерами таких графов являются деревья, которые можно определить в терминах хроматических полиномов.
![]() |
![]() |
![]() |
Дата публикования: 2015-01-23; Прочитано: 1130 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!