Практическая работа №12. Маршруты связных графов, оценка по их цене (расстоянию)

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Две вершины графа называются связными, если существует соединяющая их простая цепь. В противном случае две вершины называются не связными. 
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Число вершин графа G = (S,U) называется его порядком.
Ребра вида (x, x) называются петлями.
Вершина графа называется висячей, а если ее степень равна единице.
Вершина графа называется изолированной, если ее степень равна нулю.
Конечным графом (finite graph)  называется граф, в котором множества  и  — конечны. 
Матрица смежности. Это матрица n×n, где n - число вершин, где b_ij = 1, если существует ребро, идущее из вершины х в вершину у и b_ij = 0 в противном случае.
Дерево — это связный граф без циклов.
Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.


Маршруты в неориентированных графах
Маршрут неориентированного графа G=(V,E) – чередующаяся, конечная последовательность вершин и рёбер такая, что начинается и заканчивается вершиной и каждое ребро в маршруте соединяет две вершины маршрута – предыдущую и последующую.
Обозначения или или , -маршрут.
Концевые (терминальные) вершины маршрута – v0 и vn, внутренние – все остальные вершины.
Замкнутый маршрут – концевые вершины совпадают , иначе – открытый .