Анализ графов на ЭВМ - 6 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

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

Страницы