Ориентированный граф
Ориентированный граф — это граф, в котором связи между вершинами имеют направление: дуга ведёт из одной вершины в другую. Поэтому для каждой вершины отдельно считают число входящих и исходящих дуг.
Степени вершины
У вершины ориентированного графа есть две степени. Входящая степень \(d^-(v)\) — количество дуг, направленных в вершину \(v\). Исходящая степень \(d^+(v)\) — количество дуг, направленных из вершины \(v\). Например, если дуги \(A\to B\), \(C\to B\) и \(B\to D\), то для вершины \(B\) входящая степень равна \(2\), а исходящая — \(1\).
Если в графе \(m\) дуг, то сумма исходящих степеней всех вершин и сумма входящих степеней также равны \(m\): каждая дуга один раз выходит из одной вершины и один раз входит в другую. Не следует путать эти величины с общей степенью вершины в неориентированном графе.
Пусть дуги графа таковы: \(A\to B\), \(A\to C\), \(C\to B\), \(B\to D\). Тогда \(d^+(A)=2\), \(d^-(A)=0\), \(d^+(B)=1\), \(d^-(B)=2\). Из \(A\) можно перейти в \(B\) или \(C\), но по этим дугам нельзя двигаться в обратную сторону.
Дуги \(A\to B\) и \(B\to A\) — разные дуги. Наличие одной из них не означает наличие другой. Если направления не указаны, речь обычно идёт о неориентированном графе, а не об ориентированном.
В графе есть дуги \(A\to B\), \(C\to A\), \(A\to D\). Каковы входящая и исходящая степени вершины \(A\)?
Главное
- Ориентированный граф состоит из вершин и направленных дуг.
- \(d^-(v)\) считает входящие дуги, а \(d^+(v)\) — исходящие.
- При \(m\) дугах сумма всех входящих степеней и сумма всех исходящих степеней равны \(m\).