Локальні степені вершин графа

Якщо задано матриці суміжності  або інцидентності E, то можна визначити локальні степені всіх його вершин.

Елементи _ij матриці суміжності – це кількість ребер, інцидентних вершинам v_i і v_j. Звідси (v_j) = .

Якщо враховувати внесок петель у степінь, то значення степеня визначається через коефіцієнти _ij матриці суміжності графа G за формулою

(v_j) = + _ij = + _ij.

Якщо вираховувати степінь через коефіцієнти матриці інцидентності, то (v_j) = . Коли i-те ребро звичайне, то = 2. Якщо воно є петлею, то = 1.

Оскільки кожне ребро має два кінці, в сумі ребра враховуються двічі. Таким чином, ця сума дорівнює подвоєній кількості ребер графа, тобто є парною

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

Якщо однорідний граф степеня k має n вершин та m ребер, то m = = , n = .

Означення 3. Звичайний граф називається повним, якщо кожна пара його вершин з’єднується ребром.

У звичайному графі P на n вершинах степені всіх вершин однакові й дорівнюють n – 1.

Локальні степені вершин орієнтованого графа є ₁(v) – кількість ребер із початком у вершині v і ₂(v) – кількість ребер, що входять у вершину v. Петля дає внесок 1 в обидва ці степені. Отже, ₁(v_i) = , ₂(v_i) = .

Оскільки кожне ребро орієнтованого графа G має один початок й один кінець, то суми та рівні. Тому в орієнтованому однорідному графі степеня k з n вершинами й m ребрами

m = = = kn, n = .

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

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

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

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

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

Доповнення частини H визначається множиною всіх ребер графа G, що не належать H.

Об’єднання H₁ H₂ та переріз H₁ H₂ частин H₁ і H₂ графа G визначаються природно:

V(H₁ H₂) = V(H₁) V(H₂);

E(H₁ H₂) = E(H₁) E(H₂);

V(H₁ H₂) = V(H₁) V(H₂);

E(H₁ H₂) = E(H₁) E(H₂).

Дві частини H₁ та H₂ не перерізаються по вершинах, якщо вони не мають спільних вершин, а значить і спільних ребер. Об’єднання H₁ H₂ частин, що не перерізаються по вершинах, називається прямою сумою. Частини H₁ й H₂ не перерізаються по ребрах, якщо E(H₁) E(H₂) = .

Маршрути, ланцюги та цикли

Означення. Нехай G – неорієнтований граф. Маршрутом M у графі G називається така скінченна або нескінченна послідовність вершин і ребер, які чергуються

(…, v₁, e₁, v₂, e₂, …, v_{n – 1}, e_{n – 1}, v_n, …) (1)

так, що кожні два сусідні ребра e_{i – 1} та e_i мають спільну інцидентну вершину v_i.

Маршрут M можна задавати послідовністю (…, v₁, v₂, …, v_n, …) його вершин (у звичайному графі), а також послідовністю (…, e₁, e₂, …, e_n, …) ребер.

Означення. Нехай маршрут M(e₁, e₂, …, e_n,) має початок v₀ і кінець v_n. Тоді його називають сполучним. Кількість ребер маршруту є його довжиною. Якщо v₀ = v_n, то маршрут називається замкненим, або циклічним. Відрізок (e_i, e_{i + 1}, …, e_j) скінченного або нескінченного маршруту M є маршрутом. Він називається ділянкою маршруту M.

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

Визначення маршруту можна перенести з графа на орієнтований граф. Маршрут в останньому називається шляхом.

Зв’язність

Означення. Дві вершини v і u називаються зв’язними, якщо існує маршрут вигляду (1) із кінцями v та u. Граф називається зв’язним, якщо будь-яка пара його вершин є зв’язною.

Означення. Зв’язністю графа називається мінімальна кількість вершин, вилучення яких приводить до утворення незв’язного графа.

Означення. Кількість вершин у максимально повному підграфі графа G називається щільністю (G) графа G. Кількість вершин у максимальному порожньому підграфі графа G називається нещільністю (G) графа G.

Означення. Довжина найменшого ланцюга між вершинами v і u звичайного зв’язного графа G називається відстанню d(v, u) між цими вершинами.

Очевидно, вона задовольняє всі аксіоми метрики:

d(v, u)  0;

d(v, u) = 0  v = u;

d(v, u) = d(u, v);

d(v, u) + d(u, v)  d(v, u).

Означення. Діаметром графа G називається величина d(G) = .

Виберемо деяку фіксовану вершину c і позначимо r(c) = . Величина r(c) називається максимальною віддалю від вершини c. Назвемо c₀ центром графа G, якщо r(G) = r(c₀) = .

Величина r(G) називається радіусом графа G, а будь-який найкоротшій ланцюг від центра c₀ до максимально віддаленої від нього вершини – радіальним.

Означення. Дводольний граф G_{m, n} – це граф, множину вершин якого можна розбити на дві підмножини V₁ і V₂ (|V₁| = m, |V₂| = n) таким чином, що кожне ребро графа з’єднує вершини з різних підмножин.

Означення. Граф називається k-зв’язним, якщо вилучаючи будь-яку його k– 1-у вершину, не можна порушити його зв’язність, а при вилученні деяких k вершин зв’язність може порушитися.

Означення. Граф називається k-ребернозв’язним, якщо k – максимальне з таких p, що при вилученні будь-яких p – 1 ребер зв’язність графа не порушується.

Означення. Орієнтований граф називається сильнозв’язним, якщо для будь-яких двох його вершин v та u існує шлях в обох напрямках.

Означення. Орієнтований граф називається однобічно зв’язним, якщо для будь-яких двох його вершин v_i та v_j існує шлях хоча б в одному напрямку.

Означення. Псевдографом, асоційованим з орієнтованим псевдографом D₁(V), називається псевдограф D₂(V) такий, в якому кожну дугу графа D₁ замінено на ребро графа D₂.

Орієнтований граф називається слабозв’язним, якщо зв’язним є асоційований з ним псевдограф.

Компонентою зв’язності (сильної зв’язності) графа G (орієнтованого графа D) називається його зв’язний (сильнозв’язний) підграф, який не є підграфом жодного зв’язного (сильнозв’язного) підграфа G (орієнтованого графа D).

Дерева

Означення. Граф G називається деревом, якщо він є зв’язним і не має циклів, а граф G, усі компоненти зв’язності якого є деревами, – лісом.

Граф, зображений на рисунку, є деревом.

Еквівалентні такі твердження:

1. граф G – дерево;

2. граф G є зв’язним і не має простих циклів;

3. граф G є зв’язним і n(G) = m(G) + 1;

4. для будь-яких двох різних вершин графа G існує єдиний (і притому простий) ланцюг;

5. граф G не містить циклів, але додаючи до нього будь-яке нове ребро, дістаємо точно один і до того простий цикл.