Какое минимальное значение числа независимости может иметь двудольный граф на n вершинах?

Добрый день.

Возникли затруднения с, казалось бы, простым вопросом: какое минимальное значение числа независимости может иметь двудольный граф на n вершинах (при n >= 10)?
Я рассуждал так, что если у нас граф двудольный, то в худшем случае у нас оба подмножества вершин равны n/2, следовательно и минимальное значение числа независимости будет n/2. И картинка для моих рассуждений:
c1e8c7a05c354ac4b3bb465ab3e5e186.png
  • Вопрос задан
  • 301 просмотр
Решения вопроса 1
bobrovskyserg
@bobrovskyserg
А если n - нечетное?
:)
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы