Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Контрольные задания.
Построить графы для решения задач 1 — 2.
1. Перевозчику (П) нужно переправить через реку волка (B), козу (К) и мешок с капустой (М). Лодка так мала, что кроме перевозчика может взять только один из этих объектов. Кроме того, капусту нельзя оставлять вместе с ко­зой, а козу — с волком. Как можно осуществить переправу?
2. Два человека имеют полный кувшин воды в 8 литров, а также два пустых кувшина в 5 и в 3 литра. Как они могут разделить воду поровну?
3. Пусть имеется множество V, состоящее из 3 доку­ментов. Построить граф для отношения a  A, харак­те­ри­зу­ющий принадлежность документа a множеству A, где A про­бегает все подмножества множества V.
4. Пусть имеется множество T, состоящее из трех ко­м­пью­терных сетей: S1, S2, S3. Известно, что компьютер K1 входит только в сеть S1, компьютер K2 — только в сеть S2, а компьютер K3 входит в две сети: S1 и S2. Построить граф, характеризующий принадлежность компьютера компьютер­ным сетям.
5. Показать, что два графа на данном рисунке изоморфны.


6. Потоки документов циркулируют между городами A₁, A₂, A₃ и городами B₁, B₂, B₃. Можно ли проложить не­пересекающиеся маршруты, соединяющие каждый город A_i с каждыми городом B_j?
7. Найти степени вершин для графов тетраэдра и ку­ба.

8. Найти сумму степеней всех вершин для следующего графа:
9. Построить матрицы смежности и инцидентности для тетраэдра.
10. Являются ли эйлеровыми графами: прямоугольник с главной диагональю, куб?
11. Какова мощность минимального покрытия куба цепями?
12. На графе, который определен прямоугольником с непересекающимися диагоналями построить покрытие графа цепями.
13. Решить задачу о званом обеде, когда число участников обеда равно 5: хозяин — мужчина. Остальные две пары (мужчина, женщина) — гости. Хозяин знаком со всеми приглашенными мужчинами. Обе женщины знакомы друг с другом.
14. Привести любое решение задачи шахматного коня.
15. Применив алгоритм с возвратами построить все га­мильтоновы циклы для графа, образованного квадратом с пересекающимися диагоналями.