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

Решение:

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

а) Количество рёбер:

Перечислим все рёбра: А-В, А-C, B-C, C-D, D-E, C-E. Всего 6 рёбер.

б) Вершина с наибольшей степенью:

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

• Степень вершины А: 2 (рёбра А-В, А-C)


• Степень вершины В: 2 (рёбра А-В, B-C)


• Степень вершины C: 4 (рёбра А-C, B-C, C-D, C-E)


• Степень вершины D: 2 (рёбра C-D, D-E)


• Степень вершины E: 2 (рёбра D-E, C-E)

Наибольшую степень имеет вершина C (4 связи).

в) Существует ли путь из А в Е?

Да, существует. Путь — это последовательность вершин, соединённых рёбрами.

Один из возможных путей из А в Е:

• А → C → E

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