Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

 

Нехай G(V) - неорієнтований граф.

Визначення. Степенем r(a) деякої вершини a Î V називається кількість ребер графу, інцидентних цій вершині.

Якщо граф заданий матрицею суміжності вершин, то

(1)

Для матриці інцидентності аналогічна формула має вигляд

(2)

Число ребер у графі G позначимо через vE = vE(G). При підрахунку суми кожне ребро e(vi, vj), графу G підраховується двічі: один раз – як таке, що з’єднує вершину vi з vj, а другий раз – як таке, що з’єднує vj з vi. Тому

(3)

(формула (3) залишається правильною і для графу з петлями, якщо їх розглядати як подвійні ребра).

Оскільки в лівій частині формули (3) стоїть парне число, то це означає, що у скінченному графі без петель кількість вершин з непарним степенем – парна.

Визначення. Граф називається однорідним степеня k, якщо r(vi = k), для всіх vi Î V.

В однорідному графі кількість ребер згідно з формулою (3) vE = nk/2.

Визначення. Повний граф U = U(V) - це неорієнтований граф, у якому дві довільні вершини з’єднані рівно одним ребром.

Зрозуміло, що повний граф U(V) з n вершинами – це однорідний граф степеня (n ‑ 1). Тому vE = n(n – 1) / 2.

Визначення. Повний граф з петлями U0 = U0(V) - це повний граф, у якому до кожної вершини додана петля.

Кількість ребер у повному графі з петлями vE(U0) = vE(U) + n = n(n + 1) / 2.

Нехай тепер G(V) - орієнтований граф. Тоді через r(vi) і r*(vi) позначають кількість ребер, які виходять з вершини vi і входять в вершину vi відповідно.

Аналогічно попередньому кількість ребер в орієнтованому графі

.

 


Читайте також:

  1. Будова осцилографа
  2. Доба кінематографа
  3. Компоненти сильної зв'язності графа
  4. Малюнок № 1.19. Задання декартового добутку множин за допомогою графа.
  5. Розфарбовування графа, хроматичний поліном




Переглядів: 3077

<== попередня сторінка | наступна сторінка ==>
Способи задання графів | Частини, суграфи і підграфи графу.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.