Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Определения

Пусть G — неориентированный граф . Путём в G называется такая конечная или бесконечная последовательность рёбер и вершин ${\displaystyle S=(...,a_{0},E_{0},a_{1},E_{1},...,E_{n-1},a_{n},...)}$ ,

что каждые два соседних ребра ${\displaystyle E_{i-1}}$ и ${\displaystyle E_{i}}$ имеют общую вершину ${\displaystyle a_{i}}$ .

Таким образом, можно написать ${\displaystyle ...,E_{0}=(a_{0},a_{1}),E_{1}=(a_{1},a_{2}),...,E_{n}=(a_{n},a_{n+1}),...}$

Отметим, что одно и то же ребро может встречаться в пути несколько раз. Если нет рёбер, предшествующих ${\displaystyle E_{0}}$ , то ${\displaystyle a_{0}}$ называется начальной вершиной S, а если нет рёбер, следующих за ${\displaystyle E_{(n-1)}}$ , то ${\displaystyle a_{n}}$ называется конечной вершиной S. Любая вершина, принадлежащая двум соседним рёбрам, называется внутренней . Так как рёбра и вершины в пути могут повторяться, внутренняя вершина может оказаться начальной или конечной вершиной.

Если начальная и конечная вершины совпадают, путь называется циклическим . Путь называется цепью , а циклический путь — циклом , если каждое его ребро встречается не более одного раза (вершины могут повторяться). Нециклическая цепь называется простой цепью , если в ней никакая вершина не повторяется. Цикл с концом ${\displaystyle a_{0}}$ называется простым циклом , если ${\displaystyle a_{0}}$ не является в нём промежуточной вершиной и никакие другие вершины не повторяются.

К сожалению, эта терминология не вполне устоялась. Уилсон писал:

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

Цепь называют путём, полупростым путём; простую цепь – цепью, путём, дугой, простым путём, элементарной цепью; замкнутую цепь – циклической цепью, контуром; цикл – контуром, контурной цепью, простым циклом, элементарным циклом.

—

Пути, цепи и циклы являются фундаментальными концепциями теории графов и определяются во вводной части большинства книг по теории графов. Смотрите, например, Бонди и Марти , Гиббонс или Дистель .

Различные виды путей

Путь, для которого никакие рёбра графа не соединяют две вершины пути, называется .

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

Простой цикл, содержащий все вершины графа без повторений, известен как Гамильтонов цикл .

Цикл, получаемый добавлением ребра графа к остовному дереву исходного графа, известен как Фундаментальный цикл.

Свойства путей

Два пути вершинно независимы , если они не имеют общих внутренних вершин. Аналогично два пути рёберно независимы , если они не имеют общих внутренних рёбер.

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

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

Примечания

См. также

Литература

• Харари Ф. Теория графов. — М. : УРСС , 2003. — 300 с. — ISBN 5-354-00301-6 .
• Оре, Ойстин . Теория графов. — М. : УРСС , 2008. — 352 с. — ISBN 978-5-397-00044-4 .
• Н. Кристофидес. Теория графов. Алгоритмический подход. — 2-е.. — М. : Издательство «Мир», 1978.
• Р. Уилсон. Введение в теорию графов. — М. : Издательство «Мир», 1977. — (Современная математика. Вводные курсы).
• J.A. Bondy, U.S.R. Murty. . — North Holland, 1976. — С. 12—21. — ISBN 0-444-19451-7 .
• Рейнгард Дистель. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-X .
• Gibbons, A. Algorithmic Graph Theory. — Cambridge University Press, 1985. — С. 5—6. — ISBN 0-521-28881-9 .
• Bernhard Korte, László Lovász, Hans Jürgen Prömel Alexander Schrijver. Paths, Flows, and VLSI-Layout. — Algorithms and Combinatorics 9, Springer-Verlag, 1990. — ISBN 0-387-52685-4 .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .