35
правок
Изменения
→Ориентированные графы
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
Так же для ориентированных графов определяют '''полустепень захода исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень исхода захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.
Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
