Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Смежность и инцидентность

Пусть v1, v2 - вершины, е = (v1, v2) - соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

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

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

Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4 - висячие.

Пример. Для графа, изображенного на рис. 3.3.

Ребро e1 инцидентно вершинам v1 и v2. Вершина v1 инцидентна ребрам e1 и e2. Ребра e1 и e2 – смежны. Вершины v1 и v2 – смежны.

. p(G)=3, q(G)=5.

Т.о. можно заметить, что .

Теорема Эйлера: .

Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин.


Дата добавления: 2015-10-13; просмотров: 136 | Нарушение авторских прав


Читайте в этой же книге: История теории графов | Матрица инциденций | Гамильтоновы графы |
<== предыдущая страница | следующая страница ==>
Определения| Изоморфизм графов

mybiblioteka.su - 2015-2024 год. (0.006 сек.)