Теорема Брукса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (правки)
Строка 1: Строка 1:
 
== Вспомогательная лемма ==
 
== Вспомогательная лемма ==
 
{{Лемма  
 
{{Лемма  
|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 \Delta(G)</tex>.
+
|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) \leqslant \Delta(G)</tex>.
 
|proof=
 
|proof=
 
  [[Файл:Brooks_1.png‎|400px|thumb|Алгоритм раскраски на пятом шаге]]
 
  [[Файл:Brooks_1.png‎|400px|thumb|Алгоритм раскраски на пятом шаге]]
Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <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 \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \le \Delta(G)</tex>.
+
Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <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}) \leqslant \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \leqslant \Delta(G)</tex>.
  
 
}}
 
}}
Строка 11: Строка 11:
 
{{Теорема
 
{{Теорема
 
|about= Брукса
 
|about= Брукса
|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 \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>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) \leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>   
  
  
 
|proof=
 
|proof=
 
Для доказательства теоремы рассмотрим несколько случаев:
 
Для доказательства теоремы рассмотрим несколько случаев:
#<tex>\Delta(G) \le 2</tex>, тогда:
+
#<tex>\Delta(G) \leqslant 2</tex>, тогда:
 
#*Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>
 
#*Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>
 
#*Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>
 
#*Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>
 
#*Если <tex> \Delta = 2</tex>, то:
 
#*Если <tex> \Delta = 2</tex>, то:
#*# <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>
+
#*# <tex> G </tex> {{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>
 
#*#<tex> G</tex> нечетный цикл
 
#*#<tex> G</tex> нечетный цикл
#<tex>\Delta(G) \ge 3</tex>, тогда:
+
#<tex>\Delta(G) \geqslant 3</tex>, тогда:
 
##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex> {{---}} [[Отношение связности, компоненты связности|точка сочленения]]. Пусть <tex>G_1,G_2</tex> {{---}} две компоненты связности, полученные при удалении вершины <tex>v</tex>. Тогда, по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем  <tex>\Delta</tex> цветов. Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 
##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex> {{---}} [[Отношение связности, компоненты связности|точка сочленения]]. Пусть <tex>G_1,G_2</tex> {{---}} две компоненты связности, полученные при удалении вершины <tex>v</tex>. Тогда, по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем  <tex>\Delta</tex> цветов. Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 
##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность. Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
 
##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность. Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> deg\ u \le \Delta - 2 </tex> или <tex> deg\ v \le \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
+
### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> \deg u \leqslant \Delta - 2 </tex> или <tex> \deg v \leqslant \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 
### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
 
### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
 
###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 
###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 
###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.
 
###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.
##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <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}</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> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
+
##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : \deg w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <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}</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> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 
}}
 
}}
  
Строка 35: Строка 35:
 
*[[Раскраска графа]]
 
*[[Раскраска графа]]
  
== Источники ==
+
== Источники информации ==
 
