Ответы и решения к главе 2

Задача 2.7. Характеристики графа: количество вершин — 8, ре бер — 9 (рис. 7.2.1).

Решение задачи 2.7

Рис. 7.2.1. Решение задачи 2.7

Задача 2.10. Характеристики графа: количество вершин — 9, ре бер — 29 (рис. 7.2.2).

Решение задачи 2.10

Рис. 7.2.2. Решение задачи 2.10

Задача 2.14. Характеристики графа:

  • а) количество вершин — 13, ребер — 38;
  • б) количество вершин — 12, ребер — 0.

Задача 2.15. а) 66 ребер; б) 21 ребро.

Задача 2.16. Характеристики графа:

  • а) количество вершин — 17, ребер — 48;
  • б) количество вершин — 16, ребер — 48.

Задача 2.17. Характеристики графа:

  • а) количество вершин — 17, ребер — 120;
  • б) количество вершин — 16, ребер — 104.

Задача 2.18. Характеристики графа:

  • а) количество вершин — 21, ребер — 56;
  • б) количество вершин — 20, ребер — 56.

Задача 2.19. Характеристики графа:

  • а) количество вершин — 21, ребер — 161;
  • б) количество вершин — 20, ребер — 141.

Задача 2.20. Характеристики графа:

  • а) количество вершин — 14, ребер — 31;
  • б) количество вершин — 13, ребер — 31.

Задача 2.25. Количество компонент связности равно 1.

Задача 2.28. Количество компонент связности равно 2.

Задача 2.29. Количество компонент связности равно 2 или 3.

Задача 2.30. Количество компонент связности может быть равно 1, 2 или 3.

Задача 2.31. Количество компонент связности может быть равно 1, 2 или 3.

Задача 2.33. Указанный граф имеет максимально 15 ребер.

Задача 2.36. Указанный граф имеет максимально 16 ребер.

Задача 2.37. Указанный граф имеет минимально 16 ребер.

Задача 2.39. Ребра удалять не нужно, дерево и так есть ациклический граф.

Задача 2.40. Нужно удалить минимум 6 ребер.

Задача 2.41. Нужно удалить минимум 7 ребер.

Задача 2.47. Суммарная степень 32, значит, в графе 16 ребер (рис. 7.2.3).

Задача 2.50. В графе 20 ребер, суммарная степень равна 40, значит, две вершины, степень которых не дана в условии, имеют степень ноль (рис. 7.2.4).

Задача 2.55. Диаметр равен 2.

Задача 2.56. Диаметр равен 2 или бесконечности.

Задача 2.57. Диаметр равен 1.

Задача 2.58. Диаметр равен 3.

Решение задачи 2.50 Задача 2.59. Диаметр равен бесконечности

Рис. 7.2.4. Решение задачи 2.50 Задача 2.59. Диаметр равен бесконечности.

Задача 2.60. Диаметр равен 2.

Задача 2.61. Диаметр равен 2.

Задача 2.65. Диаметр равен 5.

Задача 2.71. Диаметр равен 99.

Задача 2.74. Диаметр равен 74.

Задача 2.75. Диаметр равен 74.

Задача 2.76. Диаметр находится в интервале от 2 до 19 или равен бесконечности.

Задача 2.80. Диаметр находится в интервале от 1 до 18 или равен бесконечности.

Задача 2.87. Цикломатическое число равно 0.

Задача 2.88. Цикломатическое число равно 5.

Задача 2.89. Цикломатическое число равно 0.

Задача 2.90. Цикломатическое число равно 2.

Задача 2.91. Цикломатическое число равно 1.

Задача 2.92. Цикломатическое число равно а) 1; б) 0.

Задача 2.105. а) да, является; б) нет, не является.

Задача 2.109. Да, является.

Задача 2.113. Количество вершин должно быть нечетно.

Задача 2.114. В простых циклах на п вершинах, п> 2.

Задача 2.123.

  • а) да, является, гамильтонов цикл 1—4—2—5—3—6—1;
  • б) нет, не является, вершины 1, 2, 5, 6 имеют нечетную степень; чтобы граф стал эйлеровым, нужно удалить минимум два ребра, например (1, 5) и (2, 6).

Задача 2.131. Нет, не существует, так как 25-я вершина имеет степень 1, т.е. является висячей.

Задача 2.136. Число внешней вершинной устойчивости равно 11.

Задача 2.137. Число внешней вершинной устойчивости равно 2.

Задача 2.138. Число внутренней вершинной устойчивости равно 1.

Задача 2.139. Число внутренней вершинной устойчивости равно 7.

Задача 2.140. Число внутренней вершинной устойчивости равно 3.

Задача 2.141. Число внутренней вершинной устойчивости равно 4.

Задача 2.142. Максимальное число внешней вершинной устойчивости указанного графа равно 2.

Задача 2.143. Минимальное число внешней вершинной устойчивости указанного графа равно 1.

Задача 2.144. Максимальное число внутренней вершинной устойчивости указанного графа равно 5.

Задача 2.145. Минимальное число внутренней вершинной устойчивости указанного графа равно 3.

Задача 2.146. У пустого графа на 15 вершинах.

Задача 2.154. Хроматическое число равно 2.

Задача 2.156. Хроматическое число равно 14.

Задача 2.157. Хроматическое число равно 13.

Задача 2.158. Хроматическое число равно 14.

Задача 2.160. Хроматическое число равно 2.

Задача 2.175. Хроматическое число равно 2.

Задача 2.176. Хроматическое число равно 9.

Задача 2.180. Хроматическое число равно 3.

Задача 2.183. Хроматическое число равно 9.

Задача 2.190. Хроматическое число равно 5 или 6. Задача 2.192. Хроматическое число равно 1, 2 или 3. Задача 2.193. Хроматическое число равно 2 или 3. Задача 2.198. Ответ представлен в табл. 7.2.1.

Таблица 7.2.1

Решение задачи 2.198

Графы

С.

С,

С2

С2

Сз

Сз

1-я операция

2-я операция

п

9

9

13

13

21

21

22

43

т

31

5

73

5

21

189

78

729

к

1

5

1

8

1

1

6

1

У

23

1

61

0

1

190

62

687

И

7

3

12

2

3

11

3

14

d

2

сю

2

сю

10

2

сю

2

Задача 2.208. Граф планарен, так как является деревом.

Задача 2.209. Граф планарен, так как является простым циклом на 20 вершинах.

Задача 2.210. Не является планарным, так как содержит К5. Задача 2.213. Не является планарным, так как содержит Х3 3.

 
< Пред   СОДЕРЖАНИЕ     След >