Понеділок, 18.02.2019, 09:13
Гость

Мішатронік

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

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Java чи С++
Всього відповідей: 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  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728
Друзі сайту
Погода у Вінниці


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