Изменения

== Вспомогательная Лемма лемма ==

|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный [[Отношение связности, компоненты связности|связный ]] неориентированный граф и <tex>\Delta(G)</tex> {{- --}} максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>w</tex> степени <tex> \deg\ w < \Delta(G)</tex>, то <tex>\chi(G) \le leqslant \Delta(G)</tex>.

[[Файл:Brooks_1.png‎|400px|thumb|Алгоритм расскраски раскраски на 5ом пятом шаге]]Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_n,</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. На <tex> i</tex>-ом шаге покраски, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей (т.к <tex> \deg(v_{n - i+1}) \le leqslant \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \le leqslant \Delta(G)</tex>.

|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, тогда <tex>\chi(G) \le leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{- --}} максимальная степень вершин <tex>G</tex>

Для доказательства теоремы рассмотрим несколько случаев:#<tex>\Delta(G) \leqslant 2</tex>, тогда:#*Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>#*Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>#*Если <tex> \Delta = 2</tex>, то:#*# <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>#*#<tex> G</tex> нечетный циклПоэтому мы будем считать до конца доказательства, что #<tex> \Delta(G) \ge geqslant 3</tex>., тогда:##Если в <tex>G</tex> существует вершина не является вершинно двусвязным графом, тогда в графе <tex>vG</tex> степени <tex> deg\ v < \Delta(G)exists</tex>, то по выше доказанной лемме <tex> v \chi(G) \le \Delta(G)</tex>. То есть осталось рассмотреть случай, когда <tex>G</in V</tex> {{---}} регулярный граф степени [[Отношение связности, компоненты связности|точка сочленения]]. Пусть <tex>\DeltaG_1,G_2</tex>. #Если {{---}} две компоненты связности, полученные при удалении вершины <tex>Gv</tex> не является вершинно двусвязным графом. Тогда, тогда в графе по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем <tex> G\Delta</tex> цветов. Поскольку количество соседей вершины <tex> \existsv </tex> в каждой из компонент не более <tex> v \in VDelta - 1</tex>, где v {{---}} точка сочленения. Пусть то <tex>G_1,G_2G</tex> две компоненты связности полученный при удалении вершины можно правильно раскрасить в не более чем <tex>v\Delta</tex>цветов.Тогда, по выше доказанной лемме <##Если <tex>G_1,G_2G</tex> можно правильно раскрасить в не более чем является вершинно двусвязным графом. Тогда, <tex>\Deltaexists</tex> цветов.Поскольку количество соседей вершины <<tex> v ,u \in V :(u,v) \notin E</tex> в каждой из компонент не более и при удалении вершин <tex> \Delta - 1v,u</tex>, то граф теряет связность. Пусть <tex>GG_1,G_2</tex> можно правильно раскрасить в не более чем {{---}} два подграфа <tex>G:(G_1 \Delta</cap G_2 = \{v,u\}) \land (G_1 \cup G_2 = G)</tex> цветов. Рассмотрим два случая.###Если в графе сумма степеней вершин <tex> Gu,v</tex> в каждом из подграфов <tex> \existsG_1,G_2</tex> меньше <tex> v,u 2(\in V :(u,vDelta-1) \notin E</tex> и при удалении вершин . Тогда, в одном из данных подграфах <tex>v,\deg u\leqslant \Delta - 2 </tex> граф теряет связность .Пусть <tex>G_1,G_2</tex> два подграфа или <tex> G:G_1 \cap G_2 = deg v \leqslant \{v,u\} \land G_1 \cup G_2 = GDelta - 2 </tex>. Рассмотрим два случая:## Если То есть, эти подграфы можно правильно раскрасить в одном из подграфов не более чем <tex> G_1,G_2\Delta</tex> цветов так, чтобы вершины <tex> deg\ u < \Delta - 2 ,v </tex> или были бы разных цветов. А из этого следует, что граф <tex> deg\ v < \Delta - 2 </tex> то, подграфы <tex>G_1,G_2G</tex> тоже можно правильно раскрасить в не более чем <tex>\Delta</tex> цветов так, чтобы вершины .### Если сумма степеней вершин <tex> u,v </tex> были бы разных цветов.А в одном из этого следует что, граф подграфов <tex>GG_1,G_2</tex> тоже можно правильно раскрасить в не более чем <равна <tex>2(\Delta-1)</tex> цветов.## Если Тогда, степени обоих обеих вершин в одном из подграфов равны <tex> \Delta - 1</tex> , рассмотрим например , что в подграфе <tex>G_1</tex>:###* Если вершины <tex> G_1u,G_2 v</tex> можно правильно раскрасить в не более чем смежны с вершиной <tex>p \Deltain G_2</tex> цветов так, чтобы вершины тогда мы можем правильно раскрасить <tex> u,v G_2</tex> были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена. ##* где степени вершин <tex>\exists p \in G_2: pu \in E \land pv \in E u,v</tex>, тогда мы можем правильно раскрасить равны <tex>G_2</tex>, где <tex>deg\ u = deg\ v = 11</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были одного цвета.Следовательно,можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.###*<tex>\exists u_1[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай,v_1 \in G_2: uu_1 \in E \land vv_1 \in E \land u_1 \neq v_1 пятый шаг]]Если вершины </tex>, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v_1v\}</tex>.Заметимрассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом,то есть для этой сумма степеней новой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин в каждой из компонент, полученных после их удаления, меньше <tex> v,u2(\Delta-1)</tex>.Из чегоПоэтому, прямым образом вытекает, что если для этой пары вершин провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в не более чем не более чем <<tex>\Delta </tex> цветов.#[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм расскраски для 3ого случая на 5ом шаге]]#Если вышеописанные случаи не подходят, тогда рассмотрим <<tex>w \in V : deg\ w = \DeltaG</tex>. У вершины является <tex>wk</tex> должны существовать две соседние вершины -связным графом, где <tex>u,v : uv \notin E k > 2</tex>. Тогда, в противном случаи рассмотрим <tex>G = K_nw \in V : \deg w = \Delta</tex>.Пусть У вершины <tex>G_- = G - u - v w</tex>. Заметим, что должны существовать две соседние вершины <tex>G_-u,v : uv \notin E </tex> связный граф, запустим для в противном случае <tex>G_-G = K_n</tex> алгоритм обхода в ширину из вершины . Пусть <tex>wG_- = G - u - v </tex>. Пронумеруем вершины Заметим, что <tex>v_1,...,v_{n-2},<G_-</tex> где связный граф, запустим для <tex>v_iG_-</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs.Теперь пусть алгоритм обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Теперь пусть <tex> v_{n-1} = v</tex>, и <tex>v_n = u</tex>. Покрасим <tex> v_n,v_{n-1} = v</tex>в один цвет,и <tex>v_n = uдалее начнем красить вершины в обратном порядке, начиная с </tex>. Покрасим <tex>v_n,v_{n-12}</tex> в один цвет, далее начнем красить вершины в обратном порядке начиная с <tex>v_{n-2}</tex> в обратном порядке в один из <из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета.Заметим, что так всегда можно сделать, поскольку на <tex> i</tex>-ом шаге покраски,где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей<tex>\Delta(G) - 1</tex> уже покрашенных соседей. Следовательно, следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов.Вершину <tex>w</tex>,мы тоже сможем правильно раскрасить в не более чем один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в не более чем не более чем <tex>\Delta</tex> цветов.

== Источники См. также == * [http://myweb.facstaff.wwu.edu/sarkara/brooks.pdf Доказательство на английском[Раскраска графа]* [http://en.wikipedia.org/wiki/Brooks'_theorem Теорема Брукса на вики]