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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
Строка 3: Строка 3:
 
|statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориентированный граф и <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то <tex>\chi(G) \le \Delta(G)</tex>.
 
|statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориентированный граф и <tex>\Delta(G)</tex> - максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>v</tex> степени <tex> deg\ v < \Delta(G)</tex>, то <tex>\chi(G) \le \Delta(G)</tex>.
 
|proof=
 
|proof=
Запустим алгоритм [[Обхода в ширину| обхода в ширину]] из вершины v. Пронумеруем вершины <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> v_{n-i+1}</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> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов.
 
Таким образом граф можно покрасить в <tex> \Delta</tex> цветов, следовательно <tex> \chi(G) \le \Delta(G)</tex>.
 
Таким образом граф можно покрасить в <tex> \Delta</tex> цветов, следовательно <tex> \chi(G) \le \Delta(G)</tex>.
  
Строка 24: Строка 24:
 
#Если <tex>G</tex> не является двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex>, где v {{---}} точка сочленения. Пусть <tex>G_1,G_2</tex> две компоненты связности полученный при удалении вершины <tex>v</tex>.Тогда, по выше доказанной лемме <tex>G_1,G_2</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>, где v {{---}} точка сочленения. Пусть <tex>G_1,G_2</tex> две компоненты связности полученный при удалении вершины <tex>v</tex>.Тогда, по выше доказанной лемме <tex>G_1,G_2</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> G_1,G_2</tex>  <tex> deg\ u < \Delta - 2 </tex> или <tex> deg\ v < \Delta - 2 </tex> то, подграфы <tex>G_1,G_2</tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.А из этого следует что, граф <tex>G</tex> тоже можно правильно раскрасить в <\Delta> цветов.
+
## Если в одном из подграфов <tex> G_1,G_2</tex>  <tex> deg\ u < \Delta - 2 </tex> или <tex> deg\ v < \Delta - 2 </tex> то, подграфы <tex>G_1,G_2</tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.А из этого следует что, граф <tex>G</tex> тоже можно правильно раскрасить в <tex>\Delta</tex> цветов.
 
## Если степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex> например в подграфе <tex>G_1</tex>:
 
## Если степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex> например в подграфе <tex>G_1</tex>:
 
##* <tex> G_1,G_2 </tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.  
 
##* <tex> G_1,G_2 </tex> можно правильно раскрасить в <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.  
 
##* <tex>\exists p \in G_2: pu \in E \land pv \in E  </tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где <tex>deg\ u = deg\ v = 1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета.Следовательно,можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 
##* <tex>\exists p \in G_2: pu \in E \land pv \in E  </tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где <tex>deg\ u = deg\ v = 1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета.Следовательно,можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 
##*<tex>\exists u_1,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,v_1\}</tex>.Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин <tex> v,u</tex>, прямым образом вытекает, что граф <tex> G</tex> можно правильно покрасить в не более чем <tex>\Delta </tex> цветов.
 
##*<tex>\exists u_1,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,v_1\}</tex>.Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин <tex> v,u</tex>, прямым образом вытекает, что граф <tex> G</tex> можно правильно покрасить в не более чем <tex>\Delta </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>. Заметим, что H связный граф, запустим на нем алгоритм bfs  
+
#Если вышеописанные случаи не подходят, тогда рассмотрим <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> цветов.
 
}}
 
}}
  

Версия 18:31, 27 декабря 2012

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

Лемма:
Пусть [math]G(V,E)[/math] - произвольный связный неориентированный граф и [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math]. Если в таком графе существует вершина [math]v[/math] степени [math] deg\ v \lt \Delta(G)[/math], то [math]\chi(G) \le \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] v_{n-i+1}[/math] можно покрасить по крайней мере в один из свободных цветов.

Таким образом граф можно покрасить в [math] \Delta[/math] цветов, следовательно [math] \chi(G) \le \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) \le \Delta(G)[/math], где [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math]
Доказательство:
[math]\triangleright[/math]
  1. Если [math] \Delta = 0[/math], [math] G = K_1[/math]
  2. Если [math] \Delta = 1[/math], [math] G = K_2[/math]
  3. Если [math] \Delta = 2[/math], то:
    1. [math] G [/math]— либо дерево либо четный цикл и тогда [math] \chi(G) = 2[/math]
    2. [math] G[/math] нечетный цикл

Поэтому мы будем считать до конца доказательства, что [math] \Delta(G) \ge 3[/math]. Если в [math]G[/math] существует вершина [math]v[/math] степени [math] deg\ v \lt \Delta(G)[/math], то по выше доказанной лемме [math] \chi(G) \le \Delta(G)[/math]. То есть осталось рассмотреть случай, когда [math]G[/math] — планарный граф.

  1. Если [math]G[/math] не является двусвязным графом, тогда в графе [math] G[/math] [math] \exists[/math] [math] v \in V[/math], где v — точка сочленения. Пусть [math]G_1,G_2[/math] две компоненты связности полученный при удалении вершины [math]v[/math].Тогда, по выше доказанной лемме [math]G_1,G_2[/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] G_1,G_2[/math] [math] deg\ u \lt \Delta - 2 [/math] или [math] deg\ v \lt \Delta - 2 [/math] то, подграфы [math]G_1,G_2[/math] можно правильно раскрасить в [math]\Delta[/math] цветов так, чтобы вершины [math] u,v [/math] были бы разных цветов.А из этого следует что, граф [math]G[/math] тоже можно правильно раскрасить в [math]\Delta[/math] цветов.
    2. Если степени обоих вершин в одном из подграфов равны [math] \Delta - 1[/math] например в подграфе [math]G_1[/math]:
      • [math] G_1,G_2 [/math] можно правильно раскрасить в [math]\Delta[/math] цветов так, чтобы вершины [math] u,v [/math] были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.
      • [math]\exists p \in G_2: pu \in E \land pv \in E [/math], тогда мы можем правильно раскрасить [math]G_2[/math], где [math]deg\ u = deg\ v = 1[/math], в не более чем [math] \Delta [/math] цветов так, чтобы вершины [math]u,v[/math] были одного цвета.Следовательно,можно покрасить граф [math]G[/math] в не более чем [math]\Delta[/math] цветов.
      • [math]\exists u_1,v_1 \in G_2: uu_1 \in E \land vv_1 \in E \land u_1 \neq v_1 [/math], тогда вместо вершин [math]\{u,v\}[/math] рассмотрим вершины [math]\{u,v_1\}[/math].Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин [math] v,u[/math], прямым образом вытекает, что граф [math] G[/math] можно правильно покрасить в не более чем [math]\Delta [/math] цветов.
  3. Если вышеописанные случаи не подходят, тогда рассмотрим [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]

Источники