Смежность, инцидентность, степени
Определение. Если е = {v, w} – ребро графа, то вершины v, w называются концами ребра е; в этом случае также говорят, что ребро е соединяет вершины v, w.
Определение. Если е = {v, w} – дуга орграфа, то вершина v называется началом, а вершина w – концом дуги е; в этом случае также говорят, что дуга е исходит из вершины v и заходит в вершину w.
Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.
Определение. Две вершины называются смежными, если существует ребро, концами которого они являются. Два ребра называются смежными, если они имеют общую вершину.
Определение.Степенью вершины v графа G называется число d(v) ребер графа, которым инцидентна эта вершина.
Определение. Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.
Замечание. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).
Определение.Полустепенью исхода (захода) вершины v орграфа D называется число d+(v) (d -(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).
Замечание. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d+(v), так и в d -(v).
Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).
предыдущаяследующая