Суміжність, інцидентність графів, ізоморфізм графів

Дві вершини v_i, v_j Î V графа G=(V,E) називаються суміжними, якщо вони є граничними вершинами ребра e_kÎE. Відношення суміжності на множині вершин графа можна визначити, представивши кожне ребро як пару суміжних ребер e_k=(v_i, v_j), k=1,2,…,q. Для неорієнтованих графів такі пари невпорядковані. Граф можна представити матрицею суміжності. Рядки і стовпці матриці відповідатимуть вершинам графа, її (i,j) елемент дорівнює кількості кратних ребер, що зв’язують вершини v_i, v_j. Наприклад, для графа (рис. 3.3.1) маємо

v1	v2	v3	v4	v5
	1				v1
1		2		1	v2
	2			1	v3
					v4
	1	1		1	v5

 

Матриця суміжності неорієнтованого графа завжди симетрична, а орієнтованого, як правило, несиметрична. У стовпцях і рядках відповідно ізольованих вершин усі елементи рівні 0. Елементи матриці простого графа дорівнюють 0 або 1, причому всі елементи головної діагоналі – 0.

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

Інцидентність графів. Якщо вершина v_i є кінцем ребра e_k, то говорять, що вони інцидентні (вершина інцидентна ребру, ребро інцидентне вершині). У той час як суміжність являє собою відношення між однорідними об¢єктами (вершинами), інцидентність – відношення між різнорідними об¢єктами (вершинами і ребрами). Інцидентність для (p, q) -графа можна представити матрицею розміру p´ q. Для неорієнтованого графа елементи цієї матриці визначаються за таким правилом: (i,j) елемент дорівнює 1, якщо v_i інцидентна ребру e_i, і дорівнює 0, якщо вони не інцидентні. У випадку орграфа дорівнює 1, якщо v_i початкова вершина ребра, й дорівнює (– 1), якщо v_i кінцева вершина, наприклад, інцидентна матриця для графа (рис. 3.3.1).

Кожний стовпець матриці інцидентності містить обов’язково два одиничних елементи. Кількість одиниць у рядку дорівнює степеню відповідної вершини. Нульовий рядок відповідає ізольованій вершині, а нульовий стовпець – петлі.

e1	e2	e3	e4	e5	e6
1						v1
1	1	1	1			v2
	1	1		1		v3
						v4
		1	1			v5

Ізоморфізм графів. Графи, для яких зберігається відношення інцидентності, називаються ізоморфними. Приклад ізоморфних графів наведено на рисунку 3.4.1.

Рис. 3.4.1. Ізоморфні графи.

Графи, які мають однакові накреслення і відрізняються лише нумерацією вершин та ребер, не будучи тотожними, є ізоморфними.

Маршрути, цикли графів

Нерідко задача на графах потребує виділення різних маршрутів, що мають певні властивості та характеристики. Маршрути довжиною m ребер (не обов’язково різні) таких, що граничні вершини двох сусідніх ребер збігаються (рис 3.2.1).

Приклад

(e₁, e₃, e₂, e₅) –з’єднує v_{1 ,}v₅

(e₅, e₆, e₄, e₄) –з’єднує v_{3 ,}v₅

Замкнутий маршрут приводить у ту ж вершину, з якої він почався.

Маршрут, усі ребра котрого різні, називається ланцюгом, а маршрут, для якого різні всі вершини, називається простим ланцюгом. Замкнутий ланцюг називається циклом, а простий ланцюг – простим циклом, наприклад, (e₂, e₅, e₆) – ланцюг, (e₁, e₂, e₅) –простий ланцюг, (e₂, e₃, e₄, e₅) – цикл, (e₂, e₄, e₅) – простий цикл.

Цикл, який містить усі ребра графа, називається ейлеровим циклом, а граф, що містить такий цикл, називається ейлеровим графом. Простий цикл, котрий проходить через усі вершини графа, називається гамільтоновим.

Маршрут, який не містить дуг, котрі повторюються, називається шляхом, а той, що не містить вершин, які повторюються, – простим шляхом. Замкнений шлях називається контуром, а простий замкнений шлях – простим контуром.

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

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

Рис. 3.5.1. Зв’язний граф

Планарність графів. Граф називається плоским, якщо існує ізоморфний йому граф, і він може бути зображений на площині без перетину ребер. На рисунку 3.5.3, хоча ребра графа перетинаються, ізоморфні йому графи не мають перетину ребер.

Два графи (так звані графи Понтрягіна – Куратовського) відіграють фундаментальну роль у теорії планарності.

а) б)

Рис. 3. 5. 2. Графи Понтрягіна – Куратовського: а) повний п’ятикутник, б) дводольний граф

Дводольний граф (рис. 3.5.2, б) є моделлю відомої задачі про три будинки і про три криниці: чи можна від кожної криниці до кожного будинку прокласти дороги так, щоб вони не перетиналися? Планарність є суттєвою властивістю графів, які моделюють комунікаційні зв’язки між об’єктами на площині (дороги між населеними пунктами, водопровідні, газопровідні мережі, лінії передач електроенергії, міжз’єднання на печатних платах електронних приладів і кристалах інтегральних схем). Плоскими графами є різні карти, з якими пов¢язана відома проблема чотирьох фарб: чи можна пофарбувати області, на котрі плоский граф поділяє поверхню, так, щоб ніякі дві суміжні області не були пофарбовані в однаковий колір і щоб при цьому було використано не більше від чотирьох кольорів?

Контрольні запитання

1. Розкрити поняття графа. Застосування графів.

2. Дати поняття орграфа, степінь вершини.

3. Які існують типи графів?

4. Розкрити поняття суміжності, інцидентності графів.

5. Розкрити поняття орграфа ізоморфізму графа.

6. Що являє собою маршрут графа?

7. Що називається планарним графом?

 

Лекція 4

Аналіз систем на основі поняття відношення. Властивості бінарних відношень. Нечіткі відношення

1. Визначення впорядкованої пари та декартового добутку.

2. Бінарні відношення. Способи задавання перерізів.

3. Властивості бінарних відношень.

4. Функціональні відношення.

5. Нечіткі відношення.