Задачі на теорію графів
Задача 1.Для графа G = (Y, V) побудувати матриці суміжностей та інцидентностей, і по матриці суміжностей - матрицю досяжності.
Рішення:
Матриця суміжності: Матриця інцидентності:
Матриця досяжності: Матриця контрдосяжності:
Задачі для самостійної роботи студентів
Які із запропонованих графів є регулярними?
Опишіть матриці суміжності повних графів, цілком незв'язних графів. Що можна сказати про матрицю простого графа і його доповнення?
З
образите
матриці суміжності, інцидентності
наступних графів:
Дано матрицю суміжності. Зобразите граф, їй відповідний.
1
2
3
4
5
6
7
1
0
0
1
1
0
1
0
2
0
0
0
0
1
0
1
3
1
0
0
1
0
1
0
4
1
0
1
0
1
0
1
5
0
1
0
1
0
0
1
6
1
0
1
0
0
0
0
7
0
1
0
1
1
0
0
Дано матрицю інцидентності. Зобразите граф, їй відповідний.
1
2
3
4
5
E1
1
0
0
0
1
E2
0
1
0
0
1
E3
0
0
0
1
1
E4
0
0
1
1
0
E5
0
0
1
0
1
E6
0
1
0
1
0
E7
1
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
1
0
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
1
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
1
1
1
1
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
Установить, які з наступних матриць є матрицями суміжностей простого графа, які - матрицями інцидентностей й які не є ні тими, ні іншим.1
0
0
1
0
1
0
1
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
р Дано матрицю суміжності. Зобразити граф, їй відповідний.
а) б)
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 | ||||||||||||
|
|
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 | ||||||||||||
|
|
3 |
1 |
0 |
0 |
1 |
0 |
1 |
0 | ||||||||||||
|
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
1 | ||||||||||||
|
|
5 |
1 |
1 |
1 |
0 |
0 |
0 |
1 | ||||||||||||
|
|
6 |
1 |
0 |
1 |
1 |
0 |
1 |
0 | ||||||||||||
|
|
7 |
0 |
1 |
0 |
0 |
1 |
0 |
0 | ||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
|
|
|
|
|
| ||||||||||||||
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
2 |
0 |
0 |
1 |
|
2 |
0 |
0 |
3 |
0 |
0 |
|
3 |
0 |
0 |
2 |
1 |
0 |
|
4 |
1 |
0 |
1 |
0 |
1 |
|
5 |
1 |
0 |
0 |
0 |
0 |