1.1. Понятия смежности, инцидентности, степени

Если X={V,W} - ребро, то V и W − Концы ребра X.

Если X=(V,W) - дуга ориентированного графа, то V − Начало, W – Конец Дуги.

Вершина V и ребро X неориентированного графа (дуга X ориентированного графа) называются Инцидентными, если V является концом ребра X (началом или концом дуги X ).

Вершины V, W называются Смежными, если {V,W}ÎX.

Степенью вершины V графа G называется число d(V) ребер графа G, инцидентных вершине V.

Вершина графа, имеющая степень 0 называется Изолированной, а степень 1 – Висячей.

Полустепенью исхода (Захода) вершины V ориентированного графа D называется число d+(V) (d-(V)) дуг ориентированного графа D, исходящих из V (заходящих в V).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

< Предыдущая		Следующая >