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

Краткое пояснение:

Пошаговое решение:

Граф 5:

а) Наименьшая степень вершин:

• Вершина R: соединена с C и S. Степень R = 2.
• Вершина S: соединена с R, P и A. Степень S = 3.
• Вершина P: соединена с S и B. Степень P = 2.
• Вершина C: соединена с R и A. Степень C = 2.
• Вершина A: соединена с S, C и B. Степень A = 3.
• Вершина B: соединена с P и A. Степень B = 2.

Наименьшая степень вершин равна 2. Вершины с наименьшей степенью: R, P, C, B.

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

Для нахождения кратчайшего пути, рассмотрим все возможные пути из R в P:

• R → S → P (длина 2)
• R → C → A → S → P (длина 4)
• R → C → A → B → P (длина 4)

Кратчайший путь имеет длину 2.

Ответ:

• а) Наименьшая степень вершин равна 2. Вершины: R, P, C, B.
• б) Существует 1 кратчайший путь из R в P. Путь: R → S → P.