Задание 1 (вершины и рёбра) На рисунке (представьте граф) изображены 5 вершин: А, B, C, D, E. Ребра: А-В, А-C, B-C, C-D, D-E, C-E. а) Сколько всего рёбер в графе? б) Какая вершина имеет наибольшую степень (количество связей)? в) Существует ли путь из А в Е? Если да, запишите один из путей.

Решение:

Дан граф с вершинами A, B, C, D, E и рёбрами: A-B, A-C, B-C, C-D, D-E, C-E.

1. а) Количество рёбер: Подсчитаем все рёбра, указанные в условии: A-B, A-C, B-C, C-D, D-E, C-E. Всего 6 рёбер.
2. б) Вершина с наибольшей степенью: Подсчитаем степень каждой вершины (количество рёбер, выходящих из неё):
   • Степень вершины A: 2 (A-B, A-C)
   • Степень вершины B: 2 (B-A, B-C)
   • Степень вершины C: 4 (C-A, C-B, C-D, C-E)
   • Степень вершины D: 2 (D-C, D-E)
   • Степень вершины E: 2 (E-D, E-C)
   Наибольшую степень (4) имеет вершина C.
3. в) Путь из А в Е: Да, путь из вершины А в Е существует. Один из возможных путей: A → C → E.

Ответ: а) 6 рёбер; б) Вершина C; в) Да, например, A → C → E.