3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея (Слайды к лекциям), страница 2
Описание файла
Файл "3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея" внутри архива находится в папке "Слайды к лекциям". PDF-файл из архива "Слайды к лекциям", который расположен в категории "". Всё это находится в предмете "дискретные модели управляющих систем" из Аспирантура и докторантура, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
R(2, 2) = 2.Оценим долю γ(p, k) графов с p помеченными вершинами, вкоторых найдется полный подграф с k вершинами.Возможных ребер в графах с p вершинами ровно Cp2 , откуда2графов с p вершинами в точности 2Cp .Выбрать k вершин, образующих полный подграф, из p вершинможно Cpk способами.Оставшиеся Cp2 − Ck2 ребра могут быть проведены произвольно.Поэтому число графов с p вершинами, содержащих полный22подграф с k вершинами, не более Cpk · 2Cp −Ck .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оНижняя оценка числа РамсеяДоказательство. Значит,2γ(p, k) ≤2Cpk · 2Cp −CkCp22=pk2k!2Ck.При p < 2k/2 получаем2γ(p, k) <2k/212k /2=<.2k!2k!2k /2−k/2Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оНижняя оценка числа РамсеяДоказательство.Разобьем все графы с p вершинами на пары (G , Ḡ ).Тогда по доказанному выше при p < 2k/2 в этом разбиениинайдется такая пара графов (G , Ḡ ), что ни G , ни Ḡ несодержат полный подграф с k вершинами.Отсюда R(k, k) ≥ 2k/2 .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оНижняя оценка числа РамсеяСледствие 5.1.
При m, n ≥ 2 справедливо неравенствоR(m, n) ≥ 2min(m,n)/2 .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЛитература к лекции1. Харари Ф. Теория графов. М.: Мир, 1973. С.28-31.2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008. P.301-302, 308-313.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оКонец лекции.