244
правки
Изменения
Нет описания правки
# $P_k$ - путь длины $k-1$ (содержащий $k$ вершин и $k-1$ ребро). Найдите $R(P_3, P_3)$.
# Найдите $R(P_4, P_4)$
# Покажите, что добавление ребра может сделать совершенный граф несовершенным
# Покажите, что удаление ребра может сделать совершенный граф несовершенным
# Граф называется хордальным, если любой простой цикл длины больше трех имеет хорду (то есть ребро, соединяющее не соседние в цикле вершины). Докажите, что любой интервальный граф является хордальным
# Докажите, что дополнение любого интервального графа является графом сравнений
# Приведите пример хордального графа, который не является интервальным
# Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)
# Совершенный порядок удаления вершин из графа (perfect elimination order, PEO) это последовательность вершин графа $v_1, v_2, \ldots, v_n$, такая что для любой вершины $v_i$ все ее соседи с номерами $j > i$ образуют клику. Докажите, что хордальный граф имеет PEO.
# Докажите, что если граф имеет PEO, то он хордальный.
# Докажите, что хордальный граф является совершенным.
# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| \le \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
# Докажите, что если $G$ является реберным графом, то $\chi(G) \in \{\omega(G), \omega(G)+1\}$.
# Опишите графы, у которых реберный граф является совершенным
# Докажите, что граф $G$ является совершенным тогда и только тогда, когда его любой непустой индуцированный подграф $H$ содержит независимое множество $A$, такое что $\omega(H \setminus A) < \omega(H)$.
# Рассмотрим граф $G$, такой что для любого индуцированного подграфа $H$ любая максимальная клика и любое максимальное независимое множество имеют общую вершину. Докажите, что $G$ совершенный.
# Докажите, что $G$ обладает свойством из предыдущего задания тогда и только тогда, когда $G$ не содержит индуцированного пути из трех вершин (любые три вершины соединены либо 0, либо 1, либо 3 ребрами).
# Рассмотрим совершенный граф $G$. Докажите, что можно покрыть все вершины графа независимыми множествами (обозначим семейство этих независимых множеств $\mathbb{I}$), а также покрыть все вершины графа кликами (обозначим семейство этих клик как $\mathbb{J}$, что для любых $A \in \mathbb{I}$ и $B \in \mathbb{J}$ выполнено $A \cap B \ne \emptyset$.
# Рассмотрим совершенный граф $G$. Заметим каждую его вершину $x$ на произвольный совершенный граф $G_x$ (вершины графов $G_x$ и $G_y$ соединены друг с другом, если было ребро $xy$). Докажите, что получившийся граф является совершенным.
# Предложите полиномиальный алгоритм проверки, что граф является хордальным.
# Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.
# Предложите полиномиальный алгоритм поиска $\chi(G)$ для хордального графа $G$.
