2. Графы (2 балла) На рисунке изображён граф связей между населёнными пунктами А, В, С, D, Е. Вес ребра — расстояние в км. (Представьте граф: А—В: 5 км; А—С: 8 км; В—С: 3 км; В—D: 6 км; С—Е: 4 км, Д—Е: 7 км.) а) Нарисуйте граф (можно схематично). 6) Найдите кратчайший путь из А в Е. Запишите последовательность вершин и длину пути. в) Есть ли в графе цикл? Если да, укажите его.

Решение:

1. Схематичное изображение графа:

   Представим граф, где вершины - населенные пункты, а ребра - дороги с указанием расстояния:

   Вершины: А, В, С, D, Е

   Ребра:

   • (А, В) - 5 км
   • (А, С) - 8 км
   • (В, С) - 3 км
   • (В, D) - 6 км
   • (С, Е) - 4 км
   • (D, Е) - 7 км

   (Без возможности нарисовать здесь граф, это описание того, как он будет выглядеть.)

2. Кратчайший путь из А в Е:

   Проанализируем все возможные пути из А в Е:

   • А → В → С → Е: 5 + 3 + 4 = 12 км
   • А → С → Е: 8 + 4 = 12 км
   • А → В → D → Е: 5 + 6 + 7 = 18 км

   Сравнивая длины путей, находим кратчайший.

3. Наличие цикла:

   Цикл в графе – это путь, который начинается и заканчивается в одной и той же вершине, проходя через другие вершины.

   Рассмотрим вершины и соединения:

   • Путь В → С → В имеет длину 3 + 3 = 6 км. Это цикл.
   • Путь А → В → С → А имеет длину 5 + 3 + 8 = 16 км. Это цикл.

Ответ:

• а) Граф схематично изображен в описании выше.
• б) Кратчайший путь из А в Е: А → В → С → Е или А → С → Е. Длина пути: 12 км.
• в) Да, в графе есть циклы, например: В → С → В.