Я решал этот вопрос, связанный с раскраской вершин. В части решения вопроса говорится, что:
"Раскраска оптимальна, поскольку граф содержит полный граф (клику) K4."
Также в другом вопросе то же самое объяснение:
"Раскраска оптимальна, поскольку вершины с 1 по 5 образуют полный подграф K5."
Почему раскраска вершин (или ребер тоже? ) должна быть оптимальной, если она содержит полный граф? Я просмотрела все конспекты лекций и слайды, но такой информации нет.
Заранее спасибо за помощь!
Эти рассуждения работают в совершенно конкретном случае. Они показывают, что первый граф не может иметь раскраску менее чем в 4 цвета, а второй граф не может иметь раскраску менее чем в 5 цветов. Таким образом, оптимальна любая 4-раскраска первого графа и оптимальна любая 5-раскраска второго графа.
Граф, содержащий K4, никогда не может быть раскрашен менее чем в 4 цвета, потому что этот подграф запрещает это. K4 имеет четыре узла, все они связаны друг с другом, поэтому каждый из них должен иметь свой цвет, поэтому вам нужно 4 цвета только для этого подграфа. Если этому подграфу уже нужно 4 цвета, то и всему графу определенно нужно — хотя, возможно, ему нужно больше (в этом случае вам понадобится другое доказательство оптимальности).
Другой способ взглянуть на ограничения раскраски графа, возможно, полезный в данном случае, — интерпретировать каждую клику как все разные ограничения.
