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

Все графы предполагаются простыми. Графы называются изоморфными,

если существует биекция 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. Какие из графов, приведенных на рис. 4.12, изоморфны?

Рис. 4.12. Примеры графов

10. Какие из графов, приведенных на рис. 4.13, изоморфны?

Рис. 4.13. Примеры графов

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

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

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

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

Рис. 4.15. Пример графа

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. В компании, состоящей из пяти студентов, среди любых трех найдутся два знакомых и два незнакомых. Доказать, что компанию можно рассадить за круглым столом таким образом, что любые два соседа будут знакомы.

Поиск по сайту: