Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 10 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

10
Рис.4. Кольцевая сумма графов G
1
, G
2
Лабораторное задание
1. Выполните генерацию матриц M
1
, М
2
смежности неориентированных
помеченных графой G
1
, G
2
. Метки вершин выберите из подмножества
натуральных чисел {1, 2, …, n}. Порядок графов, определяется
преподавателем. Вычислите матрицу смежности дополнительного графа
(дополнения)
¬ G
1
. Порядок графа п определяется преподавателем.
2. Вычислите матрицы смежности подграфов Н, Q графа G
1
(¬ G
1
).
Например:
H = G
1
- v
i
, i = 1, 2,..., n;
Q = G
1
- v
i
- v
j
, i = 1, 2,..., n, i
≠
j.
3. Выполните операцию отождествления вершин (стягивания ребра,
расщепления вершины) в графе G
1
(
¬
G
1
), Номера выбираемых для
выполнения операции двух вершин (вершины) согласуйте с
преподавателем.
4. Выполните операцию объединения (пересечения, кольцевой суммы)
графов G = G
1
∪ G
2
(G = G
1
∩
G
2
,
G = G
1
⊕
G
2
).
5. Выполните операцию декартова произведения графов G = G
1
X G
2
,
i = 1,2
Содержание отчета
1. Матричные и графические представления графов G
1
(¬G
1
),Н,Q,,G
2
, G
3
.
⊕
v
1
v
2
v
3
v
5
v
3
v
4
v
6
v
2
v
1
v
4
v
5
v
1
v
4
v
6
v
5
v
3
v
2 
                  v1          v2        v1          v2      v1         v2


                                    ⊕
                  v3           v4       v3          v4      v3         v4


                  v5           v6    v5             v6      v5


                       Рис.4. Кольцевая сумма графов G1, G2
                             Лабораторное задание
 1. Выполните генерацию матриц M1, М2 смежности неориентированных
помеченных графой G1, G2. Метки вершин выберите из подмножества
натуральных    чисел       {1, 2, …, n}.          Порядок    графов,        определяется
преподавателем. Вычислите матрицу смежности дополнительного графа
(дополнения) ¬ G1. Порядок графа п определяется преподавателем.
 2. Вычислите матрицы смежности подграфов Н, Q графа G1( ¬ G1).
 Например:
                            H = G1 - vi, i = 1, 2,..., n;
                       Q = G1 - vi - vj, i = 1, 2,..., n, i ≠ j.
 3. Выполните операцию отождествления вершин (стягивания ребра,
расщепления вершины) в графе G1( ¬ G1), Номера выбираемых для
выполнения    операции        двух           вершин      (вершины)     согласуйте       с
преподавателем.
 4. Выполните операцию объединения (пересечения, кольцевой суммы)
графов G = G1 ∪ G2 (G = G1 ∩ G2, G = G1 ⊕ G2).
 5. Выполните операцию декартова произведения графов G = G1                        X   G2,
i = 1,2
                               Содержание отчета
 1. Матричные и графические представления графов G1( ¬ G1),Н,Q,,G2, G3.




                                             10

Страницы