Елементи теорії графів. Для 1к

35

Ланцюги, цикли, шляхи та контури графа

Ланцюги та цикли – для неографа, шляхи й контури – для орграфа.

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

Ланцюг: елементарний – немає повторення ні вершин, ні ребер [ 1) ]

простий – допускається повторення вершин [ 2) ]

складний – допускається повторення вершин і ребер [ 3) ]

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

36

Орграф

Шлях – шлях для орграфа.

< g1, g2, g3, g5, g2, g3, g4 > - 7 дуг

Контур – поняття для орграфа (аналогічне циклу неографа).

Довжина шляху – кількість дуг, що складають цей шлях.

Частковий граф, підграф, частковий підграф.

Частковий граф (суграф) H графа G отримуємо з графа G викреслюванням тільки ребер (дуг)

38

1.Зв’язний неограф має одну компоненту зв’язності, якою він і є.

2.Незв’язний неограф складається з компонент зв’язності.

Орграф

1) Орграф називається сильно зв’язним, якщо для будь-якої пари вершин xi , xj

існують шляхи з xi → xj та xj → xi.

2) Орграф називається не сильно зв’язним, якщо для <xi , xj> існує або xi → xj, або xj → xi.

Х1 Х3 Х1 Х3

Орграф, що не задовольняє умові 1), називається незв’язним.

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

Висновки:

1. Сильно зв'язний орієнтований граф сам є компонентою сильної зв'язності.

40

Алгоритм Мальгранжа-Томеску

1.Подати граф матрицею суміжності R.

2.Доповнити матрицю зліва стовпчиком xi и знизу рядком xi 1 .

3.Отримати за деяким алгоритмом xi , потім xi 1 .

4.Отримати компоненту сильної зв'язності за формулою C(xi ) xi xi 1 .

5.З матриці R викреслити строки та стовпці, що відповідають вершинам, що увійшли до С(хi).

6.Алгоритм продовжувати до тих пір, поки не будуть викреслені усі строки та стовпці матриці.

Алгоритм заповнення стовпця σ*хi та рядку σ*хi ‾ ¹

1. У комірці стовпця xi для вершини хi, що відповідає рядку хi матриці

суміжності R, поставити 0.

2.Якщо у матриці R на перетині рядка хi та стовпця хj, хk, хl,… , стоять одиниці, то в комірках стовпця xi , відповідних рядкам хj, хk, хl,… , поставити 1.

3.Якщо в матриці R на перетині строк хj, хk, хl,… , з стовпцями хp, хm,…, хq стоять 1,

то у комірках стовпця xi , відповідних рядкам хp, хm,…, хq матриці R поставити 2.

4. Процес заповнення комірок стовпця xi продовжується до використання усіх доступних рядків матриці.

5. Процес заповнення рядка xi 1 аналогічний алгоритму заповнення стовпця

xi , але розглядаються не рядки, а стовпці.

X2 X4

X1

X6

41

X3 X5

С(x1) = { x1, x2, x3, x4, x6 } ∩ { x1, x2, x3 } С(x1) = { x1, x2, x3 }

С(x4) = { x4, x6 } ∩ { x4, x5 } = { x4 } С(x5) = { x5, x6 } ∩ { x5 } = { x5 } С(x6) = { x6 }

42

Дерева та ліси

Дерево – скінченний зв'язний граф, що містить щонайменше 2 вершини та не містить циклів.

Ліс – незв'язний граф, кожна компонента зв'язності котрого є деревом.

Лагранжеве дерево – дерево, усі гілки якого мають спільну вершину.

Прадерево – орієнтований граф с коренем у вершині и такий, що в кожну вершину, окрім вершини Х1 , входить рівно одна дуга, а у вершину Х1 не входить жодна дуга.

Ізоморфізм

Два графа називаються ізоморфними, якщо вони можуть бути зображені

геометрично однаково з точністю до позначень або номерів вершин.

43

Цикломатичне число графа та його застосування

Нехай граф G = (Х, δ) має n вершин та m ребер.

Скелет (остов) графа – дерево, гілки якого (ребра графа) інцидентні усім вершинам графа.

Будь-який остов має (n-1) ребро.

Граф може містити декілька остовів:

G 2

Якщо до остову графа додати одне ребро, яке не входить в остов, то утвориться цикл з участю цього ребра.

Такий цикл називається фундаментальним циклом. Фундаментальні цикли – елементарні.

Приклад. Граф G має 6 вершин та 8 ребер. Остов (1) має 6 вершин та 5 ребер.

Остов (2) має n = 6 вершин та n-1 = 5 ребер. Ребра 1, 2, 3 не входять до остова.

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

Це число називається цикломатичним числом і позначається υ(G), G m n 1.

Цикломатичне число дозволяє підрахувати усі можливі цикли графа.

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

44

Приклад для остова (1):

Правило заповнення матриці:

На перетині рядка Фi та стовпця j ставиться 1, якщо ребро з індексом j належить фундаментальному циклу.

Будь-який цикл графу утворюється як лінійна комбінація (сума по модулю 2) векторів фундаментальних циклів. При цьому лінійна комбінація може утворювати структуру, що не є циклом.

Число усіх можливих циклів 2 (G) 1. (У прикладі (G) 3 , 23 1 7 ).

Розрізи у графах

1.Розріз графа модульної схеми на дане число підсхем.

2.Розріз на довільне число підсхем з приблизно рівним числом вершин у кожній підсхемі.

3.Область застосування

Розріз – це множина ребер, видалення яких з графа подає скінченний незв'язний граф, що складається щонайменше з 2-х компонент зв'язності. Розріз позначається

Ki.

4 2 Х4 7

Х3 Х6