Ім'я файлу: Завдання Звязність на графі.pdf
Розширення: pdf
Розмір: 184кб.
Дата: 26.10.2021

1. Матриці суміжності та інцидентності
Нехай D=(V,X) орієнтований граф, V={v
1
,...,v
n
}, X={x
1
,...,x
m
}.
Матриця суміжності орієнтованого графа D - квадратна матриця
A(D)=[a
ij
] порядку n, де )
( )
î
í
ì
Ï
Î
=
X
v
v
X
v
v
a
j
i
j
i
ij
,
,
0
,
,
1
Матриця інцидентності - матриця B(D)=[b
ij
] порядку n
´m, де
ï
î
ï
í
ì
-
-
-
-
=
,
0
,
,
1
,
,
1
j
i
j
i
j
i
ij
x
на
неінцидент
v
x
дуги
початок
v
x
дуги
кінець
v
b
Матрицею
суміжності неорієнтованого графа
G=(V,X)
називається квадратна симетрична матриця A(G)=[a
ij
] порядку n, де }
{ Для орієнтованого графа
ï
ï
î
ïï
í
ì
÷
ø
ö
ç
è
æ
÷
ø
ö
ç
è
æ
Ï
Î
=
X
j
v
i
v
X
j
v
i
v
ij
a
,
,
0
,
,
1
Матрицею інцидентності графа G називається матриця
A(G)=[a
ij
] порядку n
´m, де
î
í
ì
-
-
=
,
0
,
,
1
j
i
j
i
ij
x
ребру
на
неінцидент
v
x
ребру
інцидентна
v
b
2. Звязність, компоненти зв'язності
Підграфом графа G (орієнтованого графа D) називається граф, всі
вершини і ребра якого містяться серед вершин і ребер графа G (D).
Підграф називається власним, якщо він відмінний від самого графа.
Кажуть, що вершина w орієнтованого графа D (графа G) досяжна з вершини v, якщо або w=v, або існує шлях (маршрут) з v в Граф (орієнтований граф) називається зв'язковим (сильно зв'язковим), якщо для будь-яких двох його вершин v, w існує
маршрут (шлях, що з'єднує v і Компонентою

зв'язності графа (сильної зв'язності
орієнтованого графа D) називається його зв'язний (сильно зв'язний)
підграф, який не є власним подграфом ніякого іншого зв'язного
(сильно зв'язного) подграфа графа G (орієнтованого графа D).

3. Матриці досяжності і зв'язності
Нехай A(D) - матриця суміжності орієнтованого псевдографа
D=(V,X) (або псевдографа G=(V,X)), де V={v
1
,…, v
n
}. Позначимо через k -ту степінь матриці суміжності A(D).
Елемент a
(k)
ij
матриці A
k
орієнтованого псевдографа D=(V,X)
(псевдографа G=(V,X)) дорівнює числу всіх шляхів (маршрутів)
довжини k з v
i
у v
j
Матриця досяжності орієнтованого графа D - квадратна матриця
T(D)=[t
ij
] порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
,
1
випадку
іншому
у
v
з
досяжна
v
t
i
j
ij
Матриця сильної зв'язності орієнтованого графа D - квадратна матриця S(D)=[s
ij
] порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
1
випадку
іншому
у
v
з
досяжна
v
і
v
досяжназз
v
s
j
i
i
j
ij
Матриця зв'язності графа G - квадратна матриця порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
'
,
,
1
випадку
іншому
у
v
и
v
єднює
з
що
маршрут
існує
якщо
s
i
j
ij
Твердження 3. Нехай D=(V,X) - орієнтований граф, V={v
1
,…, v
n
},
A(D) - його матриця суміжності. тоді
1) T(D)=sign[E+A+A
2
+A
3
+… A
n-1
],
2) S(D)=T(D)
&T
T
(D) (T
T
-транспонована матриця,
&- поелементне множення).
Нехай G=(V,X) - граф, V={v
1
,…, v
n
}, A(G) - його матриця суміжності. тоді
S(G)=sign[E+A+A
2
+A
3
+… A
n-1
] (E - одинична матриця порядку n).
4. Компоненти сильної зв'язності орієнтованого графа
За допомогою матриці суміжності знайти компоненти сильної
зв'язності орієнтованого графа D.
Складаємо матрицю суміжності A(D) розмірності
n
n
´
(n - кількість вершин) для даного орієнтованого графа вона складається з нулів і одиниць, номери рядків - індекси вершин, з яких виходять дуги, номери стовпців - індекси вершин, в які дуги входять (якщо є
дуга, яка виходить із вершини v
i
і входить в v
j
, то елемент матриці
суміжності, що стоїть на перетині того рядка і того стовпця дорівнює 1, інакше - 0.).
Для того, щоб виділити компоненти сильної зв'язності, необхідно спочатку знайти матрицю досяжності T(D) орієнтованого графа по першій формулі затвердження 3, потім знаходимо матрицю сильної
зв'язності
S(D) орієнтованого графа (вона повинна бути симетричною) по другій формулі з того ж твердження Алгоритм виділення компонент сильної зв'язності

