В неориентированном графе 27 вершин, а его хроматическое число равно 3. Сколько ребер может быть в таком графе? Дайте точную верхнюю и нижнюю оценки. задан 30 Май '15 12:01 svain |
Граф, насколько я понимаю, считается простым. Для того, чтобы хроматическое число было больше двух, то есть граф не оказался двудольным, необходимо наличие цикла нечётной длины. При этом трёх рёбер достаточно -- это минимальное число. Если потребовать дополнительно, чтобы граф был связным, то ответом будет 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 falcao Спасибо огромное!
(30 Май '15 12:19)
svain
|