442
правки
Изменения
→Числа Рамсея
|id=def2
|definition='''Число Рамсея''' <tex>r(m, n)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}
[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<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 ребер, тогда согласно принципу Дирихле хотя бы три из них одного цвета. Для определенности положим, что хотя бы 3 ребра, соединяющие вершину <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>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке.
