Графы и ориентированные графы

Пусть D = (V, A) – орграф

Пусть G = (V, E) – граф

Путь в D – последовательность вершин и дуг u₁, a₁, u₂, a₂,..., u_t, a_t, u_t+1 , где t0, причем каждая вершина u_i  V, а каждая дуга a_i  A, и a_i всегда является дугой (u_i, u_i+1). Путь обычно записывается последовательностью вершин u₁, u₂, ..., u_t, u_t+1.

Цепь в G – последовательность вершин и ребер u₁, e₁, u₂, e₂,..., u_t, e_t, u_t+1, где t0, причем каждая вершина u_i  V, а каждое ребро e_i  E, и e_i всегда является ребром (u_i, u_i+1). Цепь обычно записывается последовательностью вершин u₁, u₂, ..., u_t, u_t+1. Цепь = маршрут без повторений (каждое ребро проходится лишь один раз).

Полупуть в D – последовательность вершин и дуг u₁, a₁, u₂, a₂,..., u_t, a_t, u_t+1, где t0, причем каждая вершина u_i  V, а каждая дуга a_i  A, и a_i всегда является либо дугой (u_i, u_i+1), либо дугой (u_i+1, u_i). Полупуть также обычно записывается последовательностью вершин u₁, u₂, ..., u_t, u_t+1.

Аналогия — та же цепь

(см. выше)

В определении полуцепи нет смысла — полуцепь всегда совпадает с соответствующей цепью.

Полный путь или полный полупуть в D – путь или полупуть, проходящий через все вершины D.

Полная цепь или полная полуцепь в G – цепь или полуцепь, проходящая через все вершины G.

Простым путем или простым полупутем в D называется путь или полупуть без повторяющихся вершин.

Простой цепью в G называется цепь без повторяющихся вершин.

Замкнутым путем или полупутем в D называется путь или полупуть u₁, a₁, u₂, a₂,..., u_t, a_t, u_t+1, в котором u_t+1=u₁.

Замкнутой цепью в G называется цепь u₁, u₂, ..., u_t, u_t+1, в которой u_t+1=u₁.

Полный замкнутый путь или полный замкнутый полупуть в D – полный путь или полный полупуть, который замкнут.

Полная замкнутая цепь в G – полная цепь, которая замкнута.

Контуром в D называется замкнутый путь u₁, u₂, ..., u_t, u₁, в котором все вершины различны.

Циклом в G называется замкнутая цепь u₁, e₁, u₂, e₂,..., u_t, e_t, u₁ , в которой все вершины различны.

Полуконтуром в D называется замкнутый полупуть, u₁, a₁, u₂, a₂,..., u_t, a_t, u₁, в котором все вершины u₁, u₂, ..., u_t и все дуги a₁, a₂,..., a_t различны.

Аналогия — тот же цикл

(см. выше)

В определении полуцикла нет смысла — полуцикл всегда совпадает с соответствующим циклом.

Вершина u_i, достижима из вершины u_j, если имеется путь из u_i в u_j.

Вершина u_i, достижима из вершины u_j, если имеется соединяющая их цепь.

Вершины u_i и u_j соединимы, если имеется путь из вершины u_i в вершину u_j или из вершины u_j в вершину u_i.

Вершины u_i и u_j соединимы, если имеется соединяющая их цепь.

Длиной пути, полупути, простого пути, простого полупути, контура или полуконтура называется число дуг, содержащихся в них.

Длиной цепи, простой цепи или цикла называется число ребер, содержащихся в них.

Расстояние d(u_i, u_j) от вершины u_i и до вершины u_j в D равно длине кратчайшего пути из u_i в u_j или не определено, если путь из u_i в u_j отсутствует.

Во взвешенном графе длиной и расстоянием обычно называют  с учетом веса ( весов).

Расстояние d(u_i, u_j) от вершины u_i и до вершины u_j в G равно длине кратчайшей цепи между u_i и u_j или не определено, если цепь между ними отсутствует.