|
Маршрут (теорія графів)Маршрут (англ. 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 Джерела
|