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

Решение:

а) Определим степени всех вершин:

• deg(A) = 3 (соединения с D, E, F)
• deg(D) = 2 (соединения с A, C)
• deg(C) = 4 (соединения с D, E, B, F)
• deg(E) = 3 (соединения с A, C, F)
• deg(F) = 3 (соединения с A, C, E)
• deg(B) = 2 (соединения с C, F)

Наибольшая степень равна 4. Вершина с наибольшей степенью — C.

б) Кратчайший путь из А в В:

Путь 1: A → F → B. Длина = 2.

Путь 2: A → F → C → B. Длина = 3.

Путь 3: A → E → C → B. Длина = 3.

Путь 4: A → E → F → B. Длина = 3.

Путь 5: A → C → B. Длина = 2.

Путь 6: A → C → F → B. Длина = 3.

Кратчайший путь имеет длину 2. Таких путей два: A → F → B и A → C → B.

Ответ: а) Наибольшая степень равна 4. Вершина: C. б) Два кратчайших пути: A-F-B и A-C-B.