Операції над частинами графа. Графи та бінарні відношення.

Граф H називається підграфом графа G, , якщо множини його вершин V(Н) і ребер Е(Н) містяться в множинах вершин V(G) і ребер E(G) відповідно, тобто і .

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

Над частинами графа G можуть виконуватися наступні операції:

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

, ;

– сума Н₁ і Н₂ .Результатом є підграф Н₁ Н₂ , який складається з ребер та вершин, що належали Н₁ і Н₂ , або обом графам одночасно, тобто:

та ;

– перетинання або добуток .Результатом є підграф Н₁ Н₂, який складається з ребер та вершин, що належали Н₁ і Н₂ одночасно, тобто:

та .

Дві частини Н₁ і Н₂ не перетинаються по вершинах, якщо вони не мають загальних вершин , а виходить, і загальних ребер . Частини Н₁ і Н₂ не перетинаються по ребрах, якщо . Якщо , то сума називається прямою.

Приклад 2. На рисунку 6 подані приклади графів, їх суми та добутку

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

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

Приклад 3.Якими особливостями відрізняється граф G, що взаємно однозначно відповідає бінарному відношенню R, якщо R:

а)симетричне;

б)антисиметричне;

в) рефлексивне;

г) антирефлексивне;

д)транзитивне.

Нехай бінарне відношення R визначене на множині

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

б) Антисиметричному відношенню R взаємно однозначно відповідає орієнтований граф без кратних ребер, що не містить пар вершин з ребрами, протилежно спрямованими до різних вершин.

в) Якщо R рефлексивне, то граф G(R) без кратних ребер має петлі у всіх вершинах.

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

д) Якщо R транзитивне, то в графі G{R) без кратних ребер для кожної пари ребер ( ) і ( ) мається замикаюче ребро ( ).

Приклад 4.Нехай орієнтований граф G на рис.7 задає відношення R: G(R). Які властивості відношення?

Відношення R визначене на множині V= {а, b, c, d, e, f) елементів - вершин графа: |V|= 6. Властивості відношення:

а) не є рефлексивним, тому що відсутнє наприклад, a R а, bRb;

б) не антирефлексивне, оскільки має місце cRc,dRd;

в) не є симетричним, тому що, наприклад, має місце aRb, але відсутня bRа;

г) не антисиметричне, оскільки виконується, наприклад, a R с і с R а;

д) не транзитивне, тому що, наприклад, має місце aRb та bRd, але відсутнє a R d.

Тема 4.2 Ланцюги, цикли. Зв’язність графів та теорема Ейлера.

Нехай G – н-граф.

Маршрутом в G називається така кінцева або безкінечна послідовність ребер М(е₁ е₂,... , e_і,... , е_n), в якій кожні два сусідні ребра e_i-1 та е_і мають спільну інцедентну вершину.

В маршруті одне і те ж ребро може зустрічатися кілька разів. Початок маршруту - вершина v₀, що інцидентна ребру е₁ та не інцидентна е₂; кінець маршруту v_n інцидентен е_n та не інцидентен е_n-1. Якщо е₁ е₂, (e_і,... , е_n), - кратні ребра, необхідно додаткова вказівка, яку з двох інцидентних вершин вважати початком (кінцем) маршруту.

Маршрут, в якому всі ребра різні, називається ланцюгом.(рис. 8 Л₁=(ad,db,ba,ac)) Ланцюг також можна визначити як маршрут, в якому будь-яке ребро входить до нього лише один раз, а також простим ланцюгом, якщо кожна вершина ланцюга також зустрічається один раз.(рис. 8 Л₂=(db,ba,ac))

Ланцюг, початок і кінець якого збігаються називається циклом та простим циклом, якщо це – простий ланцюг.

Множину вершин графа G можна розбити на підмножини, що не перетинаються V₁…V_ктакі, що вершини, які входять до однієї підмножини пов'язані між собою, а будь-які інші дві вершини з різних підмножин не зв'язані. Дві вершини називаються зв'язними, якщо існує ланцюг, що поєднує ці вершини. Відношення зв'язності вершин має властивість еквівалентності. Граф G називається зв'язним, якщо всі його вершини зв'язані між собою. Тому всі зв'язні підграфи G(F_і) називаються компонентами зв'язності графа. Граф, зображений на рисунку 9 має 4 компоненти зв'язності , , , . Причому вершина s, яка не з'єднана ні з одним ребром є так званою псевдовершиною.

Відношення зв'язностівершин н-графа має наступні властивості :

• рефлексивності: якщо вершина зв'язана з будь-якою іншою вершиною v', тоді вона зв'язана і сама з собою (ізольовані вершини також вважаються зв”язаними самі з собою);

