Пример.

Способы задания орграфов.

Решение.

Поставим командам в соответствие вершины, соответствующий условию задачи ориентированный граф имеет вид: : X выиграла у Y.

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

Определение 36. Изолированной вершиной ориентированного графа называется вершина, у которой и степень входа и степень выхода равны нулю. Источником называется вершина, степень выхода которой положительна, а степень входа равна нулю. Стоком называется вершина, степень входа которой положительна, а степень выхода равна нулю.

Определение 37. Вершина А и ребро (дуга) u называются инцидентными, если ребро заходит в эту вершину или исходит из нее.

1. Перечислением дуг (или ребер) графа с указанием концов и добавлением списка изолированных вершин.

2. Заданием множества его вершин V и способа отображения Г множества V в V, таким образом, орграф G есть пара (V, Г), например, орграф, заданный следующим образом Гх₁ = х₁, Гх₂ = , Гх₃ = , Гх₄ = изображается в виде:

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

4. Заданием матрицы инциденций (инцидентности) графа с m вершинами и n ребрами. Это прямоугольная матрица , строки которой соответствуют вершинам графа, а столбцы – ребрам. Если x_i является началом дуги u_j, то ; если x_j – конец дуги u_j, то . Петле соответствует элемент, равный 2.

Ориентированный граф определяется следующим образом: Гх₁ = х₁, Гх₂ = , Гх₃ = , Гх₄ = , Гх₅ = х₄, Гх₆ = х₇, Гх₇ = . Записать матрицу смежности и матрицу инциденций.