Ну что ж друзья, давайте сегодня обсудим еще некоторый класс задач. На самом деле эти задачи называются экстремальными задачами теории графов, звучит устрашающе, но никакого экстремизма-то конечно не будет, будут просто классические задачи теории графов, которые очень важны в самых разнообразных приложениях, и связаны напрямую с раскрасками графов, о которых мы вообще-то в этом курсе уже немножко говорили. Вот, ну, так если говорить совсем общо, то речь пойдет о том, что называется турановскими задачами теории графов и рамсеевскими задачами теории графов, вот именно этими экстремальными проблемами мы и позанимаемся. Но опять же это звучит как-то так устрашающе, давайте просто поставим какую-нибудь простейшую задачу и будет совершенно понятно о чем идет речь. Итак, вот у нас есть какой-то граф, который как обычно представляет из себя пару — множество вершин и множество ребер, в этом для нас ничего удивительного, конечно, нету. И давайте введем обозначение для количества его вершин. Пусть n — это количество вершин в этом графе. Ну тоже какое-то натуральное число, ничего такого пока удивительного нет. А вот теперь давайте посмотрим на то, чему равняется число независимости этого графа. Давайте, как водится, обозначим его α (G). Я говорю «как водится», потому что в рамках этого курса у нас уже обсуждалось число независимости, на самом деле, когда мы с вами говорили о неком признаке гамильтоновости графа. Ну, для полноты картины, для тех, кто может быть слушает только эту лекцию, я все-таки напомню, что такое число независимости графа, это вещь такая, очень полезная. Значит, число независимости графа — это количество вершин, но можно сказать, смешно — в любом максимальном по мощности независимом множестве вершин этого графа. Смешно, потому что если вы не знаете что такое независимое множество вершин, то, естественно, вы такого определения не поймете. Ну в общем, количество вершин в самом... в любом, самом большом по мощности, самом большом по мощности, то есть как раз по числу вершин, по мощности, таком множестве вершин, в самом большом по мощности, таком множестве вершин, что никакие 2 вершины в нем, никакие 2 вершины в нем не соединены ребром, [ПИШЕТ НА ДОСКЕ] в нем не соединены ребром. Вот именно такое множество, в котором никакие 2 вершины не соединены ребром, оно-то и называется независимым множеством вершин. По сути, повторяю, это напоминание того материала, который у нас уже в рамках этого курса был. Но все-таки вот, я для полноты картины, все-таки решил его напомнить. Итак, в последний раз повторяю, независимое множество вершин — это как раз такое множество вершин, что никакие 2 вершины в нем не соединены ребром. И вот мы смотрим на все возможные независимые множества вершин в нашем графе и ищем среди них те, которые имеют самое большое количество вершин, самое большое число элементов, у которых мощность самая большая. И вот мощность любого такого самого жирного независимого множества мы обозначаем α (G), вот такое классическое обозначение, самое большое множество, в котором нету ребер, мощность самого большого множества, в котором нету ребер. Давайте я сразу до кучи напомню, что есть такая, если угодно, двойственная характеристика ω (G). Это то, что называется «кликовое» число графа. Значит, есть количество вершин, количество вершин в самом, давайте я вот это повторю просто такими палочками, чтобы лишний раз не писать. В самом большом по мощности таком множестве вершин, что вот здесь вот? Ни никакие 2 вершины в нем не соединены ребром, как это было в случае ω(G), а любые 2 вершины в нем соединены ребром, что любые 2 вершины в нем, наоборот, соединены ребром. Это, естественно, такая двойственная характеристика графа, потому что если у нас в графе есть большое независимое множество вершин, то есть множество вершин, которое полностью свободно от ребер, то мы можем сделать так: мы можем взять наш граф, те ребра, которые были в этом графе, удалить из него, а те ребра, которых не было в этом графе, провести, наоборот. Такую вот сделать процедуру уничтожения ребер, которые были в графе, и возникновение ребер, которых там не было. Такой двойственный граф рассмотреть. И вот понятно что, если у нас в исходном графе было какое-то независимое множество, то в таком двойственном графе оно как раз будет образовывать клику, полный подграф. И наоборот, поэтому давайте двойственный граф обозначим G с чертой. Понятно, что α (G) с чертой = ω (G). И наоборот, ω (G) с чертой = α (G). То есть, число независимости исходного графа это — «кликовое» число двойственного графа, вот такой вот двойственной операцией полученного из исходного. Ну это просто такая вот казуистика понятная, ничего в этом месте пока особенного тоже нет. Давайте пока будем интересоваться, все-таки, повторяю, не числом ω (G), а числом α (G). ω (G) я напомнил, потому что чуть позже оно мне в общем, наверное, пригодится.