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

Решение: А) Деревьями являются графы на рисунках 3 и 5. Дерево — это связный граф без циклов. Б) Степени вершин на рисунке 1: - A: 1 - B: 2 - C: 2 - D: 3 - E: 2 - F: 1 - K: 1 - L: 1 - M: 1 В) Пути от A до F на рисунке 4: - A-B-C-F - A-D-C-F Путь от А до F, проходящий через все вершины графа, отсутствует. Г) Циклы на рисунке 3, содержащие 3 ребра: - A-B-D-A - B-C-D-B Д) Несвязные графы отсутствуют среди представленных. Несвязный граф - это граф, который состоит из двух или более компонент связности, то есть вершины графа нельзя разбить на две группы, где нет ребер между этими группами.