Ну давайте двинемся все-таки в сторону хроматического числа. С циклами мы немножко поработали. Понимаете, да ведь? Лекция-то какая. Ну давайте по обсуждаем хроматическое число. Скажем так. Исходя из лекции, вам могло показаться, что работать с хроматическими числами всегда сложно. И, в принципе, это правильно. Почти всегда сложно, но можно придумать какие-то естественные, в принципе, задачи, в которых все получается легко, но только надо сообразить. Вот давайте рассмотрим все ту же равномерную модель, но только с конкретным количеством ребер, никак от n не зависящим. Ну в константном скажем так, вот равном 6. В данном конкретном случае. То есть мы из множества всех C из n по два возможных ребер, выбираем случайным образом 6 штук. Вот спрашивается, с какой вероятностью такой случайный граф имеет хроматическое число 4. Вероятность того, что случайный граф вот в этой равномерной модели имеет X(G) = 4. Можно было вот это не писать, а просто написать вероятность того, что X(G) = 4. Ну извините, ну зачем-то написал. Вы уж меня особенно так строго за это не судите. Вот. Да, да, да. Просто вероятность того, что хроматическое число = 4. На первый взгляд страшно. Но опять не страшно ровно потому, что мы рассматриваем-то только 6-рёберные графы. А у 6-рёберных графов очень просто понять, когда хроматическое число = 4. А именно, ну не трудно сообразить, что вот такой вот граф — это просто полный граф на четырех вершинах. Он, разумеется, имеет и 6 ребер и хроматическое число 4. А дальше вы можете порисовать все возможные графы, у которых 6 ребер. Ну какие хотите. Связные, несвязные, можно вот такой граф например рассмотреть. У него 5 ребер, а отдельно еще ребрышко пририсовать. Или можно вот так его пририсовать. Как вам заблагорассудится. Вершин-то может быть сколько угодно. Главное чтоб ребер получилось 6. Но нетрудно видеть, что у каждого такого графа. Ну вы уж там можете их просто все перебрать, если захотите. У каждого такого графа просто не получается хроматическое число 4. Вот у этого графа, например, хроматическое число чему равняется? Ну 3, конечно. Раз, два, три. Это тоже красим во второй цвет, ну а это, скажем, тоже во второй. И это ничему не противоречит. Или в третий, если хотите. Ну то есть треугольник мы, конечно, вынуждены покрасить в 3 различных цвета, а на оставшиеся вершины нам замечательным образом хватит любого поднабора из этих трех цветов. Таким образом, нетрудно проверить, что все остальные графы красятся меньше чем в 4 цвета, и стало быть вероятность того, что случайный граф имеет хроматическое число 4 — это в точности вероятность того, что этот случайный граф, что из себя представляет? У него же 6 ребер. Это значит, что он из себя представляет связную компоненту K4 и кучу изолированных вершин. И кучу изолированных вершин. То есть вот эта вероятность — это вероятность того, что граф выглядит вот так: K4 и там какие-то изолированные вершины. Ну а эта вероятность считается как положено, то есть надо посчитать сколько всего существует таких графов. Их тривиальным образом C из n по 4 штуки. Просто мы выбираем те 4 вершины, которые затем мы попарно перелинкуем. И способы этой линковки уже делаются однозначно. Выбираются однозначно. Ну а делим мы это понятно на C из C из n по 2 по 6. Потому что вероятность равномерна и случайный граф рассматривается в равномерной модели. Видите, опять все получилось легко.