168
правок
Изменения
→Ориентированные графы
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что :* <tex> v </tex> {{-- -}} '''предок''' <btex>предокu </btex> .* <tex> u </tex>. Также вершины и <tex> v </tex> {{---}} '''смежные'''* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u ) </tex> и , вершина <tex> v </tex> называют '''инцидентна''' ребру <btex>смежными(v, u) </btex> Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют <b>тривиальным</b>.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
