Задание 4 Параграф 1.3 ГДЗ Босова 9 класс 2017 (Информатика)

Граф – графическое изображение связей между объектами. Объекты изображаются вершинами, обычно изображаемые кругами, связи между ними линиями, которые называются ребрами, если они без стрелки, или дугой, если линия со стрелкой.

Граф — это графическое изображение связей между объектами. Объекты изображаются вершинами, а связи между ними — рёбрами.

На рисунке вершины графа: $$A, B, C, D, E.$$

Рёбра графа: $$AB, BC, CD, DE, EA, CE.$$

Примеры цепей в этом графе: $$ABCE, AECB, ABCDE, AEDCB, CED, DCE, ECD.$$

Примеры циклов: $$ABCEA, AECBA, ABCDEA, AEDCBA, CEDC, DCED, ECDE.$$

Найдём длины кратчайших путей между наиболее удалёнными пунктами. По рисунку веса рёбер такие:

$$AB=50,\quad BC=90,\quad CD=80,\quad DE=70,\quad EA=90,\quad CE=60.$$

Проверим самые длинные кратчайшие пути. Между $$B$$ и $$D$$ возможны пути:

• $$B \to C \to D: 90+80=170$$
• $$B \to C \to E \to D: 90+60+70=220$$
• $$B \to A \to E \to D: 50+90+70=210$$

Кратчайший из них равен $$170$$. Это и есть наибольшее значение среди кратчайших путей между всеми парами пунктов.

Ответ

Граф — это графическое изображение связей между объектами. Вершины: $$A, B, C, D, E$$. Рёбра: $$AB, BC, CD, DE, EA, CE$$. Примеры цепей: $$ABCE, ABCDE, CED$$. Примеры циклов: $$ABCEA, ABCDEA, CEDC$$. Наиболее удалены пункты $$B$$ и $$D$$, длина кратчайшего пути между ними равна $$170$$.