Тема 4. Ориентированные графы

4.1. Основные положения

Начало теории графов было положено Л. Эйлером в 1736 году. Как самостоятельная дисциплина теория графов сформировалась в 30 годах ХХ века. Особенно широко применяется в планировании производства и транспорта

Традиционно граф изображается в виде набора вершин (обозначается кружочками); определенные пары вершин соединяются линиями со стрелками или без них.

Пример. Необходимо отобразить транспортную сеть, соединяющую пассажирские пункты. Населенные пункты обозначены вершинами Е_i, i=1…n, пусть n=6.

 

 

Рис.1                                            Рис.2

 

 

Конечным графом - называется пара (E, l), где Е – непустое множество элементов (вершин), а l – конечное (возможно и пустое) множество элементов Е (дуг и ребер). Граф записывается G=(E, l).

 

 

Дугой - называется ориентированная пара (E_i, E_j) вершин графа E_i  и E_j, причем E_i – начальная вершина дуги, а E_j – конечная.                                     

                             

Петлей - называется дуга вида (E_i, E_i)

                             

Кратные дуги – дуги, у которых совпадают начальные и конечные вершины.

Обозначение дуг в виде одной буквы с индексом е_j или буквы с двумя индексами

е_ij                                                  е_ji

Ребром – называется неориентированная пара (E_i, E_j) вершин E_i  и E_j графа. Обозначения е или (E_i, E_j).

Смежные ребра – имеющие общую вершину.

Граф - называется ориентированным или орграфом, если связи между его вершинами заданы дугами (рис. 2).

Неориентированным или реберным, если связи заданы ребрами.

Смешанный граф, если и дуги и ребра (рис. 1).

Путем - называется конечная последовательность дуг, в которой начало каждой следующей дуги совпадает с концом предыдущей (1,2). (2,5). (5,4), (4,8); что можно записать в виде последовательности вершин (1,2,5,4,8).

Контуром – называется путь, начальная вершина которого совпадает с конечным

(1,3). (3,5). (5,1).

Длина пути определяется числом входящих в него дуг.

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

Циклом – называется цепь, в которой начальная вершина совпадает с конечной.

 

 

4.2. Матричное представление графов.

Существуют три способа матричного представления графа:

· матрица смежности вершин;

· матрица смежности дуг

· матрица инциденций.

Матрицей смежности вершин орграфа – называется квадратная матрица А, каждый элемент которой а_ij равен количеству дуг приходящих от вершины Е_i к вершине Е_j. Будем рассматривать орграфы с дугами кратности – 1, поэтому матрица состоит из «нулей» и «единиц»

                                              

 

 

 

           

Вершина i	Вершина j
	1	2	3	4	5
1	0	0	1	1	0
2	0	0	0	1	0
3	1	0	0	0	1
4	0	1	0	0	1
5	0	0	0	0	0

 

Матрица смежности дуг орграфа – называется квадратная матрица А, каждый элемент которой а_ij, равен «1», если конечная вершина дуги е_i является начальной вершиной дуги е_j и «0» в других случаях.

Дуга еi	Дуга еj
	е1	е2	е3	е4	е5	е6	е7
е1	0	1	1	0	0	0	0
е2	1	0	0	0	0	0	0
е3	0	0	0	0	1	1	0
е4	0	0	0	0	1	1	0
е5	0	0	0	1	0	0	0
е6	0	0	0	0	0	0	1
е7	1	0	0	0	0	0	0

 

Матрицей инциденций орграфа – прямоугольная матрица А, строки которой соответствуют вершинам, а столбцы – дугам. Элементы матрицы а_ij равны «1», если Е_i начальная вершина дуги е_j, «-1» если Е_i конечная вершина дуги е_j.

 

Вершина Еi	Дуга еj
	е1	е2	е3	е4	е5	е6	е7
Е1	-1	1	1	0	0	0	0
Е2	0	0	0	1	-1	0	0
Е3	1	-1	0	0	0	0	-1
Е4	0	0	-1	-1	1	0	0
Е5	0	0	0	0	0	-1	1