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

Решение:

Граф:

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

• Наибольшая степень вершин в данном графе равна 4.
• Вершины, имеющие наибольшую степень: C и E.

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

• Кратчайший путь в данном графе имеет длину 2 ребра.
• Существует два кратчайших пути из вершины А в вершину В:
  • Путь 1: A → E → B
  • Путь 2: A → C → B

Ответ:

а) Наибольшая степень равна 4. Вершины: C, E.

б) Существует 2 кратчайших пути: A → E → B и A → C → B.