Что такое граф? Что является вершинами и рёбрами графа на рис. 2.10, в? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами. На рис. 2.10, в вершины A, B, C, D, E соединены рёбрами AB — 50, BC — 90, CD — 80, DE — 70, EA — 90 и CE — 60.
По определению §
Цепь, например, A–B–C–D: по ней можно пройти последовательно через четыре вершины. Цикл A–B–C–E–A возвращается в исходную вершину; ещё один цикл — C–D–E–C.
Сравним длины кратчайших путей, складывая веса пройденных рёбер. От A до D путь A–E–D имеет длину
Вершины — пункты A, B, C, D, E; рёбра — соединения между ними. Пример цепи: A–B–C–D; пример цикла: A–B–C–E–A. Наиболее удалены B и D; кратчайший путь B–C–D имеет длину
