Задачи и упражнения. 1. Покажите, что два графа на рис.2.46 изоморфны

1. Покажите, что два графа на рис.2.46 изоморфны.

2. «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

3. Найдите число частичных графов конечного графа с m ребрами.

4. Каково число ребер в полном неориентированном графе с n вершинами?

5. Пусть U – множество положительных целых чисел, на котором задано отношение «a есть делитель b». Постройте граф этого отношения для множества целых чисел от 1 до 20.

6. На рис.2.47 задан граф отношения «быть сестрой» на множестве студентов-родственников нашего факультета. Постройте по рис.2.47 граф отношения «быть братом».

7. Постройте графы отношений для задач №№ 11 – 17 главы 1.

8. Постройте матрицы смежности и инциденций для правильных многогранников: тетраэдра, куба, октаэдра. Найдите для каждого из них число внутренней устойчивости, число внешней устойчивости, центр, периферийные вершины, радиус, диаметр.

9. Для графа, изображенного на рис.2.48 найдите:

а) матрицу смежности (вершин);

б) матрицу инциденций;

в) наибольшее внутренне устойчивое множество;

г) наименьшее внешне устойчивое множество;

д) матрицу отклонений;

ж) центр и радиус графа.

10. Постройте графы, для которых радиус r равен 2, 3, и такие графы, для которых диаметр d равен 2, 3.

11. Определите, какие из графов трех правильных многогранников имеют эйлеровы циклы. В тех случаях, когда эйлерова цикла нет, определите, сколько требуется цепей, чтобы покрыть все ребра.

12. Какие из графов правильных многогранников имеют гамильтоновы цепи и циклы?