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

Решение:

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

  Деревьями являются графы на рисунках 1, 3, 4, 5. Дерево — это связный граф без циклов.

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

  Степень вершины — это количество рёбер, инцидентных данной вершине.

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

  Пути от А до F:

  • A-B-F
  • A-D-F

  Пути от А до Е, проходящего через все вершины графа, не существует. Чтобы пройти через все вершины, нужно было бы вернуться обратно, что нарушило бы условие простого пути.

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

  В графе на рисунке 3 циклов, содержащих ровно 3 ребра, нет. Все циклы здесь содержат 4 ребра (например, A-B-C-D-A).

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

  Несвязных графов среди представленных нет. Все графы являются связными.