Неділя, 21.04.2019, 23:24
Гость

Мішатронік

Автор - Кренцін Михайло

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Вам легко дається програмування
Всього відповідей: 1
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0




Степінь вершини графа

Дві вершини u та v називають суміжними або сусідніми вершинами, якщо вони з’єднані ребром e=(u,v).

Суміжні вершини

Мал.1 Суміжні вершини. 

При цьому:

 

  •          Вершини u та v називають кінцями ребра e.
  •          Вершина u інцидентна ребру e.
  •          Ребро e інцидентне  вершині u.

Суміжними ребрами називають ребра, які мають спільний кінець. 

Степенем вершини графа називають число ребер, які інцидентні вершині u та позначають  deg u або d(u). 

Ізольованою вершиною називають вершину графа, степінь якої дорівнює нулю.

Мал.2. Степінь вершини. 

Ізольованою вершиною називають вершину графа, степінь якої дорівнює нулю.

Мал.3. Ізольована вершина. 

Висячою вершиною називають вершину графа, степінь якої дорівнює одиниці.

Мал.4. Висяча вершина або лист. 

Множину вершин, які суміжні з вершиною v називають оточенням вершини v та позначають S(v).

Мал.5. Оточення вершини. 

Теорема (Лема про рукостискання). Сума степенів всіх вершин графа дорівнює подвоєному числу ребер.

Наслідок. В будь-якому графі число вершин з непарним степенем – парне.

 

Форма входа
Пошук
Календар
«  Квітень 2019  »
ПнВтСрЧтПтСбНд
1234567
891011121314
15161718192021
22232425262728
2930
Друзі сайту
Погода у Вінниці


Єдина Країна! Единая Страна!