5. На рисунке изображен граф. а) Чему равна наибольшая из степеней его вершин? Выпишите вершины, которые имеют наибольшую степень. б) Сколько кратчайших путей ведет из вершины А в вершину В? Запишите данный путь.

Решение:

На рисунке изображен неориентированный граф.

1. Наибольшая степень вершин:
   • deg(A) = 2 (соединения с D, E)
   • deg(D) = 2 (соединения с A, C)
   • deg(C) = 3 (соединения с D, E, B)
   • deg(E) = 3 (соединения с A, C, F)
   • deg(F) = 2 (соединения с E, B)
   • deg(B) = 2 (соединения с F, C)
   Наибольшая степень равна 3. Вершины с наибольшей степенью: C, E.
2. Кратчайшие пути из А в В:
   • Путь 1: A → E → F → B (длина 3)
   • Путь 2: A → C → B (длина 2)
   • Путь 3: A → E → C → B (длина 3)
   Самый короткий путь имеет длину 2. Существует 1 кратчайший путь из вершины А в вершину В.

Ответ: а) Наибольшая степень равна 3. Вершины: C, E. б) 1 кратчайший путь: A → C → B.