Раскраска графа: 12 вершин
Алгебра, 9 класс · Головоломки: пути и графы
📚 Программа 9 класса · модуль «Практика: Головоломки: пути и графы» — тренажёр 3 из 3. За освоение тренажёра — +15 ★.
Правило и как решать
Минимальное число цветов может быть больше, чем кажется: четыре вершины, попарно соединённые рёбрами, требуют четырёх цветов. Раскрашивай по очереди и при тупике перекрашивай соседей.
Подсказка: Найди как можно больше попарно соединённых вершин.
Примеры с разбором
Пример 1
Ответ: один из вариантов: 1 — красный, 2 — синий, 3 — жёлтый, 4 — зелёный, 5 — зелёный, 6 — жёлтый, 7 — зелёный, 8 — красный, 9 — синий, 10 — синий, 11 — синий, 12 — красный
Решение: Начинай с вершины, из которой выходит больше всего рёбер, и крась соседей другими цветами. Если у двух соединённых вершин оказался одинаковый цвет, перекрась одну из них. Для некоторых графов меньше цветов не хватит: найди три вершины, соединённые друг с другом, — им нужны разные цвета.