Свойства графов

Все графы предполагаются простыми. Графы называются изоморфными, если существует биекция f между множествами их вершин, такая что {u,v} ребро Û {f(u), f(v)} – ребро.

1. Доказать, что граф имеет четное число вершин с нечетными степенями.

2. При встрече студентов состоялось 15 рукопожатий, трое человек сделали по 4 рукопожатия, а другие – по 3. Сколько было студентов.

3. Может ли существовать группа из 23 человек, каждый из которых знаком с пятью другими?

4. В соревнованиях по шахматам по круговой системе участвуют 5 человек. Все, кроме Иванова и Петрова, сыграли различное число партий. Сколько партий сыграли Иванов и Петров?

5. Можно ли нарисовать без отрыва карандаша граф K₆, у которого удалено одно ребро.

6. Найти число попарно неизоморфных графов, у которых 2 вершины имеют степень 2, 2 вершины имеют степень 3, и 2 вершины имеют степень 4. Остальные вершины имеют степень 0.

7. Найти число попарно неизоморфных графов, у которых 3 вершины имеют степень 2, 3 вершины имеют степень 3, и 3 вершины имеют степень 4. Остальные вершины имеют степень 0.

8. Доказать, что в простом графе, имеющем не меьше двух вершин, всегда найдутся две вершины одинаковой степени.

9. Какие графы из следующих ниже изоморфны:

10. Какие графы из следующих ниже изоморфны:

 

11. Найти число всех попарно неизоморфных графов, имеющих 4 вершины. Нарисовать эти графы.

Ответ: (см. рис.4.8) существует 11 неизоморфных графов

Рис. 4.8. Графы, имеющие 4 вершины

 

12. Кратчайший путь соединяющий вершины u и v в графе называется геодезическим путем между вершинами. Его длина обозначается d(u,v). Диаметром D(G) графа называется длина самого длинного геодезического пути в этом графе, т.е. D(G)=max{d(u,v): u,vÎV}. Найти диаметры графов

(1) K₅ ;

 

(2)

 

(3) Для дерева.

 

13. Матрица смежности состоит из коэффициентов a_ij=1 Û вершины i и j смежны.

(1) Построить матрицы смежности для графов K₃ и K₄ ;

(2) Доказать, что сумма коэффициентов i-й строки матрицы смежности равна степени i-й вершины;

(3) Построить матрицу смежности графа, состоящего из вершин и ребер куба.

(4) С помощью матрицы смежности построит матрицу, коэффициентами которой является количества путей длины 2 из вершины i в вершину j .

(5) Как связаны след матрицы A³ с числом треугольников в графе?

14. Циклы {z₁, z₂, × × × , z_n}называются независимыми, если z₁Dz₂D × × × Dz_n ¹ Æ Доказать, что у связного графа максимальное число независимых циклов равно q-p+1.

15. Сколько компонент связности имеет лес, содержащий 76 вершин и 53 ребра?

16. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.

17. В компании, состоящей из пяти студентов, среди любых трех найдутся два знакомых и два незнакомых. Доказать, что компанию можно рассадить за круглым столом таким образом, что любые два соседа будут знакомы.