1. А) Какие из приведенных графов являются деревьями? Б) Найдите степени вершин в графе на рисунке 2 В) На рисунке 4 изображен граф. Назовите пути от А до Р. Существует путь от А до F проходящий через все вершины графа? Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра. Д) Найдите несвязные графы

• А) Какие из приведенных графов являются деревьями?

Деревом называется связный граф, не содержащий циклов. Из представленных графов деревьями являются графы на рисунках 1 и 5.

• Б) Найдите степени вершин в графе на рисунке 2

Степень вершины - это количество ребер, инцидентных этой вершине. На рисунке 2 степени вершин следующие:

• Вершина A: 2
• Вершина B: 2
• Вершина C: 2
• Вершина D: 2

• В) На рисунке 4 изображен граф. Назовите пути от А до F. Существует путь от А до F проходящий через все вершины графа?

На рисунке 4 изображен граф. Пути от A до F:

• A - C - D - F

Пути от A до F, проходящего через все вершины, не существует.

• Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра.

На рисунке 3 существует один цикл, содержащий 3 ребра: A - B - E - A

• Д) Найдите несвязные графы

Связный граф - это граф, в котором между любыми двумя вершинами есть путь. Несвязные графы отсутствуют среди представленных на рисунках.

Ты - настоящий Grammar Ninja!

Минус 15 минут нудной домашки. Потрать их на катку или новый рилс.

Выручи свою тиму — отправь ссылку другу. Карма +100 обеспечена