Инструменты пользователя

Инструменты сайта


examination:diskretka:question10

Вопрос №10. Степени и полустепени вершин графа. Однородные графы

Степени и полустепени вершин графа

Степени вершин мы будем определять для нерграфа, а полустепени для орграфа.

Глобальной степенью вершины неорграфа называется число всех ребер графа инцидентных этой вершине (dg(V)).

Локальной степенью вершины неорграфа называется количество всех ребер графа инцидентных данной вершине, где при подсчете количества каждая петля рассматриваемой вершины считается дважды (т.к. при рассечении петли на 2 части она порождает 2 ребра)(dl(V)).

dl(V)=dg(V)+ число петель на вершине V.

Т.обр. если на вершине петель нет, то dl(V)=dg(V).

Для орграфа естественно определить 2 вида степеней:

Полуcтепенью исхода вершины орграфа называется число дуг этого графа включая и петли, для которых данная вершина является началом. (d-(V)).

Полуcтепенью захода вершины орграфа называется число дуг этого графа включая и петли, для которых данная вершина является концом. (d+(V)).

d-(V)+d+(V)=dl(V)


Лемма о рукопожатиях Сумма локальных степеней всех вершин конечного неорграфа - четное число, равное удвоенному числу ребер.

Док-во: каждое ребро при сложении степеней вершин графа учитывается дважды, т.е. упомянутая сумма всех степеней равна удвоенному числу всех ребер, т.е. четна.

Теорема: во всяком конечном неоргафе без петель и кратных ребер, имеющем не менее двух вершин, найдутся 2 вершины имеющие одинаковую степень.

Док-во: Пусть существует граф имеющий n>=2 вершин, любые степени вершин которого попарно различны.

Поскольку рассматриваемый граф простой, то степени его вершин не превосходят числа n-1 и потому совпадают с множеством {0,1,…,n-1}, значит в нашем графе имеется одна вершина степени 0 (т.е. изолированная) и имеется вершина степени n-1, т.е связанная ребрами с остальными вершинами, т.е. и с изолированной, таким образом получаем противоречие. Значит теорема верна, ч.т.д.


Однородные графы

Неорграф называется однородным степени однородности k, если степени всех его вершин совпадают с числом k (т.е. равны друг другу).(пример такого графа- полный граф).

Утверждение: пусть n,m,k-соответственно число вершин, число ребер и степень однородности некоторого однородного графа. Тогда эти три числа связываются в формулу: k•n=2m.

Замечание: указанное утверждение равно справедливо для однородных графов без петель и с петлями (в последнем случае под степенью вершины понимается локальная степень)

examination/diskretka/question10.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)