Вершина v называется достижимой из вершины u, если существует (u, v)-маршрут. Любая вершина считается достижимой из себя самой.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v1=vn+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется его длиной. Цикл длины 3 часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.
Маршрут – последовательность ребер, в которых каждые два соседних ребра имеют общую вершину.
Маршрут, в котором начало и конец совпадают – циклический.
Маршрут в неографе, в котором все ребра разные – цепь.
Маршрут в орграфе, в котором все дуги разные – путь.
Путь, в котором начало и конец совпадают – контур.
Цепь с неповторяющимися вершинами – простая.
Циклический маршрут называется циклом, если он цепь и простым циклом, если эта цепь простая.
Вершины связанные, если существует маршрут из одной вершины в другую.
Связанный граф – если все его вершины связаны. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.
Свойства маршрутов, цепей и циклов:
1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. В частности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.
2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
3) Всякая непростая (u, v)-цепь, может быть разбита на простую (u, v)-цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.
4) Для любых трех вершин u, w, v из существования (u, w)-цепи их и (w, v)-цепи, следует существование (u, v)-цепи. Причем может не существовать (u, v)-цепи, содержащей вершину w.
5) Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.
6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.
Если два графа изоморфны:
1) то они одного порядка;
2) у них одинаковое количество ребер;
3) для произвольного i,0?i?n-1, (n – порядок графов) количество вершин степени i, у обоих графов одинаковое;
4) у них совпадают обхваты;
5) у них одинаковое количество простых циклов минимальной длины (по количеству ребер).
Число ребер маршрута – его длина. Эйлеров цикл – цикл графа, содержащий все его ребра. Эйлеров граф – граф, имеющий Эйлеров цикл.
Теорема. Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2. Гамильтонов цикл – простой цикл, проходящий через все вершины.
ОРИЕНТИРОВАННЫЙ МАРШРУТ ДЛИНЫ k в орграфе из v в w в орграфе G=(V,E) – последовательность дуг вида (v,w1), (w1,w2), (w2,w3), …, (wk-1,w), т.е. конец каждой дуги, кроме последней, совпадает с началом следующей. Для упрощения маршрут удобно представлять последовательностью вершин, которые его представляют, однако следует помнить об одинаковом направлении дуг, входящих в маршрут: v, w1, w2, w3, …, wk-1,w.
ОРИЕНТИРОВАННАЯ ЦЕПЬ (ПУТЬ) – это ориентированный маршрут, в котором все дуги различны.
Маршрут называется ЦИКЛИЧЕСКИМ, если его начало и конец совпадают.
Циклический путь называется КОНТУРОМ.
Вершина w ДОСТИЖИМА из v, если существует (v,w) – путь. Орграф называется связным, если существуют пути для всех пар различных вершин графа. Матрица связи, связности, достижимости C=A(R*) определяется аналогично графам. Заметим, однако, что для орграфов отношение R* НЕ ЯВЛЯЕТСЯ ОТНОШЕНИЕМ ЭКВИВАЛЕНТНОСТИ на V и, следовательно, не осуществляет разбиения V!
Пусть «D – множество всех орграфов, а «G – множество всех графов.
Мы можем определить отображение «F: «D - «G следующим образом.
Пусть G=(V,E) in «D. Тогда множество вершин F(G) in «G совпадает с V, а множество дуг F(G) определяется применением следующих операций на E:
a) удаляются все петли из Е;
б) (v,w) заменяются на [v,w] для всех (v,w) in E.
Тогда F(G) является графом, СВЯЗАННЫМ с орграфом G.
Для орграфов понятие связности является более содержательным, чем для графов. Различают три важных типа связности орграфа:
а) G СИЛЬНО СВЯЗНЫЙ, если для каждой пары различных вершин v,w in V существует маршрут из v в w и обратно.
Б) G ОДНОСТОРОННЕ СВЯЗНЫЙ, если для каждой пары различных вершин v, w in V существует маршрут из v в w или обратно.
В) G СЛАБО СВЯЗНЫЙ, если граф F(G) связный;
Очевидно, что справедливо следование:
G сильно связный - G односторонне связный - G слабо связный.
В)+-v2-+ б)+-v2-+ а)+-v2-+
v1 v3 v1 v3 v1---- v3
В терминах матрицы связности C=A(R*) орграф G сильно связный тогда и только тогда, когда Cij=1 для всех I,j in Nn; G односторонне связный тогда и только тогда, когда Cij=1 или Cji=1 для всех I,j in Nn.
Утверждение
Орграф является сильносвязным тогда и только тогда, когда в нем есть остовный циклический маршрут.
Если G=(V,E) – орграф, то можно разбить V путем определения отношения эквивалентности RO следующим образом: vROw, если v=w или существуют маршруты из v в w и обратно. Если {Vi: I in Np} – разбиение V и {Ei: I in Np, а Ei=(Vi*Vi) П E} являются соответствующими множествами дуг, то подграфы Gi=(Vi,Ei), I in Np называются СИЛЬНО СВЯЗНЫМИ КОМПОНЕНТАМИ G.
Очевидно, что RO<=R* и A(RO) может быть определено из A(R*) как A(RO)ij=A(R*)ij & A(R*)ji (& - символ операции конъюнкции); граф G связный тогда и только тогда, когда G имеет только одну сильно связную компоненту, т.е. если p=1.
### v1------v2 |1 1 1 1| |1 0 0 0|
| | |0 1 1 0| |0 1 0 0|
| | A(R*)=|0 0 1 0| A(RO)=|0 0 1 0|
v v |0 0 1 1| |0 0 0 1|
v4------v3 p=4
Таким образом, Gi=({vi}, Ф), I in N4, являются сильно связными компонентами заданного графа.
Путь (ориентированная цепь), содержащий все дуги орграфа, называется эйлеровым. Связный орграф называется ЭЙЛЕРОВЫМ, если в нем есть замкнутый эйлеров путь.
Теорема. Связный орграф G содержит открытый эйлеров путь тогда и только тогда, когда в нем есть две такие вершины v1, v2, что
delta+(v1)=delta-(v1)+1, delta+(v2)=delta-(v2)-1, и
delta+(v)=delta-(v) для любой вершины v, отличной от v1 и v2.
Контур (замкнутый путь) орграфа G называется ГАМИЛЬТОНОВЫМ, если он содержит все вершины орграфа G. ГАМИЛЬТОНОВ ГРАФ – это орграф, имеющий гамильтонов контур.
Распознавание гамильтоновости орграфов и построение гамильтоновых контуров так же сложны, как и для неориентированных графов. Рассмотрим одно из достаточных условий гамильтоновости орграфа.
Теорема (Мейниэл, 1973). Пусть G – сильносвязный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары v и w его несовпадающих несмежных вершин справедливо неравенство
delta(v)+delta(w)>=2*n-1,
то в G есть гамильтонов контур.
Пусть G=(V,E) – АЦИКЛИЧЕСКИЙ ОРГРАФ. Вершину v in V называют ЛИСТОМ, если delta+(v)=0. Если (v,w) in E, то v является НЕПОСРЕДСТВЕННЫМ ПРЕДКОМ w, а w – НЕПОСРЕДСТВЕННЫМ ПОТОМКОМ v. Если существует маршрут из v в w, то говорят, что v является ПРЕДКОМ w, а w – ПОТОМКОМ v. Эти понятия не имеют смысла для графов, имеющих циклы, так как в этом случае вершины в цикле являлись бы потомками и предками самих себя!
+-------v1------+ v4
v2<-----------------v3----------->v5<---------v6
Из вершин v2, v4, v5 дуги не выходят (листья графа), v1 является предком v5, v5 является потомком v1 и прямым потомком v3 и т.д.
Существует тесная связь между ациклическими графами и частично упорядоченными отношениями. Частичные порядки будут основаны скорее на отношении <, чем на отношении <=, и, следовательно, являются нерефлексивными и транзитивными.
Утверждения:
а) Пусть G=(V,E) - а–иклический орграф и отношение < определяется следующим образом: v<w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
б) Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E={(v,w): v<w}, то пара G=(V,E) является ациклическим графом.
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э–о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного непосредственного предка. Корень соединяется с любой другой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО - э–о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ПОЛНЫМ, если каждая вершина, не являющаяся листом дерева, имеет ровно 2 непосредственных потомка. Очевидно обобщение на k-арное дерево.
УРОВЕНЬ ВЕРШИНЫ - м–ксимальная длина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ - д–ина пути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА - д–ина самого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
l<=k^d; d=log(k) l.
Планарность
Плоский граф - г–аф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - м–ожество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани - м–ожество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - в–утренние.
Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - ч–сло вершин,m - ч–сло ребер, f - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.