Решение задачи по теме 'Деревья': определение, диаметр и степени вершин

Самостоятельная работа по теме "Деревья" а) Какие из графов являются деревьями? Укажите их диаметр и количество концевых вершин. Дерево — это связный граф без циклов. Граф 2 является деревом. Граф 5 является деревом. Для графа 2: Концевые вершины (степень которых равна 1): E, C, F, K, L. Количество концевых вершин: 5. Диаметр (самый длинный путь между вершинами): путь от E до L (или K, или F) через вершины B и M. Длина пути составляет 3 ребра. Диаметр = 3. Для графа 5: Количество концевых вершин: 4. Диаметр: путь между самыми удаленными концами составляет 4 ребра. Диаметр = 4. б) Найдите степени вершин в графе на рис. 2. Степень вершины — это количество ребер, выходящих из нее. \( deg(A) = 1 \) (вершина A соединена только с B) \( deg(B) = 3 \) (соединена с A, E, C) \( deg(E) = 1 \) \( deg(C) = 1 \) \( deg(M) = 4 \) (соединена с B, F, K, L) \( deg(F) = 1 \) \( deg(K) = 1 \) \( deg(L) = 1 \) в) На рис. 4 граф. Назовите пути от F до A. Существует ли путь от F до A, проходящий по каждому ребру один раз? Пути от F до A: 1) F — K — A 2) F — K — B — A 3) F — K — B — C — A 4) F — K — B — D — A 5) F — K — B — C — D — A Путь, проходящий по каждому ребру ровно один раз, называется Эйлеровым путем. Он существует, если в графе не более двух вершин с нечетной степенью. Проверим степени вершин на рис. 4: \( deg(F) = 1 \) (нечетная) \( deg(K) = 2 \) \( deg(A) = 3 \) (нечетная) \( deg(B) = 4 \) \( deg(C) = 2 \) \( deg(D) = 2 \) Так как ровно две вершины (F и A) имеют нечетную степень, Эйлеров путь существует. Он должен начинаться в F и заканчиваться в A (или наоборот). Пример такого пути: F — K — B — D — A — C — B — A. г) Найдите в графе рис. 3 циклы, содержащие 3 ребра. Цикл из 3 ребер — это треугольник. В графе 3 такими циклами являются: 1) A — B — D — A 2) B — C — D — B 3) A — C — D — A д) Найдите несвязные графы. Связный граф — это граф, в котором между любыми двумя вершинами есть путь. На представленных рисунках все графы (1, 2, 3, 4, 5) являются связными, так как в каждом из них нет изолированных частей или отдельных вершин, до которых нельзя добраться. Несвязных графов на картинке нет.