442
правки
Изменения
→Индуцированная теорема Рамсея
}}
==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется индуцированным подграфом (англ. ''induced subraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }} {{Определение|id=def10|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским будем называть '''рамсеевским графом ''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}{{Определение|id=def11|definition='''Индуцированным числом Рамсея'''(англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф для графа <tex>H</tex> на <tex>x</tex> вершинах.}}induced Ramsey number
При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.
{{Теорема
где <tex>V_1(G)</tex> и <tex>V_2(G)</tex> — разбиение множества вершин <tex>V(G)</tex> на две доли, а рёбра соединяют вершины из разных долей.
{{Определение
|id=def10def11
|definition=
Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём погружением, если оно удовлетворяет двум условиям.<br>
