Полустепени вершин орграфа
Пусть, А — некоторая вершина орграфа G (V, E). Степенью, а (А) вершины, А называется количество инцидентных ей дуг. Ясно, что степень вершины орграфа G равна степени соответствующей вершины в неориентированном графе G" который является симметризацией орграфа G. Поэтому для ориентированного графа точно так же, как и для неориентированного, будет выполняться равенство (1.4.1): Каждая дуга орграфа… Читать ещё >
Полустепени вершин орграфа (реферат, курсовая, диплом, контрольная)
Пусть А — некоторая вершина орграфа G (V, E). Степенью а (А) вершины А называется количество инцидентных ей дуг. Ясно, что степень вершины орграфа G равна степени соответствующей вершины в неориентированном графе G" который является симметризацией орграфа G. Поэтому для ориентированного графа точно так же, как и для неориентированного, будет выполняться равенство (1.4.1):
?<7 Д) = 2|?|, и, следовательно, ориентированный граф
ASV может содержать лишь четное количество нечетных вершин.
В ориентированном графе G (V, E) дуги, инцидентные некоторой вершине А, можно разбить на два класса — входящие в эту вершину и выходящие из нее. В соответствии с этим степень вершины А расщепляется на два слагаемых:
где<7+(Л) — количество дуг, входящих в вершину А, называемое положительной полустепенью вершины А (или степенью захода), а<7 (А) — количество дуг, выходящих из вершины А, называемое отрицательной полустепенью вершины А (или степенью исхода).
Так, например, для орграфа на рисунке 178 имеем:
Каждая дуга орграфа выходит из некоторой одной вершины и входит в единственную вершину, поэтому количество дуг в орграфе, с одной стороны, равно сумме отрицательных полустепеней всех вершин и, с другой стороны, равно сумме положительных полустепеней всех вершин:
