Изменения

Перейти к: навигация, поиск

Теория Рамсея

11 байт добавлено, 20:59, 29 ноября 2018
Числа Рамсея
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в данной задаче просится найти, какое минимальное количество людей должно присутствовать на празднике, чтобы хотя бы <tex>m</tex> человек были друзьями, или хотя бы <tex>n</tex> человек не будут знать друг друга. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(m, n)</tex>, представленное ранее.
Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны 5 ребер, тогда согласно принципу Дирихле хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3 </tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex>, то есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, то есть красный треугольник. Таким образом, <tex>r(3,3) \le 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке.
442
правки

Навигация