Page 80 - 2589

m n
(  )           .
j ij jj ij jj
 i 1 k 1

Залежно від задачі, що розглядається, може бути потрібен
той чи інший спосіб визначення степеня вершини. Тому в
кожному випадку має бути відомо, чи є петля один раз або двічі
інцидентною своїй вершині.

Оскільки кожне ребро має два кінці, в сумі  ( ) ребра
v G
враховуються двічі. Таким чином, ця сума дорівнює подвоєному
числу ребер графа, тобто є парною. Отже, парна також кількість
непарних доданків цієї суми, тобто кількість вершин непарного

степеня.

Граф називається однорідним степеня k якщо степені всіх
його вершин дорівнюють k і, отже, є рівними між собою.

Якщо однорідний граф степеня k має n вершин та m ребер, то
1 kn 2 m
m    ( )  , n  ,
2 v G 2 k
Звичайний граф називається повним, якщо кожна пара його

вершин сполучається ребром. У звичайного повного графа Р на
n
n вершинах степені всіх вершин однакові й дорівнюють n - 1.

5.4 Частинний граф, суграфи та підграфи

Граф Н називається частинним графом графа (частиною)

G ((H  G ), якщо множина його вершин V(Н) міститься в
множині V(G), а множина Е(Н) ребер – в Е(G). Якщо V(Н)=V(G),
то частина графа називається суграфом.

Наприклад, існує нульовий суграф, множина ребер якого є
порожньою. Суграф Н покриває вершини неорієнтованого графа
G (або є покривним), якщо будь-яка вершина останнього –
інцидентна хоча б одному ребру з Н. Таким чином, якщо в графі

G існує ізольована вершина v, не інцидентна жодному ребру, то
покривного суграфа цього графа не існує.
Будь-яку множину В ребер графа G можна вважати

множиною ребер деякої частини Н. Множина вершин цієї
частини складається з вершин, інцидентних елементам множини
В. Якщо В є множиною ребер іншої частини Н', то НН', причому
вершини Н', що не належать H, у графі H' є ізольованими.

Підграфом графа G називається частина графа з множиною
вершин UV(G), якщо її ребрами є всі ребра з Е(G), обидва кінці

80