Рассмотрим граф на n вершинах. Доказать, что в нем существует подмножество S вершин исходного графа, такое что мощность S не меньше $% \sum_{i=1}^n \frac{1}{d_i +1}$%. Доказать, что между вершинами из S нет ребер.

задан 7 Окт '15 21:02

10|600 символов нужно символов осталось
1

Обращаю внимание на неточность в формулировке. Сначала требуется доказать, что существует множество вершин достаточно большой мощности. Ясно, что оно существует -- возьмём всё вершины. Ограничений ведь никаких нет! Далее требуется доказать, что между вершинами этого (произвольно взятого) множества нет рёбер, что заведомо неверно.

Почему бы сразу не сформулировать правильно: доказать, что существует подмножество $%S$% такой-то мощности, между вершинами которого нет рёбер? Не говоря о том, что в условии вообще не сказано, что такое $%d_i$%.

Теперь доказательство. В принципе, оно хорошо известно: с помощью этого рассуждения можно доказать теорему Турана.

Рассмотрим случайную нумерацию вершин $%v_1$%, ... , $%v_n$%. К ней применим "жадный алгоритм" построения $%S$%. Вершину $%v_1$% в него включаем; далее по индукции включаем очередную вершину тогда и только тогда, когда она не соединена ни с одной из уже включённых.

Мощность построенного множества $%S$% есть случайная величина, зависящая от перестановки. Оценим матожидание этой с.в. и докажем, что оно не меньше $%\sum_{i=1}^n\frac1{d_i+1}$%, где $%d_i$% -- степень $%i$%-й вершины. Из этого будет следовать, что на какой-то перестановке значение $%S$% будет не меньше среднего. По построению, в подграфе с множеством вершин $%S$% рёбер не имеется.

Для $%i$%-й вершины (в фиксированной нумерации) введём с.в. $%\xi_i$%, равную 1 или 0 в зависимости от попадания этой вершины в $%S$%. Ясно, что $%MS=\sum_{i=1}^nM\xi_i=\sum_{i=1}^nP\{\xi_i=1\}$%.

Рассмотрим достаточное условие того, что вершина $%i$% попадёт в $%S$%. Она соединена с какими-то $%d_i$% вершинами, и в $%S$% она гарантированно попадёт, если в случайно взятой нумерации она окажется первой среди всех $%d_i+1$% вершин, включая себя, а также всех вершин, ей смежных. Поскольку все вершины равноправны (в смысле порядка следования в случайной перестановке), вероятность такого события равна $%\frac1{d_i+1}$%, то есть $%P\{\xi_i=1\}\ge\frac1{d_i+1}$%, откуда всё следует.

Можно заметить, что к данной оценке далее можно применить неравенство о среднем, и получить оценку размера $%S$% в зависимости от количества рёбер графа, которое равно сумме степеней вершин.

ссылка

отвечен 8 Окт '15 4:38

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,233
×528
×166
×7

задан
7 Окт '15 21:02

показан
682 раза

обновлен
8 Окт '15 4:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru