6 Докажите свойство степеней вершин ориентированного графа: в ориентированном графе сумма исходящих степеней вершин равна сумме входящих степеней вершин.

Доказательство свойства степеней вершин ориентированного графа:

Теория:

В ориентированном графе:

• Исходящая степень (Out-degree, deg⁺(v)) вершины v — это количество ребер, выходящих из нее.
• Входящая степень (In-degree, deg⁻(v)) вершины v — это количество ребер, входящих в нее.

Доказательство:

1. Рассмотрим любое ребро e в ориентированном графе G=(V, E). Это ребро соединяет две вершины, скажем, u и v, так, что оно выходит из u и входит в v.
2. Когда мы считаем сумму исходящих степеней всех вершин, каждое ребро e будет посчитано ровно один раз (как исходящее из начальной вершины).
3. Аналогично, когда мы считаем сумму входящих степеней всех вершин, каждое ребро e также будет посчитано ровно один раз (как входящее в конечную вершину).
4. Таким образом, каждое ребро в графе вносит ровно 1 в сумму исходящих степеней и ровно 1 в сумму входящих степеней.
5. Следовательно, сумма всех исходящих степеней всех вершин графа равна общему количеству ребер в графе, и сумма всех входящих степеней всех вершин также равна общему количеству ребер.
6. Поэтому сумма исходящих степеней вершин равна сумме входящих степеней вершин.

Формула:

Для графа G=(V, E):

\[ \sum_{v ∈ V} ext{deg}^+(v) = | E | = { ext{количество ребер} } \]

\[ { ext{deg}^-(v) }_{v ∈ V} = | E | \]

Отсюда следует:

\[ { ext{deg}^+(v) }_{v ∈ V} = { ext{deg}^-(v) }_{v ∈ V} \]

Что и требовалось доказать.