Автор Тема: Найти хроматическое число и минимальное раскрашивание графа  (Прочитано 316 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Ivan

  • Пользователь
  • Сообщений: 2
    • Просмотр профиля
Найти хроматическое число и минимальное раскрашивание графа
Задание Б
 

Оффлайн Admin

  • Администратор
  • Сообщений: 4966
  • Поблагодарили: 1575 раз(а)
    • Просмотр профиля
Я, например, очень плохо разбираюсь в теории графов. Поэтому предлагаю начать с определений. Что такое хроматическое число графа? Что называется минимальным раскрашиванием графа?
 
Сказали спасибо: Байт

Оффлайн Байт

  • Пользователь
  • Сообщений: 928
  • Поблагодарили: 674 раз(а)
    • Просмотр профиля
ХЧ(а) = ХЧ(б) = 3
Меньше нельзя, потому что оба графа содержат подграф К3
А в 3 краски раскрашивается. легко. Могу показать, если ты обозначишь вершины.
Но сначала ответь на вопрос в посте 2
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin