Тема 3. Операции над графами

Задание 1. Постройте подграфы изображённого графа G, изобразите их дополнения и укажите число всех подграфов графа G.

Задание 2. Сколько подграфов имеет полный граф K ₂, K ₃, K ₄ и, вообще, K_n?

Задание 3. Укажите число неизоморфных подграфов для графов, рассмотренных в двух предыдущих заданиях.

Задание 4. При каких значениях n и m:

a) пустой граф О_n является подграфом полного графа K_m;

б) полный граф K_n является подграфом графа K_m;

в) пустой граф О_n является подграфом графа О_m;

г) полный граф K_n является подграфом пустого графа О_m.

Задание 5. Граф на n вершинах имеет m ребер. Сколько ребер имеет его дополнение?

Задание 6. Что можно сказать о следующих графах: а) дополнении полного двудольного графа; б) дополнениях графов тел Платона; в) дополнении графа Петерсена?

Задание 7. Получите из графа G новый граф: уничтожением ребра е; стяжкой этого ребра.

Задание 8. Говорят, что граф G (W) является индуцированным подграфом графа , если , где , а содержит все ребра из , которые соединяют вершины из . Для изображённого графа постройте подграфы .

Задание 9. Если G (W) – полный граф, то говорят, что множество W образует клику в графе G. Приведите примеры клик в графе предыдущей задачи.

Задание 10. Матчингом (анг. matching – согласование, подбор, приведение в соответствие) в графе называется его подграф, содержащий все вершины графа G, при этом никакие два ребра из не имеют общей вершины. Матчинг называется совершенным, если каждая вершина графа G принадлежит ровно одному ребру матчинга. Приведите примеры матчинга; совершенного матчинга.

Задание 11. Ребро (u, v) в графе G называется мостом, если после его удаления вершины u и v становятся несвязными, т.е. не существует соединяющего их пути в графе G. Докажите следующие утверждения, которые являются признаками моста в графе:

ребро (u, v) является мостом тогда и только тогда, когда:

а) (u, v) – единственный путь, соединяющий вершины u и v;

б) существуют вершины a и b такие, что каждый соединяющий их путь содержит ребро (u, v);

в) (u, v) не принадлежит ни одному циклу графа;

г) при удалении ребра (u, v) число компонент графа увеличивается на единицу.

Задание 12. Найдите все мосты в изображённом графе и докажите, что связный граф является деревом тогда и только тогда, когда каждое его ребро – мост.

Задание 13. Вершина графа называется вершиной-разрезом, если после её удаления число компонент графа увеличивается. Найдите все вершины разрезы в графе предыдущей задачи. Докажите, что вершина дерева является вершиной-разрезом тогда и только тогда, когда её степень не меньше 2.

Задание 14. Граф F называется минором (лат. minor – меньший) графа G, если он может быть получен из графа G последовательным применением операций уничтожения ребер, стяжки ребер и уничтожения вершин (в любом порядке). Приведите примеры миноров изображённого графа, а также графов K ₅ и K _3,3.

Является ли граф

минором графа G; графа K ₅; графа K _3,3?

Задание 15. Евклидовым произведением графов и называется граф , где , а . Постройте Евклидовы произведения графов O ₁ и K ₂; K ₃ и P ₂; C ₃ и K _1,2.

Задание 16. Объединением графов и , множества вершин которых не пересекаются, называется граф , где . Докажите, что . Приведите другие примеры объединения графов.

Задание 17. Соединением графов и , множества вершин которых не пересекаются, называется граф , где . Покажите, что граф является соединением графов и , а колесо – соединением графов и K ₁. Приведите другие примеры соединения графов.

Задание 18. Приведите пример: а) колеса, дополнением которого является цикл; б) связного графа, не представимого в виде соединения двух графов. Что можно сказать о соединении двух полных графов; дополнении соединения двух графов?

Задание 19. Какие из равенств верны:

а) ;

б) ?

Задание 20. Подвешенным графом для графа G называется граф, полученный из графа G добавлением новой вершины, соединенной со всеми вершинами графа G. Найдите .