Задания для самостоятельной работы. 1. Покажите, что два графа изображенные на рисунке 2 изоморфны

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

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

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

4. Пусть - множество положительных целых чисел от 1 до 20, на котором задано отношение : «число х делится на число у», причем . Постройте граф данного отношения .

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

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

Вопросы для самоконтроля:

1. Что называется графом?

2. Какой граф называется неориентированным? ориентированным? Приведите примеры.

3. Что такое степень вершины?

4. Перечислите основные понятия, связанные с неориентированными графами.

5. Перечислите основные понятия, связанные с ориентированными графами.

6. Дайте определение изоморфного графа.

7. Дайте определение Эйлерова графа.

8. Какой граф называется гамильтоновым?

9. Какой граф называют связным?