Реферат: Орграфы, теория и применение

Вершина 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, и