Маршрут () в графі — скінченна або нескінченна послідовність ребер S = {…, e, e1, …, en,…} в якій кожні два сусідні ребра ei -1 і ei мають спільну вершину тобто
e0 = (v0, v1) (ребро e0 інцидентне вершинам v0, v1 )
e1 = (v1, v2)
e2 = (v2, v3)
. . .
en = (vn, vn+1).
Маршрут називають скінченним якщо він має початкову і кінцеву вершину. Якщо маршрут має початкову вершину, але не має кінцевої (або навпаки), то його називають односторонньо-нескінченним. Якщо маршрут не має початкової та кінцевої вершин, то його називають двосторонньо-нескінченними.
Маршрут M називається ланцюгом, якщо кожне ребро зустрічається в ньому не більше одного разу, і простим ланцюгом, якщо будь-яка вершина, крім, можливо, початкової, зустрічається в ньому не більш як один раз.
Маршрут називають циклічним або замкнутим якщо v0 = vn.
Довжина маршруту дорівнює кількості ребер у ньому (причому кожне ребро вказується стільки разів, скільки воно зустрічається в даному маршруті).
Якщо S має початкову вершину v0 і кінцеву вершину vn, то записують
S = S(v0, vn) (тобто S — маршрут довжини n, який з'єднує вершини v0 і vn).
Приклад
Прикладом простого ланцюга може слугувати граф об’єктів структури Організації Об'єднаних Націй, вектори якого відбивають вертикальну субординацію та горизонтальну нумерацію. Ієрархічна структура представляється у вигляді дерева рішень або графа знань . Об’єкти структури позначені маршрутами.
Маршрут Назва <span style='color: '> ^ Структура Організації Об'єднаних Націй <span style='color: blue'> ^A Генеральна Асамблея <span style='color: Orange'> ^AA Шість головних комітетів <span style='color: MediumVioletRed'> ^AAA Займається питаннями роззброєння, глобальної безпеки та пов'язаними з ними міжнародними питаннями. <span style='color: MediumVioletRed'> ^AAB Зосереджується на економічних та фінансових питаннях. <span style='color: MediumVioletRed'> ^AAC Вирішує соціальні, гуманітарні та культурні питання. <span style='color: MediumVioletRed'> ^AAD Вирішує спеціальні політичні питання та питання деколонізації. <span style='color: MediumVioletRed'> ^AAE Керує адміністративними та бюджетними справами ООН. <span style='color: MediumVioletRed'> ^AAF Основний форум для міжнародно-правових питань. <span style='color: Orange'> ^AB Два ключові комітети <span style='color: MediumVioletRed'> ^ABA Генеральний комітет: Складається з Президента Асамблеї, віце-президентів та голів Головних комітетів. <span style='color: MediumVioletRed'> ^ABB Асамблея може створювати інші необхідні комітети. <span style='color: blue'> ^B Рада Безпеки <span style='color: blue'> ^C Економічна та Соціальна Рада <span style='color: blue'>^D Рада з опіки <span style='color: blue'>^E Міжнародний Суд <span style='color: blue'>^F Секретаріат В структуру ООН входять шість об’єктів першого рівня ієрархії: ^A, ^B, ^C, ^D, ^E, ^F. Причому дочірні об’єкти має лише Генеральна Асамблея з маршрутом ^A: ^AA Шість головних комітетів та ^AB два ключові комітети, які знаходяться на третьому рівні ієрархії. Маршрут вказує положення кожного об'єкта на графі.
Довжина маршруту дорівнює кількості векторів (ребер) у даному маршруті. Отже, маршрут від корінного об'єкта до об'єкта ^AAF "Основний форум для міжнародно-правових питань" складається з 8 векторів.
Крім того, існує простий арифметичний спосіб. Довжина маршруту до об’єкта дорівнює сумі номерів букв . Тобто, сума букв в маршруті ^AAF дорівнює:
S=A+A+F.
Перетворюючи їх на номери букв в алфавіті:
S=1+1+6;
Отримуємо тій самий результат:
S=8.
Тобто, довжина маршруту знаходиться через арифметичну операцію на графі.
Примітки
Джерела
Дискретний аналіз: Навч.-метод. посібник для самост. вивч. дисц. / О. Д. Шарапов, Д. Є. Семьонов, В. Д. Дербенцев. — К.: КНЕУ, 2002. — 126 с. ISBN 966—574–380–5