442
правки
Изменения
→Числа Рамсея для произвольных графов
|id=def8
|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> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Существует и другое определение чисел Рамсея для произвольных графов.
|id=def16
|definition=
Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея ''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>, либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex>.
}}
Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.
