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