Маршрут walk. Определения

Рассмотрим встречающиеся в интернете содержательные, слегка формальные определения маршрута, а потом дадим естественное определение маршрута:-)

Сначала идут определения "класса" вар-1 (см. страницу выше). Неверные определения в заголовке оканчиваются на (-), верные - на (+), стоящие особняком - (0).

ru.wikipedia(-)

Начнём с критики определения ru.wikipedia "Маршрут в графе — это чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента инцидентны."

а) Видно что заданы две последовательности: вершин от 0 до k и дуг от 1 до k. Можно сделать вывод что k>0. Итак непосредственно в определении маршрут есть две последовательности с согласованными длинами, что даёт возможность устроить из них чередующуюся последовательность.

б) идентификаторы v0, e1... в определении лишние т.к. в нём не используются и похожи на классическое наукообразие;-) Более того их запись содержит в неявной форме важное свойство чередующейся последовательности: она начинается и заканчивается вершинами:-) В оправдание скажем что обозначения v0, e1... используются для дальнейших определений.

Более важно то что

в) требования инцидентности двух соседних членов в чередующейся последовательности не достаточно для непрерывности!

А именно, рассмотрим графы Г1, Г2

Контр-пример в Г1. Будет ли в0, р1, в0 маршрутом на Г1? По идее - нет! Но требование инцидентности соблюдено!

Контр-пример в Г2. Рассмотрим последовательность: в0, р1, в1, р2, в1, р1, в1, р2, в2. Это также инцидентный не маршрут!

Итак это определение не верно.

ГСиА(-)

Определение [ГСиА] с.16. "Маршрут в графе G=(V,E) представляет собой конечную чередующуюся последовательность вершин и рёбер v0, e1, v1, e2,..., vk-1, ek, vk, начинающуюся и кончающуюся на вершинах, причём vi-1 и vi являются концевыми вершинами ребра ei, 1≤i≤k."

В определении не сказано что vi-1 и vi составляют все концевые вершины так что определение не верно.

В том числе в английской версии другой их книги [GTaA], p.7:

вершин и ребер графа такая, что ."

Здесь формулой записано ЛКМ1 и определение верно.

KR-2013(-)

KR-2013. p.6: "A walk in the graph G = (V, E) is a finite sequence of the form vi0, ej1, vi1, ej2, . . . , ejk, vik, which consists of alternating vertices and edges of G. The walk starts at a vertex. Vertices vit−1 and vit are end vertices of ejt (t = 1, . . . , k)."

На картинке видна двойная индексация:

Предложение "Vertices vit−1 and vit are end vertices of ejt (t = 1, . . . , k)." понимается так: vit−1 есть концевая вершина ejt и vit есть концевая вершина ejt но не обязательно что vit−1 и vit дают полный состав концевых вершин ejt!

Например, если у ejt концевых вершин две, а мы выбрали vit = vit−1.

И так и это определение не верно.

Немного ещё об определении Keijo Ruohonen [KR-2013]:

- технически двойной индекс нужен только если есть глобальная индексация вершин и рёбер, тогда нам нужны последовательности индексов.

- у него есть маршрут 0-длины (просто вершина), т.е. k может быть = 0!!! Впрочем из фигуры последовательности так не скажешь;-)

wikip-eng(-)

- wikip-eng "A walk is a sequence of vertices and edges, where each edge's endpoints are the preceding and following vertices in the sequence."

Короткое, содержательное и почти верное определение - автор забыл добавить alternating! И, например, v1, v2, e1, v2 подходит, но не маршрутом не является;-)

Правильно:

A walk is a sequence of alternating vertices and edges, where each edge's endpoints are the preceding and following vertices in the sequence.

Этот пример интересен тем что не использует "наукообразие", а лишь силу ЕЯ!

То что walk начинается и заканчивается на вершины следует из того что у каждой дуги есть предыдущая и последующая вершины;-)

Замечание. 07.07.2015, часов в 11 мск, определение было исправлено. Будем посмотреть:-)

wiki-book(0)

Особняком стоит определение, назовём его вар-2:

-wiki-book "A u-v walk is defined as a sequence of vertices starting at u and ending at v, where consecutive vertices in the sequence are adjacent vertices in the graph"

Эта формулировка есть в [ГСиА] с.16. НО вар-2 не считается в [ГСиА] определением - там сказано тоньше: “маршрут можно рассматривать как последовательность вершин”;-)

Ясно что вар-1 и вар-2 не эквивалентны, т.к. вар-1 говорит какие дуги надо выбрать для прохода (а их может быть несколько)!

НО абстрагирование до вершин может быть практично - какие там дуги не важно!!!

Сводка

По сути мы имеем 3 определения маршрута:

- не верное: ru.wikipedia и аналогичные. Они считают что инцидентности соседей достаточно.

- верное: Nsk и исправленное wikip-eng. Они понимают что состав соседей дуги важен.

- абстрактное - wiki-book. Оно абстрагируется от дуг которые надо пройти на пути от от u к v.

Конечно для "формалиста" ошибка в базовом определении говорит что им авторы не пользуются:-)

Естественное определение маршрута

Итак мы начинаем с некоторой вершины и должны сделать некоторое (конечное) число шагов по дугам. Поэтому естественно задавать маршрут указанием стартовой вершины и последовательности дуг по которым от неё надо пройти: начни с вершины v1, пройди от неё по дуге e1, далее по дуге e2…

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

(вар-0) Маршрут есть пара: вершина v1 (стартовая) и последовательность дуг (e1...), таких что

а1) каждая дуга кроме последней имеет со следующей по крайней мере одну общую вершину.

б) для каждой дуги, имеющей две соседних, эти соседние должны быть инцидентны всем её концевым вершинам.

в1) v1 инцидентна e1.

в2) если e1 ребро, то его вторая вершина (не v1) должна быть инцидентна e2.

Замечание. в2) нужно из-за контр-примера:

2do. Доказать что вар-0 эквивалентен вар-1!