Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Полустепени вершин орграфа

Пусть А - некоторая вершина орграфа G(V,E). Степенью а(А) вершины А называется количество инцидентных ей дуг. Ясно, что степень вершины орграфа G равна степени соответствующей вершины в неориентированном графе G„ который является симметризацией орграфа G. Поэтому для ориентированного графа точно так же, как и для неориентированного, будет выполняться равенство (1.4.1):

?<7 Д) = 2|?|, и, следовательно, ориентированный граф

ASV может содержать лишь четное количество нечетных вершин.

В ориентированном графе G(V,E) дуги, инцидентные некоторой вершине А, можно разбить на два класса - входящие в эту вершину и выходящие из нее. В соответствии с этим степень вершины А расщепляется на два слагаемых:

где<7+(Л)- количество дуг, входящих в вершину А, называемое положительной полустепенью вершины А (или степенью захода), а<7 (А) - количество дуг, выходящих из вершины А, называемое отрицательной полустепенью вершины А (или степенью исхода).

Так, например, для орграфа на рисунке 178 имеем:

Каждая дуга орграфа выходит из некоторой одной вершины и входит в единственную вершину, поэтому количество дуг в орграфе, с одной стороны, равно сумме отрицательных полустепеней всех вершин и, с другой стороны, равно сумме положительных полустепеней всех вершин:

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы