Реферат: Орграфы, теория и применение
Вершина 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.
ОРИЕНТИРОВАННАЯ ЦЕПЬ (ПУТЬ) – это ориентированный маршрут, в котором все дуги различны.
Маршрут называется ЦИКЛИЧЕСКИМ, если его начало и конец совпадают.