Главная > Математика > Конечные графы и сети
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.3. Термины для описания локальной структуры

Рассмотрим термины, полезные для описания некоторых структурных свойств ориентированных графов и не используемые в неориентированном случае. Если то дуги называются строго параллельными. Если то не строго параллельны. Если то говорят, что дуга а направлена от вершины к вершине Дуга а считается положительно инцидентной ее конечной вершине Число дуг, положительно инцидентных вершине и, называется полоокительной степенью и обозначается через Отрицательная степень определяется аналогично и обозначается через (Ориентированная петля, инцидентная и, считается положительно и отрицательно инцидентной с Индексированные степени вершин и , очевидно, связаны с введенной ранее степенью следующим образом:

(Для графов, не являющихся конечными, эта взаимосвязь остается верной, если ее интерпретировать как соотношение кардинальных чисел.)

Учитывая, что каждая дуга положительно инцидентна одной вершине и отрицательно инцидентна также одной вершине, получим

где означает число дуг графа. Напомним, что в неориентированном случае мы имеем

Ориентированный граф называется обыкновенным, если он не имеет строго параллельных дуг и петель. Заметим, что если обыкновенный ориентированный граф имеет параллельные, но противоположно ориентированные дуги, то соответствующий неориентированный граф уже не будет обыкновенным графом в неориентированном смысле, так как он содержит параллельные ребра. Дуги обыкновенно ориентированного графа могут быть

однозначно представлены упорядоченными парами вершин, так как между любой данной парой вершин может быть не более одной дуги сзаданным направлением. (Заметим, что такое представление есть частный случай представления графа с помощью множества вершин V и множества дуг А, а не особая форма представления графа. На природу элементов А не наложено никаких ограничений, в частности, они могут быть элементами

<< Предыдущий параграф Следующий параграф >>
Оглавление