• симетричності: якщо в графі U є маршрут з початком v' і кінцем v", тоді існує маршрут з початком v" і кінцем v';

• транзитивності: якщо вершина v' зв'язана з v" маршрутом М’(е’₁,...,е'_n),а v" та v"' - маршрутом М”(е”₁,...,е”_p), то v' зв'язана з v'" маршрутом М(е’₁,...,е'_n,е”₁,....,е"_р).

Таким чином, відношення зв'язностівершин н-графа є відношенням еквівалентності, а значить розбиває всю множину вершин V(G) на неперетинаючи підмножини V_і., V(G) = UV_i, такі що вершини однієї й тієї ж множиин V_і. зв'язані друг з другом, а вершини з різних множин V_і и V_j не зв'язані між собою: .

Вершина, видалення якої збільшує число компонент зв'язності графу називається точкою зчленування. Ребро, видалення якого збільшує число компонент зв'язності називається мостом.

Для орієнтованих графів є паралельна термінологія.

Послідовність ребер, в якій кінець кожного попереднього ребра e_і-1 співпадає з початком наступного е_і, називається шляхом (у ньому всі ребра проходять згідно їх орієнтації). В шляху одне і те ж ребро може зустрітися кілька разів. Початком шляху є початок v₀ ребра е₁, кінцем шляху - кінець v_n ребра е_n.

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

Контур – шлях , в якому v₀ = v₁ . Контур називається циклом, якщо він є ланцюгом, и простим циклом, якщо це – простий ланцюг. Якщо граф містить цикли, тоді він містить і прості цикли. Граф, що не містить циклів, називається ациклічним.

Вершина називається досяжною з вершини , якщо існує шлях L(v',... ,v") з початком і кінцем v".

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

Число ребер маршруту (шляху) називається його довжиною.

Ейлерів цикл - цикл графа, що містить всі ребра графа. Ейлерів граф - граф, що має ейлерів цикл (ейлерів цикл можна визначити слідом пера, що вимальовує цей граф, не відокремлюючись від паперу).

Теорема Ейлера: для того, щоб у графі був ейлерів цикл необхідно та достатньо , щоб він був зв'язним і всі вершини мали парну степінь.

Ейлерів ланцюг – ланцюг, що містить всі ребра даного конечного н-графа G, але має різні початок v' і кінець v". Щоб в кінечному н-графі G була ейлерів ланцюг, необхідно та достатньо, щоб він був зв'язним і всі вершини мали парну степінь , крім початкової v' та конечної v".(v' та v" повинні мати непарну степінь). Щоб в конечному орграфі існував ейлерів цикл, необхідно та достатньо, щоб він був зв'язним, а також рівність степенів вершин цього графа по вхідним та вихідним ребрам, р, (v) = p₂ (v).

Гамілътонів цикл - простий цикл, що проходить через всі вершини графа. Гамілътонів ланцюг – простий ланцюг, що проходить через всі вершини графа, з початком і кінцем в різних вершинах .

Приклад 1. Для вершин v₁ і v₆ графа G на рис. 10 привести приклади маршруту, ланцюга, простого ланцюга; визначити в графі циклічний маршрут, цикл, простий цикл, прийняв вершину v₁ за їх початок та кінець.

Для вершин v₁ і v₆ :

• маршрут, що не є ланцюгом, – (е₁,е₂,е₃,е₄,е₅,е₁,e₈,e₇,e₆,e₁,e₈,е₇) або (е₁ ,е₂,е₃,е₄,е₅,е₁,e₈,e₇) та т.і.;

•ланцюг, але не простий ланцюг, – (е₁,е₂,е₃,е₄,е₅,е₆);

•простий ланцюг – (е₁, е₆) або (е₈, е₇).

•Для вершини v₁:

•циклічний маршрут, що не є циклом, - (е₁,е₂,е₃,е₄,е₅,е₁,e₈,e₇,e₆,e₁,e₈,е₇)

•цикл, що не є простим циклом, - (е₁,е₂,е₃,е₄,е₅,e₆,е₇,e₈)

• простий цикл - (е₁, е₆, е₇, e₈).

В якості початку і кінця циклу може бути вибрана будь-яка вершина, тому послідовності (е₁, е₆,е₇, е₈), (е₆,е₇,е₈, е₁), (е₇ , е₈, е₁, е₆), (e₈, е₁, е₆, е₇) є одним і тим самим циклом. Більш того, часто вважається, що можна міняти порядок ребер циклу на протилежний, тобто послідовність (e₈,e₇,e₆,е₁) є той же цикл.