3.2.2 Задание ориентированных графов

Матрица смежностей по вершинам строится в основном так же, как и для неориентированного графа. Размерность матрицы - m × m, где m – количество вершин графа. Значения элементов матрицы определяются следующим образом: R_ij – количество ребер, соединяющих i-ю вершину с j-й (т.е. направленных из i-й вершины в j-ю).

Матрица инцидентностей – матрица размерностью m × n, где m – количество вершин, n – количество ребер графа (как и для неориентированного графа). Значения элементов матрицы определяются следующим образом: S_ij = -1, если j-е ребро заходит в i-ю вершину; S_ij = 1, если j-е ребро выходит из i-й вершины; S_ij = 0, если i-я вершина и j-е ребро не инцидентны. Если j-е ребро - петля при i-й вершине, то обычно указывается S_ij = 1.

Аналитическое задание графа – его представление в виде отношения. Область задания отношения – множество вершин графа. Если i-я и j-я вершины смежны (имеется ребро из i-й вершины в j-ю), то i-я и j-я вершины находятся в заданном отношении, т.е. в нем указывается пара (i, j).

Примечание – Аналитическое задание, строго говоря, невозможно для графов с кратными ребрами (например, для графа, приведенного на рисунке 3.4), так как в этом случае в отношении, описывающем граф, пришлось бы указывать одинаковые элементы – пары вершин.

Пример 3.2 – Задать в матричной форме граф, приведенный на рисунке 3.4.

Построим матрицу смежностей по вершинам. Ее размерность – 4 × 4, так как у графа четыре вершины. Матрица имеет следующий вид:

.

Построим матрицу инцидентностей. Ее размерность – 4 × 8, так как у графа четыре вершины и восемь ребер. Матрица имеет следующий вид:

.

Пример 3.3 – Задать граф, приведенный на рисунке 3.2, аналитически.

Как указано выше, аналитическое задание графа – это его представление в виде отношения. Область задания отношения (множество вершин) в данном случае следующая: X = {1, 2, 3, 4}. Собственно отношение (т.е. множество пар смежных вершин) имеет следующий вид: G = {(1, 2), (2, 3), (2, 4), (3, 4), (4, 3), (1, 4)}.

Рекомендуется самостоятельно построить для этого графа матрицу смежностей по вершинам и матрицу инцидентностей.

3.3 Пример решения задачи с использованием графов: упорядочение комплекса задач

Рассмотрим пример практической задачи, решаемой с использованием графов.

Постановка задачи. Пусть в некоторой системе обработки данных требуется решить несколько задач. При этом задачи связаны друг с другом: решение одних задач представляет собой подготовку данных для других задач (или, другими словами, некоторые задачи можно решать только после того, как решены некоторые другие задачи). Требуется разбить комплекс задач на группы по порядку их решения, т.е. выделить группу задач, которые можно решать в первую очередь, затем – группу задач, которые можно решать после задач первой группы, и т.д.

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

Пример 3.4 – Пусть некоторый комплекс задач описан графом, приведенным на рисунке 3.5.

Рисунок 3.5 – Описание комплекса задач в виде графа

Здесь имеется девять задач. Чтобы решить задачу 2, необходимо сначала решить задачу 1; чтобы решить задачу 4, необходимо решить задачи 2 и 3, и т.д. Требуется разбить задачи на группы.

Для этого построим для графа, описывающего комплекс задач, матрицу смежностей по вершинам:

На первом шаге вычисляются суммы столбцов матрицы. Здесь сумма j-го столбца – количество ребер, входящих в j-ю вершину (или, в данном случае, количество задач, непосредственно предшествующих j-й задаче). Если сумма j-го столбца оказывается равной нулю, значит, j-й задаче не предшествуют другие задачи, и она относится к первой группе задач (т.е. задач, решаемых в первую очередь).

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

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

Процесс продолжается, пока не будут разбиты на группы все задачи (или, другими словами, пока не будет вычеркнута вся матрица).

Процесс решения для рассматриваемого примера показан в таблице 3.1.

Таблица 3.1 – Разбиение комплекса задач на группы (пример 3.4)

Шаг (номер группы задач)	Суммы столбцов									Задачи, включенные в группу
	1	2	3	4	5	6	7	8	9
1	0	1	0	2	1	1	2	1	2	1, 3
2	–	0	–	1	1	1	2	0	2	2, 8
3	–	–	–	0	1	1	1	–	1	4
4	–	–	–	–	0	1	0	–	0	5, 7, 9
5	–	–	–	–	–	0	–	–	–	6

Здесь, например, в исходной матрице смежностей по вершинам нулю равны суммы первого и третьего столбцов. Значит, задачи 1 и 3 относятся к первой группе задач: для их решения не требуется решать какие-либо другие задачи (это легко видеть и из графа, приведенного на рисунке 3.5). Из матрицы смежностей по вершинам необходимо исключить первую и третью строку, а также первый и третий столбец. В сокращенной матрице нулю равны суммы второго и восьмого столбцов. Значит, вторую группу образуют задачи 2 и 8: эти задачи следует решать после задач 1 и 3. Аналогичный смысл имеют три другие группы задач.

На рисунке 3.6 приведен упорядоченный граф, иллюстрирующий разбиение задач на группы.

Рисунок 3.6 – Описание комплекса задач в виде упорядоченного графа

Примечание – Если на некотором шаге разбиения комплекса задач на группы оказывается, что ни одна из сумм столбцов не равна нулю, это означает, что в описании связей между задачами (и в графе, описывающем эти связи) допущена ошибка: некоторые задачи образуют замкнутый контур. Например, указано, что для решения j-й задачи необходимо решить i-ю, для решения k-й задачи – j-ю, но при этом для решения i-й задачи необходимо решить k-ю. В этом случае необходимо проанализировать и уточнить постановки рассматриваемых задач и связи между ними.