Лекция -21. Ориентированные графы. Матрица смежности для орграфа. Маршруты цепи, циклы в орграфах

Лекция -21. Ориентированные графы. Матрица смежности для орграфа. Маршруты цепи, циклы в орграфах.


Определение. Множество точек соединенных между собой дугами называется ориентированным графом

4

5

3

2

1

22

2

Способы задания:

1. 
   Аналитически:
   

2. 
   Графически
   
3. 
   Матрицы смежности:
   

	1	2	3	4	5
1	0	1	1	0	0
2	0	0	1	1	0
3	0	0	0	1	0
4	0	1	0	1	0
5	0	0	0	1	0

Всякий орграф можно представить матрицей смежности, при этом первым элементам пар, обозначающих дуги, соответствуют строки матрицы, вторым элементам – столбцы.

Определение. Заменим в орграфе все дуги ребрами, получим граф, который называется основанием данного орграфа.
Определение. Два орграфа изоморфны, если изоморфны их основания и совпадают направления всех соответствующих дуг.
Например, графы, приведенные на рисунках , не являются изоморфными, поскольку дуги, соединяющие вершины 2 и 3, направлены в противоположные стороны.

Орграф может содержать и кратные дуги. Пример такого графа приведен на рисунке. Его матрица смежности изображена матрицей.

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

Если в орграфе 2 вершины соединены парой встречных дуг, то их можно заменить одним неориентированным ребром.
Определение. Граф, содержащий ребра и дуги, называется смешанным.

Степени вершин

Определение. Степенью входа вершины называют число входящих в нее дуг, а степенью выхода число выходных дуг.






Маршруты, цепи, циклы в орграфах определяется также, как и в случае неориентированных графов, однако в орграфах существует понятие достижимости.
Определение. Вершина называется достижимой из вершины , если существует маршрут ведущие из вершины до вершины (существует направление стрелок от к ).
Маршрут называется ориентированной цепью, если в ней нет повторяющихся дуг. Орцепь называется простой, если в ней нет повторяющихся вершин.
Связность орграфа.Эйлеровы цепи и циклы в орграфе.

Орграф на n вершинах называется сильно связанным, если существует простая орцепь соединяющая любые две вершины. Орграф называется слабо связанным, если его основание является связанным.

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


Полный орграф


Определение. Орграф называется полным, если его основание есть полный граф.
Определение. Орграф без петель называется полным, если каждая пара его вершин соединена точно одной дугой. Полный орграф называют также турниром
В случае неориентированных графов для всякого n существует единственный полный граф(n — число вершин). Для турниров верным является другое утверждение: если n — число вершин, то существует S полных орграфов:




Из последней формулы следует, что число полных орграфов быстро растет с увеличением числа n
Например:
■ если n = 2, то S = 2; ■ если n = 3, то S = 8;
■ если n = 4, то S = 64; ■ если n = 5, то S = 1024, и т. д.

Приведем несколько теорем о полных орграфах.

Теорема 1. Во всяком полном орграфе имеется простая цепь, проходящая через все вершины орграфа.
Теорема 2. Всякий полный сильно связанный орграф является гамильтоновым.
Теорема 3. Всякий полный орграф является полугамильтоновым.