Степени ориентированных графов

В ориентированном графе существуют такие понятия, как по­лустепени исхода и захода.

Полустепенью исхода m'(х) называется число дуг, выхо­дящих из вершины х. Полустепень захода m"(х) – число дуг, входящих в вершину х. Петли считают по одному разу в каждой из полустепе­ней.

Аналогом кратности неориентированных ребер m(x_i,x_j) в ори­ентированном графе являются две кратности: m'(x_i, x_j) – число дуг, направленных от x_i к x_j, m"(x_i,x_j) – число дуг, направленных от x_j к x_i.

Таким образом:

m'(x_i, x_j) = m"(x_j, x_i).

Число дуг, выходящих из вершины x_i, определится суммой

а число дуг, входящих в вершину х_i равно

Отсюда общее число дуг графа:

Если все полустепени m'(x) и m"(x) равны для всех х Î X, то ориентированный граф G(X) называется однородным графом степени m_n.

Рис. 3.28. Однородные ориентированные графы

Для такого графа m = m_n х n, где n число вершин графа G(X). Примеры однородных ориентированных графов приве­дены на рис. 3.28.