Только что для графа без треугольников,
мы доказали некоторое соотношение такое очень симпатичное и симметричное,
для произведения числа независимости на размер минимального вершинного покрытия.
Но давайте установим еще одно похожее соотношение,
причем вне зависимости от того — есть в графе треугольники, нет их...
Просто некое общее утверждение, которое на самом деле исключительно полезно в науке.
Об этом я тоже скажу.
Утверждение такое: для любого
графа G с множеством
вершин V и множеством ребер E, давайте я так симметрично
тоже напишу, его хроматическое число χ(G),
умноженное на его число независимости, видите — тут для любого графа абсолютно,
никаких предположений не делается, а вот такое вот симпатичное произведение не
меньше, но только не чем мощность E, как это было в той задаче, а чем мощность V.
Произведение хроматического числа и числа независимости всегда не меньше,
чем количество вершин в графе.
На самом деле это очень простое утверждение.
Мы его сейчас вмиг докажем.
Ну действительно, смотрите — хроматическое число по своему определению устроено как?
Что наше множество вершин распадается в дизъюнктное
объединение каких-то там подмножеств V1...
V с индексом χ(G), но это, собственно, цвета.
То есть V1 мы красим в первый цвет, V2 мы красим во второй цвет,
V χ(G) мы красим в χ(G)-й цвет.
Значит, оно так распадается, причем, по определению хроматического числа,
внутри каждого цвета нету ребер.
Не бывает вершин, которые были бы соединены ребром,
и при этом имели бы один и тот же цвет.
Такое просто запрещено.
Но тогда смотрите, ясно,
что для любого i — Vi, это независимое множество.
Независимое множество.
Повторяю: в нем нет ребер,
потому что у нас не бывает ребер с концами одного цвета.
Это как раз запрещено по определению хроматического числа нашего графа.
Замечательно!
Давайте посмотрим по-другому на это.
Мощность V конечно равняется мощность V1 +...
+ мощность V с индексом χ(G).
Раз они не пересекались попарно, эти множества,
каждое в свой цвет было покрашено, то, конечно, количество всех вершин,
это сумма количества вершин, покрашенных в каждый очередной цвет.
При этом каждый и вот этих V(i), каждый цвет,
повторяю — является независимым множеством.
Но значит вот эта мощность, которая здесь написана, и вот эта мощность — все
мощности, которые мы написали, каждая из них не превосходит величины α(G).
Она не может быть больше, чем размер самого жирного независимого множества.
У нас получается α(G) умножить на χ(G).
Ну и все.
Неравенство доказано, потому что, читаем его справа налево, и получаем,
что α(G), умноженное на χ(G) больше либо равняется мощности V,
что собственно и требовалось доказать.
Теперь, пара слов по поводу того, как это используется.
Конечно, хроматическое число графа,
исходя вот из этого неравенства, можно оценить количеством вершин графа,
поделенным на его число независимости.
Вот можно так оценить?
Ну, понятно — из этого неравенства это моментально следует.
Это просто равносильные утверждения.
α(G) нулю не равняется, так что делить на него спокойно можно.
Замечательно!
Вот это вот некоторая граница нижняя для хроматического числа графа.
В следующей задаче мы узнаем некоторую классическую верхнюю границу для
хроматического числа графа, но, покамест, давайте посмотрим на эту границу.
Есть еще одна замечательная граница, которая делается совсем просто.
χ(G), разумеется, не меньше,
чем количество вершин в самом жирном полном подграфе нашего графа.
То есть не меньше, чем величина ω(G).
ω(G) — это количество вершин в самом большом по мощности
полном подграфе графа G.
Ну ясно, что если вы хотите покрасить полный граф, то вы должны
задействовать столько цветов, сколько в этом полном графе имеется вершин.
Поэтому χ(G) никак не меньше,
чем количество вершин вот в этом самом большом полном подграфе нашего графа.
Так вот, давайте я не буду сейчас отвечать на этот вопрос, а задам его слушателям!
Подумайте на досуге!
Ну, обычно когда передо мной сидит большая аудитория,
я прошу сразу проголосовать кому как кажется.
Ну а вы передо мной не сидите.
Вы там где-то в виртуальном мире существуете по отношению ко мне.
Поэтому давайте вы просто подумаете на досуге.
В каком смысле, вернее, не в каком смысле, а какая из этих оценок лучше?
В каком смысле лучше?
А давайте сделаем так: зафиксируем некоторое число
вершин n — это число вершин, и посмотрим на все графы,
которые на множестве из n вершин могут быть построены.
Ну, понятно, что количество всех графов,
это 2 в степени C из n по 2 — это банальная вещь.
И вот вопрос звучит следующим образом: вот в таком жирном множестве графов, множестве
графов, которое имеет мощность 2 в степени C из n по 2, каких графов больше?
Тех, для которых вот эта оценка сильнее, чем вот эта,
или тех, для которых наоборот — нижняя оценка сильнее, нежели верхняя?
Ну, наверное, в каком-то смысле можно догадаться до ответа,
просто потому, что, ну — интенция моя здесь такова.
Так я как-то вот на вас давлю всем своим авторитетом,
что более или менее понятно, что должно быть правильным ответом.
Но может и непонятно.
Кто знает?
Так что вот подумайте, какая из двух оценок чаще оказывается лучше,
нежели другая из них.
Вот это вот такой интересный вопрос на будущее — поразмышлять.