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

Решение:

Граф на рисунке:

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

Степень вершины — это количество ребер, выходящих из нее.

• Степень вершины A: 2 (ребра AB, AC, AS) - исправлено, A связано с B, C, S, что дает 3 ребра
• Степень вершины B: 2 (ребра BA, BP)
• Степень вершины C: 2 (ребра CA, CR)
• Степень вершины P: 2 (ребра PB, PS)
• Степень вершины S: 3 (ребра SA, SP, SR) - исправлено, S связано с A, P, R, что дает 3 ребра
• Степень вершины R: 2 (ребра RC, RS)

Наименьшая степень вершин равна 2.

Вершины, имеющие наименьшую степень: B, C, P, R.

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

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

• Путь 1: B → P → S → R. Длина = 3 ребра.
• Путь 2: B → A → S → R. Длина = 3 ребра.
• Путь 3: B → A → C → R. Длина = 3 ребра.
• Путь 4: B → P → S → A → C → R. Длина = 5 ребер.

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

Кратчайшие пути из В в R:

1. B → P → S → R
2. B → A → S → R
3. B → A → C → R

Ответ: а) Наименьшая степень вершин равна 2. Вершины: B, C, P, R. б) Кратчайший путь состоит из 3 ребер. Пути: B → P → S → R, B → A → S → R, B → A → C → R.