Question

Раскраска вершин графа назвается правильной, если любые две вершины, соединённые ребром, покрашены в разные цвета. Хроматическое число графа — это наименьшее количество цветов, нужное для правильной раскраски. Хроматическое число графа G
обозначается через χ(G)
.

Answer 1

Ответ:

$\chi()G)=2;$. есть две правильные раскраски.

Пошаговое объяснение:

Хроматическое число  $\chi(G)$  куба  $G$ равно 2. В самом деле, 1 оно очевидно не может быть равно, поэтому достаточно предъявить правильную раскраску двумя цветами. Введем систему координат, в которой координаты вершин куба являются нулями и единицами: (0,0,0); (0,0,1); (0,1,0); (0,1,1)); (1,0,0); (1,0,1); (1,1,0); (1,1,1). Заметим, что две вершины являются соседними тогда и только тогда, когда их координаты отличаются только в одном месте - ведь переход к соседней вершине означает сдвиг по какому-то ребру, а каждое ребро параллельно одной из осей координат. Пусть для определенности. мы используем цвета белый (Б) и черный (Ч). Закрасим вершину (0,0,0), скажем, цветом Б, тогда вершины (0,0,1), (0,1,0) и (1,0,0) нужно закрасить другим цветом, а поскольку мы хотим использовать только два цвета, то они будут Ч. С ними соседствуют (кроме уже закрашенной вершины (0,0,0) ) вершины (0 ,1,1), (1,0,1) и (1,1,0) - они не являются соседями друг для друга, поэтому мы можем их закрасить цветом Б (и другой возможности нет). Остается их общий сосед (1,1,1) - его закрашиваем цветом Ч. Итак,  $\chi(G)=2.$ Одновременно мы видим,  что существуют две правильные раскраски - закрасив вершину (0,0,0) одним из двух цветов, остальные вершины можно раскрашивать после этого единственным способом.