Маршруты в графавах

Пусть G -- мульти- или псевдограф. Последовательность вершин и рёбер вида:

такая, что - ребро в графе G, соединяющее vi c vi+1 называется . Вершина v1 при этом называется началом маршрута, а vn+1 – концом маршрута. Число рёбер n в маршруте называется длиной маршрута. Во взвешенном графе за длину маршрута принимается сумма весов входящих в маршрут рёбер.

В простом графе, когда смежные вершины соединены только одним ребром, для задания маршрута достаточно указать только последовательность вершин (разумеется, любые две соседние вершины в этой последовательности должны быть смежными). В этом случае (v1, v n+1) – маршрут обозначается: (v1, v2, v3, …, vn+1).

В маршруте вершины и рёбра могут повторяться. Если в маршруте все рёбра различны, то он называется цепью. Если кроме того в цепи различны и все вершины (кроме, может быть, первой и последней), то такой маршрут называется простой цепью.

Маршрут называется циклическим, если в нём начало совпадает с концом. Циклический маршрут являющийся цепью называется циклом, а являющийся простой цепью -- простым циклом.

Минимальная из длин всех циклов графа называется охватом графа.

Граф G называется связным, если в нем для любых двух вершин u и υ существует (u,υ)-маршрут.

В ориентированных графах рассматриваются ориентированные маршруты, в которых для любой пары соседних вершин υi и υi+1 существует дуга (υi, υi+1) (υi – начало дуги, υi+1 – конец). Другими словами – это маршруты, по которым можно передвигаться от начала маршрута к концу с соблюдением ориентации (стрелок).

56. Матрица смежности и матрица инцидентности.

57. Алгоритмы обхода графа в ширину и глубину.

58. Алгоритм Дейкстры.