Пример.

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

Решение.

Решение.

2. Проводится круговой турнир по баскетболу между командами A, B, C, D, E. Каждая команда играет с каждой командой по одному разу. Требуется изобразить итоги турнира: В выиграла все встречи, С проиграла все, А выиграла у С и D и проиграла у В и D.

Поставим командам в соответствие вершины, соответствующий условию задачи ориентированный граф имеет вид: : 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 (в некоторых источниках, равный 0).

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