Следующий пункт нашей программы — это некое совсем забавное утверждение. Но для того, чтобы это забавное утверждение сформулировать, а потом продемонстрировать, чем оно интереснее, чем оно лучше, нежели признак Дирака, нам потребуется ввести ещё парочку дополнительных определений. И это мы сейчас сделаем. Идея того признака, о котором я хочу теперь рассказать, она появилась позже, конечно, чем идея признака Дирака, и автором этого признака является Хватал. Такой тоже замечательный математик. Значит, давайте прежде, чем я сформулирую собственно признак, я введу две важных характеристики графа, которые, ну без которых просто нельзя этот признак сформулировать, куда ж тут деваться. Так. Ну давайте, у нас есть какой-то граф G = ( V, E ). И есть какое-то множество вершин нашего графа. Теоретически оно может совпадать даже со всем множеством вершин, поэтому я подчеркнул эту возможность значком потенциального равенства. Ну есть какое-то подмножество, возможно даже, само множество вершин. И оно устроено таким образом, что никакие 2 вершины этого подмножества не соединены ребром. Никакие 2 вершины не соединены ребром. Ну можно сказать так: для любых двух вершин из множества W пара ( x, y ) не принадлежит множеству E. Любые 2 вершины не соединены ребром. Такое множество принято называть «независимым». W называется «независимое множество вершин». Независимое множество вершин. Ну по-всякому, конечно, можно называть, но вот это основной термин, и я бы настаивал на том, чтобы мы пользовались именно им. «Независимое множество». А дальше можно рассмотреть собственно характеристику графа, которую традиционно принято обозначать α (G). И по своему определению, это есть максимальное среди всех чисел k, таких, что существует множество вершин нашего графа, имеющее мощность k, ну и такое, что W независима. То есть, говоря словами, всё очень просто. Это количество вершин в самом большом, самом жирном, самом большом по мощности независимом множестве вершин графа. Вот перебираем все независимые множества вершин и находим среди них такое, которое имеет самую большую мощность. Оно, конечно, не обязано быть единственным, но мощность-то его одна. Вот она однозначно и определяется. Вот это число α (G) принято называть числом независимости графа. Это очень важная характеристика графа, с которой мы ещё будем сталкиваться в дальнейшем в наших лекциях, которая связана, безусловно, с хроматическим числом графа. В общем, это очень важная характеристика, которой занимается куча народу с самых разных точек зрения, в том числе, конечно, и с прикладных. Так, α (G), число независимости, ну вроде определили, да? Значит, важно, чтоб внутри этого множества не было никаких рёбер, и чтобы оно было самым жирным по мощности среди множества вершин нашего графа. Ну не знаю, давайте я все-таки для полноты картины пару слов скажу, пару примеров, что ли, приведу. Чтоб было понятно, как устроено независимое множество вершин в том или ином графе. Ну вот, скажем, нарисую какую-нибудь картиночку, вот такую вот. Ясно, что в этой картиночке самое большое независимое множество — это либо вот это, либо вот это. То есть 2 вершины, которые не соединены между собою ребром. Стало быть, α от вот этого графа в точности равняется 2, но величина 2 здесь достигается сразу на 2 различных подмножествах, каждое из которых является максимальным по мощности среди всех независимых множеств вершин нашего графа. Вот. Ну вообще можно взять любой простой цикл и сообразить, чему равняется число независимости в нём. Понятно, что надо брать просто вершины через одну. И это будет максимальное независимое множество внутри цикла. А если вы, скажем, возьмете в качестве примера полный граф на n вершинах, то в нём... А как вы думаете, есть независимое множество или нет? В полном графе на n вершинах? Есть. Это одновершинные множества. То есть если вы возьмёте, например, треугольник (полный граф на 3 вершинах), то, вопреки вашим ожиданиям, независимое множество в этом графе есть. Каждая вершина по определению образует независимое множество. Потому что для любых 2 вершин в этом множестве между ними ребра, конечно, нету. Ну множество одноэлементное, в нём просто нету подмножеств мощности 2. Поэтому про них можно честно сказать, что вот это выполнено, да, это действительно так. То есть в любом полном графе на n вершинах, конечно, все независимые множества имеют размер 1. И α от такого графа равняется 1. Вот. Ну я надеюсь, после этих замечаний, после этих примеров стало совсем понятно, что такое число независимости графа.