Лекции по Дискретным моделям, страница 3
Описание файла
PDF-файл из архива "Лекции по Дискретным моделям", который расположен в категории "". Всё это находится в предмете "дискретные модели" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Выбрать k вершин, образующих полный подграф, из p вершин можно Cpk способами.Оставшиеся Cp2 − Ck2 ребра могут быть проведены произвольно. Поэтому число графов с22p вершинами, содержащих полный подграф с k вершинами, не более Cpk · 2Cp −Ck . Отсюда2γ(p, k) ≤2Cpk · 2Cp −Ck22Cp=pk2.k!2CkПри p < 2k/2 получаем22k /22k/21γ(p, k) <=< .2k/2−k/2k!2k!2Разобьем все графы с p вершинами на пары (G, Ḡ). Тогда в силу доказанного выше приp < 2k/2 в этом разбиении найдется такая пара графов (G, Ḡ), что ни G, ни Ḡ не содержатполный подграф с k вершинами. Отсюда R(k, k) ≥ 2k/2 .Следствие 5.2.1.
При m, n ≥ 2 справедливо неравенство R(m, n) ≥ 2min(m,n)/2 .Вопросы и замечания просьба направлять Селезневой Светлане Николаевне по электронной почте selezn@cs.msu.su8.
