Изменения

|id=def1

|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}

{{Определение

|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>, представленное ранее.