 |
|
АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология |
МАРШРУТЫ, ЦЕПИ И ЦИКЛЫ.
В этой главе будут рассмотрены такие свойства графов, которые не меняются при произвольной ориентации звеньев графа, переориентации или дезориентации дуг (всех или некоторых). Мы рассмотрим такие свойства графов общего вида L = (X, U; P), которые полностью определяются в терминах полуинцидентора P' и не требуют знания самого инцидентора P. Условимся в следующем: обозначение некоторой вершины графа L через xi не обязывает нас считать индекс i номером этой вершины в множестве X, когда последнее упорядоченно посредством нумерации его элементов; xi xj не обязательно различны при i ¹ j. Аналогичные соглашения примем по отношению к символам вида Ui, обозначающим ребра. Конечная последовательность: М = x0 u1 x1 u2 x2 u3...xk-1 uk xk (k>=0) элементов графа L, для которой истинно высказывание: P'(x0,u1,x1) & P'(x1,u2,x2) &... & P'(xk-1,uk,xk), называется маршрутом из вершины x0 в вершину xk, или маршрутом, соединяющим x0 c xk; в случае x0=xk имеем циклический маршрут при вершине x0, или цикл. Число k носит название длинны маршрута. Иными словами, длина маршрута равняется числу ребер, входящих в него. Заметим, что маршрут - это не просто часть графа, ибо порядок его обхода играет существенную роль; так, маршрут: М1 = xk uk xk-1... x2 u2 x1 u1 x0 при k>=0 не совпадает с написанным выше маршрутом М, хотя и состоит из тех же самых элементов и с тем же отношением инцидентности. Маршрут: М = x0 u1 x1 u2 x2 u3...xk-1 uk xk называется цепью, если ребра u1, u2,...,uk различны (при k<=1 это условие выполнено "в силу ложности посылки"). Цепь в случае, если x0=xk при k>= 1 называется циклом. Цепь называется простой, если все её вершины xp, xk,...,xk различны. В случае, когда x0=xk & k>=1 имеем простой цикл, который, будучи цепью, в то же время не есть простая цепь. Цепь, в которой начальная и конечная вершины не совпадают, но есть повторяющиеся вершины, называется циклической. ЛЕММА. Всякий маршрут (в частности, всякая цепь) графа содержит хотя бы одну простую цепь, соединяющую ту же пару вершин. Всякий циклический маршрут нечетной длины содержит простой цикл нечетной длины. Всякий цикл содержит простой цикл. СЛЕДСТВИЕ: Всякий кратчайший маршрут между двумя заданными вершинами графа есть простая цепь. Всякий цикл наименьшей длины при заданной вершине является простым. 5. ОПРЕДЕЛЕНИЕ ЧИСЛА МАРШРУТОВ ДЛИНЫ "L" НА ГРАФЕ. МАРШРУТОМ в графе G=(X,U) называется конечная последовательность вершин и ребер вида ¾ S=(x0, u1, x1, u2, x2,..., xk-1, uk, xk), где x0,xk - соответственно начальная и конечная вершины маршрута S. Очевидно, - в конечном графе G можно выделить только конечное число маршрутов. Число ребер в маршруте S называется его длиной. Для определения маршрутов длины q графа G его матрицу смежности R возводят в q-ю степень. ПРИМЕР: Дана матрица смежности R графа G =(X,U) (рисунок 4):
Рисунок 4. R
Возведем матрицу R в квадрат: R2
Каждый ri,j-й элемент матрицы R2 равен числу маршрутов длиной 2, ведущих из вершины xi в xj. Например, r3,2 = 2 означает, что в графе два маршрута длины L=2, ведущих из x3 в x2 : - S1=(x3, x1), (x1, x2) и S2=(x3, x4),(x4, x2). ПРИМЕЧАНИЕ. Дата добавления: 2015-09-27 | Просмотры: 967 | Нарушение авторских прав |
