299
правок
Изменения
→Числа Рамсея для произвольных графов
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def11def7
|definition=
Пусть <tex>H_1,h_2</tex> — два данных графа. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета 1 или подграф изоморфный <tex>H_2</tex> с рёбрами цвета 2
{{Лемма
|id=lemma1l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>. База для <tex>n=1</tex> очевидна. Докажем индукционный переход <tex>n-1 \rightarrow n(n>1</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex> Тогда <tex>|U|=\alpha(H) \le m-1</tex>, следовательно <tex>v(H-U) \ge (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \le m-1</tex>.
}}
{{Теорема
|id=th10 ter5 |author=V. Chvatal5
|statement=Пусть <tex>T_n</tex> — дерево на <tex>n</tex> вершинах. Тогда <tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>.
|proof=
