Материал из Викиконспекты
|
|
| (не показано 8 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | == Введение ==
| |
| | | | |
| − |
| |
| − | == Раскраска в 6 цветов ==
| |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
| |
| − | |proof=
| |
| − | Докажем по индукции.
| |
| − | * База
| |
| − | Если граф содержит не более 6 вершин, то утверждение очевидно.
| |
| − | * Переход
| |
| − | Предположим, что для планарного графа с <tex>N</tex> вершинами существует раскраска в 6 цветов. Докажем то же для графа с <tex> N+1 </tex> вершиной.
| |
| − |
| |
| − | Для начала покажем что найдётся вершина, степень которой не больше 5.
| |
| − |
| |
| − | Предположим это не так. Для любой вершины <tex> u_i </tex> верно <tex> deg </tex> <tex> u_i \ge 6 </tex>. Если выписать это неравенство для всех <tex> i </tex> и сложить, получим <tex> 2E \ge 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \le 3V-6 </tex>. Пришли к противоречию.
| |
| − | Теперь, удалим из графа вершину со степенью не превышающей 5. По предположению индукции получившийся граф можно раскрасить в 6 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан
| |
| − | }}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Раскраска в 5 цветов ==
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Раскраска в 4 цвета ==
| |
Текущая версия на 19:39, 4 сентября 2022
