Тема 8. Двудольные графы

Задание 1. Приведите примеры: двудольного графа; полного двудольного графа; связного двудольного графа; несвязного двудольного графа; двудольного графа, являющегося деревом; двудольного графа, являющегося полным графом; двудольного графа, являющегося регулярным графом.

Задание 2. Что можно сказать о полном двудольном графе, если мы знаем, что он регулярен?

Задание 3. Докажите, что любой простой путь , любой простой цикл четной длины и любое дерево является двудольным графом. Является ли двудольным графом любой путь общего вида; любой цикл общего вида?

Задание 4. Укажите наибольшее (наименьшее) число ребер, которое имеет полный двудольный граф на n вершинах.

Задание 5. Может ли быть двудольным графом колесо, полный граф, пустой граф, гиперкуб, гиперполукуб, соединение двух графов, объединение двух графов, евклидово произведение двух графов?

Задание 6. Какие из графов тел Платона являются двудольными?

Задание 7. Дайте определение трехдольного графа. Сколько вершин и ребер имеет полный трехдольный граф ? Что можно сказать о регулярном полном трехдольном графе?

Задание 8. Для данного графа линейным (реберным) графом называется граф, вершинами которого являются ребра графа , причем две вершины и в связаны ребром, если ребра и в графе имели общую вершину. Докажите, что Докажите, что линейный граф для регулярного графа является регулярным. Что можно сказать о графах, линейных для дерева на n вершинах?

Задание 9. Для каждого из двух графов, изображенных на рисунке. Постройте их линейные графы.

Задание 10. Найдите выражение для числа ребер линейного графа L (G) через степени вершин графа G.

Задание 11. Покажите, что линейные графы графов и изоморфны.

Задание 12. Докажите, что линейный граф для полного графа имеет вершин и является -регулярным. Получите аналогичные результаты для .

Задание 13. Приведите примеры графа, изоморфного своему линейному графу; пример графа, дополнение которого изоморфно своему линейному графу.

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