Маршруты, цепи, циклы, компоненты
Чередующаяся последовательность вершин и ребер графа:
v1, e1, v2, e2, …, vn, en, vn+1
такая, что ребро ei = (vi, vi+1) называется маршрутом , соединяющим вершины v1, и vn+1 (или (v1, vn+1)-маршрутом). Маршрут можно задать последовательностью его вершин: v1, v2, …, vn, vn+1, а также последовательностью ребер: e1, e2, …, en. Например, на рис. 5.1 маршрут (1, 2, 3, 4, 5, 3, 8, 9) соединяет вершины 1 и 9 .
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Граф порядка n, являющийся простой цепью, часто обозначают Pn .
Цепь, у которой крайние вершины совпадают, называется циклом, а циклическая простая цепь - простым циклом.
Число ребер маршрута называется длиной маршрута. Длина всякого цикла графа не меньше трех. Цикл длины три обычно называют треугольником. Любой маршрут графа можно рассматривать как его подграф.
На рис.5.1 цепи (1, 2, 3, 8) и (2, 3, 4) - простые, (1, 2, 3, 4, 5, 3, 6, 7, 3, 8) - цепь, не являющаяся простой, маршрут (2, 3, 4, 5, 3, 2) не является цепью, цепь (3, 4, 5, 3) - простой цикл (треугольник).
Выбросив из (u,v)-маршрута, не являющегося цепью, все циклы, получим простую (u,v)-цепь, поэтому верно
Утверждение 5.1. При u ¹ v всякий (u,v)-маршрут содержит простую (u,v)-цепь.
Аналогично получается
Утверждение 5.2. Всякий цикл содержит простой цикл
Например, на рис.5.1 цикл (3, 4, 5, 3, 6, 7, 3) состоит из двух треугольников.
Очевидно также следующее утверждение:
Утверждение 5.3. Объединение двух несовпадающих простых (u,v)-цепей содержит простой цикл.
Утверждение 5.4. Если С и D - два несовпадающих простых цикла, имеющих общее ребро e, то граф (C È D)-e содержит простой цикл.
Доказательство: если e = (u,v), то C-e и D-e - две несовпадающие (u,v)-цепи, поэтому утверждение 5.4 следует из предыдущего.
Утверждение 5.5. Длина простой цепи Pn равна n-1.
Этот факт легко доказывается индукцией по n.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом и несвязным в противном случае. Учитывая утверждение 5.1, можно в этом определении заменить слово маршрут цепью или простой цепью.
Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G, а множество вершин компоненты -областью связности графа. На рис. 5.2 несвязный граф состоит из двух компонент.
Его области связности: A = { 1, 2, 3, 4} и B = {5, 6, 7, 8, 9}.
Остовный подграф графа с теми же областями связности но без циклов называется остовом (или каркасом) графа. Остовы помеченного графа отличаются составом ребер. На рисунке (5.3) приведены два различных остова предыдущего графа.
В 1897 году английский математик А. Кэли доказал теорему:
Теорема Кэли. Число остовов полного помеченного графа Kn порядка n равно nn-2.
При n = 3 теорема очевидна. На рис. 5.4 изображен граф K3 и три его остова.
