2
1

Какое наибольшее число рёбер может быть у 10-вершинного графа, если хроматическое число этого графа равно 4?

Хроматическое число графа - это наименьшее число вершин в которое можно покрасить вершины графа так, чтобы концы любого ребра имели разные цвета.

задан 15 Июн '19 18:07

10|600 символов нужно символов осталось
1

Разобьём 10 вершин на 4 группы численностью 3+3+2+2. Раскрасим вершины каждой группы в один из 4 цветов. Рёбрами соединим каждую пару вершин из разных групп. Дополнение графа будет иметь 3+3+1+1=8 рёбер, а у нас останется 10*9/2-8=37. Хроматическое число равно 4, так как в 3 цвета граф не раскрасить: у нас имеется подграф K4.

Найденное число максимально, так как если рёбер >=38, то количество рёбер строго больше величины n^2(1-1/r)/2 при n=10, r=4. Тогда по теореме Турана, в графе будет иметься подграф K_{r+1}=K5, но его вершины нельзя правильно раскрасить в 4 цвета.

ссылка

отвечен 15 Июн '19 20:03

@falcao, спасибо! Но только как вы догадались разбить именно на группы 3+3+2+2 ?

(15 Июн '19 21:25) worker

@falcao, если обозначить через кi - число вершин в i-й группе. То сумма ребер равна: к1(к2+к3+к4)+к2(к3+к4)+к3к4 при ограничении к1+к2+к3+к4=10. Решение задачи в такой формулировке можно найти?

(15 Июн '19 21:33) worker

@worker: при доказательстве теоремы Турана выясняется, среди прочего, строение "экстремальных" подграфов без K_{r+1}. Для этого надо разбить число вершин, равное n, на r примерно равных по численности групп. Это делается однозначно при условии, что численности отличаются не более чем на 1. Если где-то отличие в 2 и более, то легко проверяется, что такой пример не экстремальный: передача вершины из большой группы в малую число рёбер увеличивает. По сути дела, из этого вытекает одно из доказательств теоремы (коих довольно много). Я здесь ничего не подбирал, так как всё это известно.

(15 Июн '19 21:40) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×631

задан
15 Июн '19 18:07

показан
456 раз

обновлен
15 Июн '19 21:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru