Page 19 - 4386

Якщо в графі G з n вершинами степінь вершини дорівнює k,

то в доповненні G її степінь n-k-1.

Наприклад, доповненням графа G, зображеного на

рис. 1.11 а є граф G , зображений на рис. 1.11 б. Для порівняння,

повний граф зображений на рис. 1.11 в.

а б в

Рисунок 1.11 – Приклад доповнення графа

Операція вилучення вершини v з графа G=(V, E) полягає у

вилученні з множини V елемента v, а з множини E − всіх ребер,

інцидентних v.

Операція вилучення ребра e з графа G=(V, E) − це вилучення

елемента e з множини E. При цьому всі вершини зберігаються.

Приклад 1.8. Якщо G=({v , v , v }, {(v , v ), (v , v ), (v , v )}),
1
1
2
3
3
2
3
2
1
то G-(v , v )=({v , v , v }, {(v ,v ), (v ,v )}), а G-v =({v ,v },
3
3
1
1
3
2
2
1
2
1
3
2
{(v ,v )}).
3
2
1.6 Часткові графи і підграфи
Якщо для двох графів G=(V, E) та G´=(V´, E´) виконуються
включення V´⊆V та E´⊆E, тобто, якщо кожна вершина і кожне
ребро графа G´ є відповідно вершиною і ребром графа G, то граф
G´ називається підграфом графа G; це позначається G´⊆G. Граф
G у цьому випадку називається надграфом графа G´. Якщо G´⊆G
та V´=V, тобто, якщо граф G´ містить усі вершини графа G, то
граф G´ називається суграфом (каркасом) графа G. Він також є

підграфом графа G.

18