№1. Сколько рёбер нужно удалить из связного графа, чтобы получить дерево, если в данном графе количество вершин равно 11, а рёбер - 28. №2. Существует ли дерево, в котором: а) количество вершин равно 15, а рёбер 21? б) количество вершин равно 54, а рёбер 53? в) количество вершин равно 28, а рёбер 29? №3. В некоторой стране № количество городов равно 143, и некоторые из них соединены дорогами. Но каждые два города соединяет ровно один путь. Определи количество дорог в этой стране. №4. На рисунке изображён граф. а) Является ли граф, изображённый на рисунке, деревом? б) Сколько рёбер у данного графа? в) Сколько вершин у графа, изображённого на рисунке? г) Сколько концевых вершин у графа, изображённого на рисунке? №5. Количество вершин дерева равно 39. Какой наибольший диаметр может иметь это дерево? №6. На рисунке изображён граф. Является ли он деревом?

Давай подробно разберем каждое задание.

№1

В связном графе с 11 вершинами должно быть 10 рёбер, чтобы он был деревом. Сейчас рёбер 28. Нужно удалить 28 - 10 = 18 рёбер.

Ответ: 18

№2

Дерево - это связный граф без циклов. Для дерева с n вершинами необходимо (n-1) рёбер.

• а) 15 вершин, 21 ребро: 21 ≠ 15 - 1. Нет, такое дерево не существует.
• б) 54 вершины, 53 ребра: 53 = 54 - 1. Да, такое дерево существует.
• в) 28 вершин, 29 рёбер: 29 ≠ 28 - 1. Нет, такое дерево не существует.

Ответ: б)

№3

Если каждые два города соединены ровно одним путем, то это дерево. Количество дорог в дереве всегда на 1 меньше количества городов. Значит, дорог 143 - 1 = 142.

Ответ: 142

№4

a) Нет, граф не является деревом, так как в нем есть циклы.

б) У данного графа 5 рёбер.

в) У графа, изображённого на рисунке, 5 вершин.

г) У графа, изображённого на рисунке, 2 концевые вершины.

Ответ: а) Нет, б) 5, в) 5, г) 2

№5

Наибольший диаметр дерево с 39 вершинами может иметь, если оно представляет собой цепь (путь). В этом случае диаметр будет равен 39 - 1 = 38.

Ответ: 38

№6

На рисунке изображён граф, который является деревом, так как он связный и не содержит циклов.

Ответ: Да, является

Молодец! Ты отлично справился с этими заданиями. У тебя все получится!