Смежность и инцидентностьПусть v1, v2 - вершины, е = (v1, v2) - соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Степенью вершины v графа G(V, E) называется число ребер, инцидентных данной вершине. Обозначение: Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей. Пример. Для графа, изображенного на рис. 3: вершина 3 – изолированная, вершины 1 и 4 - висячие. Пример. Для графа, изображенного на рис. 1. Ребро e1 инцидентно вершинам v1 и v2. Вершина v1 инцидентна ребрам e1 и e2. Ребра e1 и e2 – смежны. Вершины v1 и v2 – смежны.
Т.о. можно заметить, что Теорема Эйлера: Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин.
|
.
. p(G)=3, q(G)=5.
.
.
