Путь (теория графов)

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Путь (в графе)»)
Перейти к: навигация, поиск
Граф-путь с 6 вершинами

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

Определения[править | править вики-текст]

Пусть G - неориентированный граф. Путём в G называется такая конечная или бесконечная последовательность рёбер и вершин[1] S = (..., a_0,E_0, a_1, E_1, ..., E_{n-1}, a_n, ...),

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

Таким образом, можно написать ..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...

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

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

К сожалению, эта терминология не устоялась. Уилсон[2] пишет: «То, что мы назвали маршрутом, называют также путём, рёберной последовательностью. Цепь называют путём, полупростым путём; простую цепь – цепью, путём, дугой, простым путём, элементарной цепью; замкнутую цепь – циклической цепью, контуром; цикл – контуром, контурной цепью, простым циклом, элементарным циклом.»[3][4][5]

Ориентированный цикл. Без стрелок это просто цикл. Это не простой цикл, поскольку синие вершины используются дважды.

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

Различные виды путей[править | править вики-текст]

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

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

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

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

Свойства путей[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  1. Оре, 2008, 2.1 Маршруты, цепи и простые цепи, с. 34-38
  2. Уилсон, 1977, Новые определения, с. 37
  3. Харари, 2003, Маршруты и связность, с. 232
  4. Харари, 2003, Орграфы и соединимость., с. 232
  5. Кристофидес, 1978, Глава 1. Введение 2. Пути и маршруты, с. 13

Смотрите также[править | править вики-текст]

Ссылки[править | править вики-текст]

  • Харари Ф. Теория графов. — М.: УРСС, 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 Graph Theory with Applications. — North Holland, 1976. — С. 12–21. — ISBN 0-444-19451-7.
  • Рейнгард Дистель . — Новосибирск: Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-Х.
  • 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.

Внешние ссылки[править | править вики-текст]