Маршрут (теорія графів)

Маршрут (англ. walk) в графі — скінченна або нескінченна послідовність ребер S = {…, e, e1, …, en,…} в якій кожні два сусідні ребра ei -1 і ei мають спільну вершину тобто

e0 = (v0, v1) (ребро e0 інцидентне вершинам v0, v1 )

e1 = (v1, v2)

e2 = (v2, v3)

.   .   .

en = (vn, vn+1). 

Маршрут називають скінченним якщо він має початкову і кінцеву вершину. Якщо маршрут має початкову вершину, але не має кінцевої (або навпаки), то його називають односторонньо-нескінченним. Якщо маршрут не має початкової і кінцевої вершин то його називають двосторонньо-нескінченними

Довжина маршруту дорівнює кількості ребер у ньому (причому кожне ребро вказується стільки разів, скільки воно зустрічається в даному маршруті).

Якщо S має початкову вершину v0 і кінцеву вершину vn, то записують 

S = S(v0, vn) (тобто S — маршрут довжини n, який з'єднує вершини v0 і vn).

Маршрут M називається ланцюгом, якщо кожне ребро зустрічається в ньому не більше одного разу, і простим ланцюгом, якщо будь-яка вершина, крім, можливо, початкової, зустрічається в ньому не більш як один раз.

Маршрут називають циклічним або замкнутим якщо v0 = vn

Джерела

  • Дискретний аналіз: Навч.-метод. посібник для самост. вивч. дисц. / О. Д. Шарапов, Д. Є. Семьонов, В. Д. Дербенцев. — К.: КНЕУ, 2002. — 126 с. ISBN 966—574–380–5
  • Дискретна математика: підручник для студ. вищих тех. навч. закладів / Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков; За ред. В. Є. Ходакова. — К. : Вища школа, 2002. — 288 с. ISBN 966-642-090-2
  • Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл. ISBN 966-552-201-9
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.