*[http://myweb.facstaff.wwu.edu/sarkara/brooks.pdf Brooks’ Theorem]
 
*[http://myweb.facstaff.wwu.edu/sarkara/brooks.pdf Brooks’ Theorem]
 
*[http://en.wikipedia.org/wiki/Brooks'_theorem Wikipedia: Brooks' theorem]
 
*[http://en.wikipedia.org/wiki/Brooks'_theorem Wikipedia: Brooks' theorem]

Версия 09:02, 15 января 2016

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

Лемма:
Пусть [math]G(V,E)[/math] — произвольный связный неориентированный граф и [math]\Delta(G)[/math] — максимальная степень вершин [math]G[/math]. Если в таком графе существует вершина [math]w[/math] степени [math] \deg w \lt \Delta(G)[/math], то [math]\chi(G) \leqslant \Delta(G)[/math].
Доказательство:
[math]\triangleright[/math]
Алгоритм раскраски на пятом шаге
Запустим алгоритм обхода в ширину из вершины [math]w[/math]. Пронумеруем вершины [math]v_1,...,v_n,[/math] где [math]v_i[/math] вершина рассмотренная на [math]i[/math]-ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из [math]\Delta[/math] цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. На [math] i[/math]-ом шаге покраски, для вершины [math] v_{n - i+1}[/math] есть не более [math]\Delta(G) - 1[/math] уже покрашенных соседей (т.к [math] \deg(v_{n - i+1}) \leqslant \Delta(G)[/math] и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть [math]w[/math]), следовательно вершину [math] v_{n-i+1}[/math] можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем [math] \Delta[/math] цветов, то есть [math] \chi(G) \leqslant \Delta(G)[/math].
[math]\triangleleft[/math]

Теорема

Теорема (Брукса):
Пусть [math]G(V,E)[/math] — связный неориентированный граф и [math]G[/math] не является [math]K_m[/math] или [math]C_{2m+1}[/math], ни для кого [math] m[/math], тогда [math]\chi(G) \leqslant \Delta(G)[/math], где [math]\Delta(G)[/math] — максимальная степень вершин [math]G[/math]
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы рассмотрим несколько случаев:

  1. [math]\Delta(G) \leqslant 2[/math], тогда:
    • Если [math] \Delta = 0[/math], [math] G = K_1[/math]
    • Если [math] \Delta = 1[/math], [math] G = K_2[/math]
    • Если [math] \Delta = 2[/math], то:
      1. [math] G [/math] — либо дерево либо четный цикл и тогда [math] \chi(G) = 2[/math]
      2. [math] G[/math] нечетный цикл
  2. [math]\Delta(G) \geqslant 3[/math], тогда:
    1. Если [math]G[/math] не является вершинно двусвязным графом, тогда в графе [math] G[/math] [math] \exists[/math] [math] v \in V[/math]точка сочленения. Пусть [math]G_1,G_2[/math] — две компоненты связности, полученные при удалении вершины [math]v[/math]. Тогда, по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем [math]\Delta[/math] цветов. Поскольку количество соседей вершины [math] v [/math] в каждой из компонент не более [math] \Delta - 1[/math], то [math]G[/math] можно правильно раскрасить в не более чем [math]\Delta[/math] цветов.
    2. Если [math]G[/math] является вершинно двусвязным графом. Тогда, [math] \exists[/math] [math] v,u \in V :(u,v) \notin E[/math] и при удалении вершин [math]v,u[/math] граф теряет связность. Пусть [math]G_1,G_2[/math] — два подграфа [math] G:(G_1 \cap G_2 = \{v,u\}) \land (G_1 \cup G_2 = G)[/math]. Рассмотрим два случая.
      1. Если сумма степеней вершин [math]u,v[/math] в каждом из подграфов [math]G_1,G_2[/math] меньше [math]2(\Delta-1)[/math]. Тогда, в одном из данных подграфах [math] \deg u \leqslant \Delta - 2 [/math] или [math] \deg v \leqslant \Delta - 2 [/math]. То есть, эти подграфы можно правильно раскрасить в не более чем [math]\Delta[/math] цветов так, чтобы вершины [math] u,v [/math] были бы разных цветов. А из этого следует, что граф [math]G[/math] тоже можно правильно раскрасить в не более чем [math]\Delta[/math] цветов.
      2. Если сумма степеней вершин [math]u,v[/math] в одном из подграфов [math]G_1,G_2[/math] равна [math]2(\Delta-1)[/math]. Тогда, степени обоих вершин в одном из подграфов равны [math] \Delta - 1[/math], рассмотрим например, что в подграфе [math]G_1[/math]:
        • Если вершины [math]u,v[/math] смежны с вершиной [math]p \in G_2[/math], тогда мы можем правильно раскрасить [math]G_2[/math], где степени вершин [math]u,v[/math] равны [math]1[/math], в не более чем [math] \Delta [/math] цветов так, чтобы вершины [math]u,v[/math] были одного цвета. Следовательно, можно покрасить граф [math]G[/math] в не более чем [math]\Delta[/math] цветов.
        • Алгоритм раскраски. Третий случай, пятый шаг
          Если вершины [math]u,v[/math] смежны с вершинами [math]u_1,v_1 \in G_2[/math] соответственно, тогда вместо вершин [math]\{u,v\}[/math] рассмотрим вершины [math]\{u,v_1\}[/math]. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше [math]2(\Delta-1)[/math]. Поэтому, если для этой пары вершин провести рассуждения аналогичные тем, которые проводились для вершин [math] v,u[/math], получится, что граф [math] G[/math] можно правильно раскрасить в не более чем [math]\Delta [/math] цветов.
    3. Если [math]G[/math] является [math]k[/math]-связным графом, где [math]k \gt 2[/math]. Тогда, рассмотрим [math]w \in V : \deg w = \Delta[/math]. У вершины [math]w[/math] должны существовать две соседние вершины [math]u,v : uv \notin E [/math], в противном случае [math]G = K_n[/math]. Пусть [math]G_- = G - u - v [/math]. Заметим, что [math]G_-[/math] связный граф, запустим для [math]G_-[/math] алгоритм обхода в ширину из вершины [math]w[/math]. Пронумеруем вершины [math]v_1,...,v_{n-2}[/math], где [math]v_i[/math] вершина рассмотренная на [math]i[/math]-ом шаге алгоритма bfs. Теперь пусть [math] v_{n-1} = v[/math], и [math]v_n = u[/math]. Покрасим [math]v_n,v_{n-1}[/math] в один цвет, далее начнем красить вершины в обратном порядке, начиная с [math]v_{n-2}[/math] в один из [math]\Delta[/math] цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на [math]i[/math]-ом шаге покраски, где [math]i \neq n[/math], для вершины [math] v_{n - i+1}[/math] есть не более [math]\Delta(G) - 1[/math] уже покрашенных соседей. Следовательно, вершину [math] v_{n-i+1}[/math] можно покрасить по крайней мере в один из свободных цветов. Вершину [math]w[/math] мы тоже сможем правильно раскрасить в один из [math]\Delta[/math] цветов потому, что ее [math]\Delta[/math] соседей покрашено в не более чем [math]\Delta - 1[/math] цветов. Таким образом граф [math] G[/math] можно правильно раскрасить в не более чем [math]\Delta[/math] цветов.
[math]\triangleleft[/math]

См. также

Источники информации