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

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

Визначення. Граф Н називається частиною графу G (позначається H Í G), якщо:

а) V(H) Í V(G);

б) E(H) Í E(G).

Визначення. Граф Н називається суграфом графу G, якщо він є частиною графу G і

V(H) = V(G).

На Рис. 4 зображені граф G і його три частини. Граф H3 є суграфом.

Рис.4.

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

Визначення. Підграфом G(U) графу G(V) називається така його частина, яка містить всі ребра графу G(V), що з’єднують дві будь-які вершини з множини U.

На рис. 4 H1 не є підграфом G (не містить ребро e(2, 4)), а H2 – підграф графу G.

Визначення. Зірковим графом, який визначається деякою вершиною a Î V, називається граф, що містить всі ребра даного графу G(V), інцидентні вершині „a”.

За аналогією з операціями поміж множинами можна виконувати і операції між графами.

Визначення. Якщо H – частина графу, то (доповнення графу H) – це граф, в який входять всі ребра графу G, які не належать H:

.

Визначення. Нехай H₁ і H₂ - дві частини графу G. Тоді H = H₁ È H₂ (об’єднання або сума) це також частина графу G, яка складається зі всіх ребер, що належать або H₁ або H₂.

Визначення. Нехай H₁ і H₂ - дві частини графу G. Тоді H = H₁ Ç H₂ (перетин) це частина графу G, яка складається зі всіх ребер, що належать H₁ та H₂ одночасно.

Визначення. Якщо дві частини H₁ і H₂ графу G не мають спільних вершин, то їх сума H = H₁ È H₂ називається прямою. Якщо H₁ і H₂ не перетинаються по ребрах, то їх сума називається прямою по ребрах.

Наприклад: - пряма сума за ребрами.

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

Деякі визначення

Нехай G - неорієнтований граф.

Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e₀, e₁, …, e_n, …} в якій кожні два сусідні ребра e_{i - 1} і e_i мають спільну вершину, тобто

e₀ = (v₀, v₁)

e₁ = (v₁, v₂)

e₂ = (v₂, v₃)

. . .

e_n = (v_n, v_{n + 1}).

Визначення. Якщо в S немає ребер, які стоять перед e₀, то v₀ називається початковою вершиною S; якщо немає ребер після e_{n - 1}, то v_n - кінцевою вершиною. Якщо вершина v_i належить і e_{i - 1} і e_i, то вона називається внутрішньою.

Визначення. Якщо маршрут S має початкову і кінцеву вершини, то він називається скінченним; якщо S має початок і не має кінцевої вершини (або навпаки), то він називається односторонньо-нескінченним; якщо немає ні початкової вершини ні кінцевої – то двосторонньо-нескінченними. Якщо S має початкову вершину v₀ і кінцеву v_n, то позначається

S = S(v₀, v_n)

(тобто S - це маршрут довжини n, який з’єднує вершини v₀ і v_n ).

Визначення. Якщо v₀ = v_n, то маршрут називається циклічним.

Визначення. Якщо v_i і v_j - дві вершини маршруту S, то

S(v_i, v_j) = (e_i, …, e_{i + 1}, …, e_{j - 1})

називається підмаршрутом.

На рис.5 маршрут S = (e₁, e₂, e₃, e₄, e₅) є скінченним, має довжину 5, початкову вершину v₁ і кінцеву v₅. Маршрут S = (e₂, e₃, e₄) є підмаршрутом даного маршруту.

Рис.5

Визначення. Ланцюг – це маршрут, кожне ребро якого зустрічається рівно один раз. Циклічний ланцюг називається циклом.

Визначення. Нециклічний ланцюг називається простим, якщо в ньому жодна вершина не повторюється. Цикл з початком (і кінцем) в v₀ називається простим, якщо в ньому жодна вершина, крім v₀ не повторюється.

Зрозуміло, що частина ланцюга або циклу теж є ланцюгом або циклом.

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

Зв’язаність

Нехай G - неорієнтований граф.

Визначення. Дві вершини „a” і „b” графу G називаються зв’язними, якщо існує маршрут S(a, b).

Якщо в S(a, b) деяка вершина v_i повторюється більше одного разу, то відкидаючи циклічну ділянку S(v_i, v_i), отримаємо новий маршрут S’(a, b), в якому вершина v_i зустрічається тільки один раз. Повторюючи цю процедуру для всіх таких вершин v_i, приходимо до висновку: якщо дві вершини в графі можуть бути зв’язані маршрутом, то існує і простий ланцюг, який зв’язує ті ж вершини.

Визначення. Граф G називається зв’язним, якщо зв’язна будь-яка його пара вершин.

Всі підграфи G(V_i) зв’язного графу G(V) є теж зв’язними і називаються зв’язними компонентами графу.

Зауважимо, що зв’язність – відношення еквівалентності між вершинами графу:

а) довільна вершина v графу зв’язана сама з собою;

б) якщо „a” і „b” – зв’язні (тобто існує маршрут S(a, b)), то в силу неорієнтованості графу „b” і „а” теж зв’язані (маршрутом S(b, a));

в) якщо зв’язані „а” і „b” (маршрутом S₁(a, b)) і „b” і „с” (маршрутом S₂(b, c)), то існує маршрут з „а” в „с” (S₁(a, b) + S₂(b, c)), тобто вершини „a” і „c” теж зв’язані.

В силу відомого твердження з алгебри, граф G розбивається на класи еквівалентності – підграфи, в яких всі вершини є зв’язаними між собою і які не мають спільних вершин:

, (пряма сума)

таким чином, істинне

Твердження. Довільний неорієнтований граф розбивається на пряму суму своїх зв’язаних компонент.

Це дозволяє більшість задач зводити до випадку зв’язаних графів.