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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

6
называется концевым. Вершина графа, смежная с каждой другой его
вершиной, называется доминирующей.
Лабораторное задание
1. Осуществите генерацию матрицы смежности M(G)
неориентированного графа G,
MG()
x
ij,
rnd 1( ) 0.5−←
M
ij,
if x
ij,
0.5< 0, 1,
()
←
M
ji,
M
ij,
←
jin..∈for
i1n
.
.
∈
for
M
:=
где n - порядок помеченного графа.
2. Определите радиус и диаметр графа G, используя матрицу смежности
графа M(G) и
алгоритм вычисления эксцентриситета вершины.
3. Определите подмножества периферийных и центральных вершин
графа G, используя матрицу смежности M(G)
4. Определите список степеней вершин графа, изолированные, концевые
и доминирующие вершины.
5. Постройте для графа G матрицу инцидентности A(G). Выполните п.4,
используя представление графа и форме матрицы инцидентности.
6. Постройте для графа G матрицу
Кирхгофа B(G).
Содержание отчета
Протокол решения задач по всем пунктам лабораторного задания
средствами системы MathCAD. 
называется концевым. Вершина графа, смежная с каждой другой его
вершиной, называется доминирующей.
                             Лабораторное задание
 1. Осуществите        генерацию                   матрицы          смежности   M(G)
неориентированного графа G,


                  M( G) :=    for i ∈ 1 .. n
                                 for j ∈ i.. n
                                    x       ← rnd ( 1) − 0.5
                                     i, j
                                    M
                                        i, j
                                               ← if x( i, j < 0.5, 0, 1)
                                    M          ←M
                                        j, i         i, j
                             M

где n - порядок помеченного графа.
 2. Определите радиус и диаметр графа G, используя матрицу смежности
графа M(G) и алгоритм вычисления эксцентриситета вершины.
 3. Определите подмножества периферийных и центральных вершин
графа G, используя матрицу смежности M(G)
 4. Определите список степеней вершин графа, изолированные, концевые
и доминирующие вершины.
 5. Постройте для графа G матрицу инцидентности A(G). Выполните п.4,
используя представление графа и форме матрицы инцидентности.
 6. Постройте для графа G матрицу Кирхгофа B(G).
                              Содержание отчета
     Протокол решения задач по всем пунктам лабораторного задания
средствами системы MathCAD.




                                               6

Страницы