Page 59 - 4496

Якщо для визначення ЛС вершин графа
використовується таблиця суміжностей, то для цієї мети
використовується така формула:

n

  V )( j    jj
ij
 i 1
Означення 1. Граф називається однорідним степеня k,
якщо степені всіх його вершин рівні між собою і дорівнюють
k.
Якщо однорідний граф має n вершин і m ребер, то
kn
m 
2
Приклад:

Однорідний граф (k=3)
3 * 4
m   6
n=4; 2
Означення 1. Звичайний граф називається повним, якщо
кожна пара його вершин з’єднана ребром.

3. 7 Локальні степені вершин орієнтованих графів
Для орієнтованих графів (орграфів) визначаються дві ЛС
вершини.
Перша ЛС- кількість ребер з початком у вершині і друга
ЛС- кількість ребер, що закінчуються в вершині. Позначимо
ці ЛС для і- тої вершини відповідно через  1(v i) i  2(v 2)
Тоді
n
 1 ( v )    ij (3.1)
i
 j 1

56