Дана схема дорог. Найти кратчайшее расстояние из А в Е На рисунке изображены графы. Назовите те из них, которые: а) являются связными; б) не являются связными.

Задание про схему дорог

Кратчайшее расстояние из А в Е можно найти, рассмотрев все возможные пути и выбрав самый короткий. Пути из А в Е: 1. \( A \to B \to E = 100 + 400 = 500 \) 2. \( A \to C \to E = 260 + 100 = 360 \) 3. \( A \to B \to C \to E = 100 + 240 + 340 = 680 \) 4. \( A \to C \to D \to E = 260 + 310 + 350 = 920 \) 5. \( A \to C \to E = 260 + 360 + 350 = 970 \) Кратчайший путь: \( A \to C \to E = 360 \)

Задание про графы

а) Связные графы:

• 1) Все вершины соединены, граф связный.
• 2) Все вершины соединены, граф связный.
• 5) Все вершины соединены, граф связный.
• 6) Все вершины соединены, граф связный.

б) Несвязные графы:

• 3) Граф состоит из двух несвязных частей.
• 4) Граф состоит из двух несвязных частей.

Проверка за 10 секунд: Убедись, что в связных графах можно добраться от любой вершины до любой другой, а в несвязных - нет.

Доп. профит (База): Связность графа - одно из базовых понятий теории графов, которое используется в самых разных областях, от проектирования сетей до анализа социальных связей.