 |
Частини, суграфи і підграфи графу.
|
|
|
|
Операції з частинами графу
Визначення. Граф Н називається частиною графу G (позначається H Í G), якщо:
а) V (H) Í V (G);
б) E (H) Í E (G).
Визначення. Граф Н називається суграфом графу G, якщо він є частиною графу G і
V (H) = V (G).
На Рис. 4 зображені граф G і його три частини. Граф H 3 є суграфом.
Рис.4.
Визначення. Суграф H називається покриваючим для графу G, якщо будь-яка вершина H інцидентна хоча б одному ребру з G. Зауважимо, що якщо в графі G є ізольовані вершини, то для нього не існує покриваючого графу H.
Визначення. Підграфом G (U) графу G (V) називається така його частина, яка містить всі ребра графу G (V), що з’єднують дві будь-які вершини з множини U.
На рис. 4 H 1 не є підграфом G (не містить ребро e (2, 4)), а H 2 – підграф графу G.
Визначення. Зірковим графом, який визначається деякою вершиною a Î V, називається граф, що містить всі ребра даного графу G (V), інцидентні вершині „ a ”.
За аналогією з операціями поміж множинами можна виконувати і операції між графами.
Визначення. Якщо H – частина графу, то 
(доповнення графу H) – це граф, в який входять всі ребра графу G, які не належать H:
.
Визначення. Нехай H 1 і H 2 - дві частини графу G. Тоді H = H 1 È H 2 (об’єднання або сума) це також частина графу G, яка складається зі всіх ребер, що належать або H 1 або H 2.
Визначення. Нехай H 1 і H 2 - дві частини графу G. Тоді H = H 1 Ç H 2 (перетин) це частина графу G, яка складається зі всіх ребер, що належать H 1 та H 2 одночасно.
Визначення. Якщо дві частини H 1 і H 2 графу G не мають спільних вершин, то їх сума H = H 1 È H 2 називається прямою. Якщо H 1 і H 2 не перетинаються по ребрах, то їх сума називається прямою по ребрах.
Наприклад: 
- пряма сума за ребрами.
Маршрути, ланцюги і цикли
|
|
|
Деякі визначення
Нехай G - неорієнтований граф.
Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e 0, e 1, …, en, …} в якій кожні два сусідні ребра ei - 1 і ei мають спільну вершину, тобто
e 0 = (v 0, v 1)
e 1 = (v 1, v 2)
e 2 = (v 2, v 3)
...
en = (vn, vn + 1).
Визначення. Якщо в S немає ребер, які стоять перед e 0, то v 0 називається початковою вершиною S; якщо немає ребер після en - 1, то vn - кінцевою вершиною. Якщо вершина vi належить і ei - 1 і ei, то вона називається внутрішньою.
Визначення. Якщо маршрут S має початкову і кінцеву вершини, то він називається скінченним; якщо S має початок і не має кінцевої вершини (або навпаки), то він називається односторонньо-нескінченним; якщо немає ні початкової вершини ні кінцевої – то двосторонньо-нескінченними. Якщо S має початкову вершину v 0 і кінцеву vn, то позначається
S = S (v 0, vn)
(тобто S - це маршрут довжини n, який з’єднує вершини v 0 і vn).
Визначення. Якщо v 0 = vn, то маршрут називається циклічним.
Визначення. Якщо vi і vj - дві вершини маршруту S, то
S (vi, vj) = (ei, …, ei + 1, …, ej - 1)
називається підмаршрутом.
На рис.5 маршрут S = (e 1, e 2, e 3, e 4, e 5) є скінченним, має довжину 5, початкову вершину v 1 і кінцеву v 5. Маршрут S = (e 2, e 3, e 4) є підмаршрутом даного маршруту.
Рис.5
Визначення. Ланцюг – це маршрут, кожне ребро якого зустрічається рівно один раз. Циклічний ланцюг називається циклом.
Визначення. Нециклічний ланцюг називається простим, якщо в ньому жодна вершина не повторюється. Цикл з початком (і кінцем) в v 0 називається простим, якщо в ньому жодна вершина, крім v 0 не повторюється.
Зрозуміло, що частина ланцюга або циклу теж є ланцюгом або циклом.
Для орієнтованих графів вводяться в розгляд як неорієнтовані маршрути (ланцюги) (тобто не приймається до уваги орієнтація ребер), так і орієнтовані маршрути (ланцюги).
Зв’язаність
Нехай G - неорієнтований граф.
|
|
|
Визначення. Дві вершини „ a ” і „ b ” графу G називаються зв’язними, якщо існує маршрут S (a, b).
Якщо в S (a, b) деяка вершина vi повторюється більше одного разу, то відкидаючи циклічну ділянку S (vi, vi), отримаємо новий маршрут S ’(a, b), в якому вершина vi зустрічається тільки один раз. Повторюючи цю процедуру для всіх таких вершин vi, приходимо до висновку: якщо дві вершини в графі можуть бути зв’язані маршрутом, то існує і простий ланцюг, який зв’язує ті ж вершини.
Визначення. Граф G називається зв’язним, якщо зв’язна будь-яка його пара вершин.
Всі підграфи G (Vi) зв’язного графу G (V) є теж зв’язними і називаються зв’язними компонентами графу.
Зауважимо, що зв’язність – відношення еквівалентності між вершинами графу:
а) довільна вершина v графу зв’язана сама з собою;
б) якщо „ a ” і „ b ” – зв’язні (тобто існує маршрут S (a, b)), то в силу неорієнтованості графу „ b ” і „ а ” теж зв’язані (маршрутом S (b, a));
в) якщо зв’язані „ а ” і „ b ” (маршрутом S 1(a, b)) і „ b ” і „ с ” (маршрутом S 2(b, c)), то існує маршрут з „ а ” в „ с ” (S 1(a, b) + S 2(b, c)), тобто вершини „ a ” і „ c ” теж зв’язані.
В силу відомого твердження з алгебри, граф G розбивається на класи еквівалентності – підграфи, в яких всі вершини є зв’язаними між собою і які не мають спільних вершин:
, 
(пряма сума)
таким чином, істинне
Твердження. Довільний неорієнтований граф розбивається на пряму суму своїх зв’язаних компонент.
Це дозволяє більшість задач зводити до випадку зв’язаних графів.
|
|
|
