Ответ:
Решение:
- 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. Д) Найдите несвязные графы.
Несвязных графов среди представленных нет. Все графы являются связными.
Решение:
- 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. Д) Найдите несвязные графы.
Несвязных графов среди представленных нет. Все графы являются связными.