1. Надаємо p = 1 (p - кількість компонент зв'язності),
)
(
1
D
S
S
=
2. Включаємо в безліч вершин V
p
компоненти сильної зв'язності
D
p
вершини, відповідні одиницям першого рядка матриці S
p
. В якості
матриці A(D
p
) візьмемо підматрицю матриці A(D), що складається з елементів матриці A, що знаходяться на перетині рядків і стовпців,
відповідних вершин з V
p
3. Викреслюємо з S
p
рядки і стовпці, що відповідають вершинам з. Якщо не залишається жодного рядка (і стовбця), то p - кількість компонент сильної зв'язності. В іншому випадку позначимо залишилася після викреслювання термін і стовпців матрицю як S
p+1
,
присвоюємо p=p+1 і переходимо доп. 2.
Приклад
Виділимо компоненти зв'язності орієнтованого графа,
зображеного на рис. 6. У цьому завданню кількість вершин Мал. Значить, для даного орієнтованого графа матриця суміжності
матиме розмірність 5 × 5 і буде виглядати наступним чином 1
1 0
1 0
0 1
0 0
0 0
0 1
0 0
1 0
0 0
0 0
0 1
0
)
(D
A
Знайдемо матрицю досяжності для даного орієнтованого графа за формулою 1) з утвердження 3:

[
]
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
0 0
1 1
0 0
0 0
1 0
0 1
0 0
0 0
0 1
0 0
0 1
0 0
0
)
(
2
D
A
sign
,
[ ]
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
0 1
0 1
0 0
1 0
0 0
0 0
1 0
0 0
0 0
1 0
0 0
1 0
0
)
(
3
D
A
sign
,
[
]
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
0 1
1 0
0 0
0 1
0 0
0 0
0 1
0 0
1 0
0 0
0 0
0 1
0
)
(
4
D
A
sign
,
отже,
ï
ï
ï
î
ïï
ï
í
ì
+
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
+
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
+
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
0 0
1 1
0 0
0 0
1 0
0 1
0 0
0 0
0 1
0 0
0 1
0 0
0 0
1 1
0 1
0 0
1 0
0 0
0 0
1 0
0 1
0 0
0 0
0 0
1 0
1 0
0 0
0 0
1 0
0 0
0 0
1 0
0 0
0 0
1 0
0 0
0 0
1
)
(
sign
D
T
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
=
ï
ï
ï
þ
ïï
ï
ý
ü
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
+
÷
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
ç
è
æ
+
1 1
1 1
1 0
1 1
1 0
0 1
1 1
0 0
1 1
1 0
0 1
1 1
1 0
1 1
0 0
0 0
1 0
0 0
0 0
1 0
0 1
0 0
0 0
0 0
1 0
0 1
0 1
0 0
1 0
0 0
0 0
1 0
0 0
0 0
1 0
0 0
1 Таким чином, матриця сильної зв'язності, отримана за формулою) затвердження 3, буде такою 0
0 0
0 0
1 1
1 0
0 1
1 1
0 0
1 1
1 0
0 0
0 0
1 1
0 0
0 0
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
0 0
0 1
&
1 1
1 1
1 0
1 1
1 0
0 1
1 1
0 0
1 1
1 0
0 1
1 1
1
)
(D
S
Надаємо p=1
)
(
1
D
S
S
=
і складаємо безліч вершин першої
компоненти сильної зв'язності D
1
: це ті вершини, яким відповідають одиниці в першому рядку матриці S(D). Таким чином, перша компонента сильної зв'язності складається з однієї вершини
{ }
1 1
v
V
=
Викреслюємо з матриці S
1
(D) рядок і стовпець, відповідні
вершині v
1
, щоб отримати матрицю S
2
(D):

÷÷
÷
÷
÷
ø
ö
çç
ç
ç
ç
è
æ
=
1 0
0 0
0 1
1 1
0 1
1 1
0 1
1 1
)
(
2
D
S
Надаємо p=2. Множина вершин другої компоненти зв'язності
складуть ті вершини, яким відповідають одиниці в першому рядку матриці S
2
(D), тобто
{
}
4 3
2 2
,
,
v
v
v
V
=
. Складаємо матрицю суміжності
для компоненти сильної зв'язності
2
D
вихідного графа D - в її якості
візьмемо підматрицю матриці A(D), що складається з елементів матриці A, що знаходяться на перетині рядків і стовпців, відповідних вершин з V
2
:
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
0 1
0 0
0 1
1 0
0
)
(
2
D
A
Викреслюємо з матриці S
2
(D) рядки і стовпці, що відповідають вершинам з V
2
, щоб отримати матрицю S
3
(D), яка складається з одного елемента:
( і присвоюємо p=3. Таким чином, третій компонент сильної зв'язності
вихідного графа, як і перша, складається з однієї вершини
{ }
5 Таким чином, виділені 3 компоненти сильної зв'язності
орієнтованого графа D:
D
1
:
D
2
:
D
3
:

Завдання
За допомогою матриці суміжності знайти компоненти сильної
зв'язності орієнтованого графа D.
1.
2
3.
4
5.
6

7.
8
9.
10.
11.
12.

скачати

© Усі права захищені
написати до нас