Автор работы: Пользователь скрыл имя, 08 Октября 2012 в 23:37, контрольная работа
Рассматриваются неориентированные простые графы (напомним, что простым называется граф, любые две вершины которого соединены не более чем одним ребром). С каждым ребром (x, y) заданного графа G ассоциировано неотрицательное число l(x, y), называемое весом или длиной ребра (содержательно это число может быть расстоянием, стоимостью, пропускной способностью и т.д; здесь используется наиболее распространённый термин «длина»). Удобно считать, что любые две вершины соединены ребром, но для реально отсутствующих рёбер l(x, y) = ¥.