Графы

курсовая работа

1.1 Основные определения

Пусть V -- конечное непустое множество, V2 -- его декартов квадрат. Ориентированный граф (орграф) -- это пара (V, А), где A V2. Элементы множества V называются вершинами орграфа G=(V, А), а элементы множества А -- его дугами. Таким образом, дуга -- это упорядоченная пара вершин. Множества вершин и дуг орграфа G обозначаются через VG и AG соответственно. Число |VG| называется порядком орграфа G и обозначается через |G|.

Если х = (u, v) -- дуга, то вершины u и v называются ее концевыми вершинами, причем u называется началом дуги х, а. v -- концом. Говорят, что дуга инцидентна каждой из своих концевых вершин. Говорят также, что дуга исходит из своего начала и заходит в свой конец. Дуга с совпадающими началом и концом, т. е. дуга вида (v, v), называется петлей. Можно определить ориентированные графы с несколькими дугами, имеющими общее начало и общий конец (мультиграфы). Такие дуги называются параллельными.

На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Направление линии обозначается стрелкой. Например, для графа G, представленного на рис. 1, VG={v1, v2, v3, v4, v5}, AG= {x1, x2, x3, x4, x5, x6, x7}, причем x1 и x2 --параллельные дуги, a x7 -- петля.

Вершины орграфа называются смежными, если они являются концевыми для некоторой дуги. Дуги называются смежными, если они имеют общую концевую вершину.

Пусть G-- некоторый орграф. Ориентированным маршрутом (или просто маршрутом) в графе G называется такая последовательность

S = (v0, x1, v1, x2, v2, x3, v3, x4,.., vn, xn,) (1)

его чередующихся вершин vi и дуг хj, что xi = (vi-1, vi) (i = 1, n). Такой маршрут назовем (v0, vn) - маршрутом. Вершины v0 и vn назовем крайними, а остальные вершины маршрута (1) -- промежуточными (внутренними). Длиной маршрута называется число входящих в пего дуг. Маршрут называется цепью, если все входящие в пего дуги различны, и путем, если все входящие в него вершины, кроме, возможно, крайних, различны.

Если в орграфе G нет параллельных дуг, то маршрут (1) может быть задан последовательностью входящих в него вершин: S=( v0, v1, v2, v3,.., vn). В любом случае маршрут можно задать последовательностью входящих в него дуг:

S = (x1, x2, x3, x4,.., xn,)

Маршрут называется циклическим, если его первая и последняя вершины совпадают. Циклический путь называется контуром. Очевидно, что любой (u, v) - маршрут при u v содержит (u, v)-путь, а при u = v -- контур.

Последовательность (1) чередующихся вершин и дуг орграфа G, таких что xi = (vi-1, vi) или xi = (vi, vi-1), называется полумаршрутом. Аналогично определяются полуцепь, полупуть и полуконтур.

Если в орграфе существует (u, v) -маршрут, то говорят, что вершина v достижима из вершины u. Любая вершина считается достижимой из себя самой.

Орграф называется сильным (или силъносвязным), если любые две его вершины достижимы друг из друга. Орграф называется односторонним (или односторонне-связным), если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабым (слабосвязным, связным), если любые две его вершины соединены полупутем.

Поскольку любая вершина графа достижима из себя, то одновершинный граф одновременно и сильный, и односторонний, и слабый.

Очевидно, что каждый сильный граф является односторонним, а каждый односторонний -- слабым. Очевидно также, что любые две несовпадающие вершины сильного орграфа принадлежат некоторому циклическому маршруту.

На рис. 2, а изображен сильный орграф, на рис. 2, б -- односторонний, а на рис. 2, в -- слабый.

Маршрут, содержащий все вершины орграфа G, называется остовным.

Утверждение 1. Орграф является сильным тогда и только тогда, когда в нем есть остовный циклический маршрут.

Необходимость. Пусть G -- сильный орграф и T = (v0, x1, v1, x2, v2,.., xn, v0)--его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G -- сильный орграф, то существуют маршруты

T1 = (v0, y1, .., v), T2 = (v0, z1, .., v0)

Но тогда циклический маршрут

T = (v0, x1, v1, .., xn, v0, y1, .., v, .., z1, v0)

содержит большее, чем Т, число вершин, что противоречит выбору маршрута Т. Следовательно, Т -- остовный маршрут.

Достаточность. Пусть u и v -- две произвольные вершины орграфа G, а

T = (v0, x, .., v, y, .., v, .., z,.., v0)

циклический маршрут. Тогда u достижима из v с помощью маршрута (v, у, ..., u)--части маршрута Т, -- а v из u -- с помощью маршрута (u, z, ..., v0, х, ..., v).

Аналогично доказывается

Утверждение 2. Орграф является односторонним тогда и только тогда, когда в нем есть остовный маршрут. Орграф является слабым тогда и только тогда, когда в нем есть остовный полумаршрут.

Подграфы и порожденные подграфы ориентированного графа определяются так же, как и для неориентированного. Так же определяются и операции над орграфами.

Введем важное понятие сильной компоненты орграфа. Сильной (или силъносвязной) компонентой ориентированного графа называется любой его максимальный относительно включения сильный подграф.

Очевидно, что отношение взаимной достижимости вершин ориентированного графа G рефлексивно, симметрично и транзитивно. Следовательно, мы получим разбиение множества VG на классы, объединив в один класс все вершины, достижимые друг из друга. Подграфы, порожденные классами этого разбиения, и только они, служат сильными компонентами орграфа G.

В орграфе могут быть дуги, не входящие ни в одну из его сильных компонент.

Орграф G, изображенный на рис. 3, имеет четыре сильные компоненты с множествами вершин {v1, v2, v3, v4}, {v5, v6, v8}, {v7} и {v9}.

Пусть {S1, S2, ..., Sm} -- множество всех сильных компонент ориентированного графа G. Конденсацией орграфа G называется орграф G*, вершины s1, s2, ..., sm которого соответствуют сильным компонентам орграфа G, и пара (si, sj) является дугой в G* тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте Si а конец -- Sj.

На рис. 3 представлены орграф G и его конденсация G*.

Утверждение 3. Конденсация G* любого орграфа G не имеет контуров.

Проведем доказательство от противного. Пусть Т = (s0, x1, s1, …, s0) -- контур в G*. Тогда каждая вершина, входящая в компоненту Si, достижима из любой вершины, входящей в компоненту Sj. Но это противоречит максимальности сильных компонент.

Неориентированный мультиграф, получающийся в результате снятия ориентации с дуг орграфа G, называется основанием орграфа G и обозначается через Gb.

Очевидно, что орграф является слабым тогда и только тогда, когда его основание -- связный мультиграф.

Орграф называется несвязным, если его основание -- несвязный мультиграф.

Ориентированный граф называется турниром, если его основание является полным графом. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимыми по круговой системе. Результаты встреч можно описать ориентированным графом, вершины которого соответствуют участникам соревнований, а дуга (u, v) есть в орграфе, если участник u победил участника v.

Делись добром ;)