АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример 7. Последовательности дуг:

Последовательности дуг:

1) а₆, а₅, а₉, а₈, а₄,

2) а₁, а₆, а₅, а₉

3) а₁, а₆, а₅, а₉, а₁₀, а₆, а₄

являются путями.

Маршрут в ориентированном графе – это неориентированный двойник пути; рассматривается только в том случае, когда направленностью дуг в графе можно пренебречь.

Длиной (или мощностью) пути m называется число дуг, входящих в него. При рассмотрении пути m на графе с взвешенными дугами, представленного последовательностью дуг (а₁, а₂,... а_q) за его вес (или стоимость) принимается число l(m), равное сумме весов всех дуг, входящих в m, т.е.

l (m) = åc_ij, где (x_i, x_j)Îm

§ 2.7.2. Цепи, орцепи, простые цепи и простые орцепи.

Цепью называется такой маршрут, в котором каждое ребро используется не более одного раза.

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

Так, 1-й и 2-й пути из примера 7, являются орцепями, а 3-й – нет, т. к. дуга а₆ в ней используется дважды.

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

Очевидно, что простая орцепь является также и орцепью. Обратное утверждение неверно.

Так в примере 7, путь 1 является орцепью, но не простой орцепью, путь 2 является орцепью и простой орцепью, путь 3 не является ни орцепью, ни простой орцепью.

§ 2.7.3. Циклы, орциклы, простые циклы, простые орциклы (контуры).

Замкнутая цепь называется циклом. Особое значение имеет Эйлеров цикл. Это цикл, который проходит ровно один раз по каждому ребру неориентированного графа. Не все графы имеют Эйлеров цикл.

Аналогично предыдущему определению, замкнутая орцепь называется орциклом.

Замкнутая простая цепь (орцепь) называется простым циклом (орциклом). Простые орциклы называются ещё контурами.

Дата добавления: 2015-09-27 | Просмотры: 418 | Нарушение авторских прав