Изменения

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

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

99 байт добавлено, 21:36, 29 ноября 2018
м
Числа Рамсея для произвольных графов
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1) <\tex> Докажем, что <tex>r(T_n,K_m) \ge (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1 <\tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2<\tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1<\tex>. Тогда любой связный подграф с рёбрами цвета <tex>1 <\tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1<\tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2 <\tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
<tex>2) <\tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2<\tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#l1|лемме 1]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах в частности, дерево, изоморфное <tex>T_n</tex>.
}}
442
правки

Навигация