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

(Локальної) Ступенем або (валентністю)

вершини називається число ребер, інціндентних вершині v.

Якщо не обмовляється особливо, то петля враховується двічі при підрахунку валентності вершини.

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

Вершина називається ізольованою. якщо вона несуміжних ні з однією з вершин графа, або, що те ж саме, неінціндентна жодному ребру. Ступінь цієї вершини дорівнює 0.

Вершина, що має ступінь, рівну 1, називається висячої (кінцевий). Ребро, інціндентное висячої вершині, називають кінцевим.

Твердження 1. (Лемман рукостискання): У н-графі сума ступенів усіх вершин дорівнює подвоєному числу ребер (тобто парна):

. де m - число ребер.

Слідство 1. Довільний граф має парне число вершин непарного ступеня.

Слідство 1. Число ребер у повному графі одно

. де n - число вершин.

В ор-графі дві (локальних) ступеня вершини:

і число ребер з початком і кінцем в v відповідно.

Твердження 2. Суми ступенів усіх вершин ор-графа дорівнюють кількості ребер цього графа і, отже, рівні між собою:. m - число ребер.

Частини, суграфом і підграфи

Граф H називається частиною графа G (

), Якщо безлічі його вершин і ребер містяться в безлічі вершин і ребер графаG.

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

подграфом

графаз безліччю вершинназивається частина графа, якій належать всі ребра інціндентние

(Подграф

можна отримати з графашляхом стирання деяких з вершин і / або ребер графа. При цьому, якщо стираємо вершину, то обов'язково стираємо і все ребра, інціндентние їй).

Операції над частинами графа

доповнення

до частіH визначається безліччю всіх ребер графа G. котрі належать до H:

, ;

сума

частин і графаG. це граф, у якого

твір

частин і графаG. це граф, у якого

частини

і не перетинаються по вершинам, якщо вони не мають спільних вершин, а значить і загальних ребер:

, .

частини

і не перетинаються по ребрах, якщо

.

Якщо, то сума

називаетсяпрямой.

Графи і бінарні відносини

Відношенню R, заданому на множині V, взаємно однозначно відповідає орієнтований граф G (R) без кратних ребер з безліччю вершин V, в якому ребро

існує, тільки якщо виконано. Симетричного отношеніюR взаємно однозначно відповідає неорієнтовані граф без кратних ребер G (R) .Антісімметрічному відношенню R взаємно однозначно відповідає орієнтований граф без кратних ребер, що не містить пар вершин з ребрами, протилежно спрямованими до різних вершин. Якщо Rрефлексівно. то граф G (R) без кратних ребер має петлі у всіх вершинах. Якщо Rантірефлексівно, то граф G (R) без кратних ребер не має петель. Якщо Rтранзітівно. то в графі G (R) без кратних ребер для кожної пари ребер іє замикає ребро. нехай- доповнення відносини R на V. , де U -Універсальна (повне) відношення , тобто відношення, що має місце між будь-якою парою елементів ізV.

Граф G (

) Є доповненням графаG (R) (до повного орграфа K з безліччю вершин V і множиною ребер ).

Граф зворотного відносини G (

) Відрізняється від графаG (R) тим, що направлення всіх ребер замінені на зворотні.

Граф об'єднання двох відносин, заданих на V,

є графом суми двох графіві:

.

Граф перетину відносин на V,

є графом перетину двох графіві:

.