В неориентированном графе 27 вершин, а его хроматическое число равно 3. Сколько ребер может быть в таком графе? Дайте точную верхнюю и нижнюю оценки.

задан 30 Май '15 12:01

изменен 30 Май '15 12:01

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

Граф, насколько я понимаю, считается простым.

Для того, чтобы хроматическое число было больше двух, то есть граф не оказался двудольным, необходимо наличие цикла нечётной длины. При этом трёх рёбер достаточно -- это минимальное число. Если потребовать дополнительно, чтобы граф был связным, то ответом будет 27.

Далее рассмотрим такой пример: разобьём все вершины на 3 подмножества из 9 вершин, и соединим рёбрами вершины из разных подмножеств. Рёбер станет $%3\cdot9^2=243$%. Покажем, что это количество максимально. Пусть имеется $%k_i$% вершин $%i$%-го цвета, где $%k_1+k_2+k_3=27$%. Вершины одного цвета не соединены, и рёбер имеется не более $%k_1k_2+k_1k_3+k_2k_3$%.

Складывая почленно три неравенства $%(x-y)^2\ge0$%, $%(x-z)^2\ge0$% и $%(y-z)^2\ge0$% и сокращая на 2, получаем $%x^2+y^2+z^2\ge xy+xz+yz$%. Прибавляя $%2(xy+xz+yz)$% к обеим частям, имеем $%(x+y+z)^2\ge3(xy+xz+yz)$%. Таким образом, $%k_1k_2+k_1k_3+k_2k_3\le\frac13(k_1+k_2+k_3)^2=\frac{27^2}3=3^5=243$%.

ссылка

отвечен 30 Май '15 12:17

Спасибо огромное!

(30 Май '15 12:19) svain
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×396

задан
30 Май '15 12:01

показан
372 раза

обновлен
30 Май '15 16:48

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

по почте:

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

по RSS:

Ответы

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

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