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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Лабораторная работа № 1
МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ И ХАРАКТЕРИСТИКИ ГРАФОВ
Цель работы - изучение форм представления графов на основе
матриц и вычисление их характеристик на ЭВМ.
Основные понятия и определения
Пусть G - связный помеченный граф, содержащий непустое
множество вершин V и множество ребер U
G V E
,
( )
.
Вершинам графа присвоены метки из подмножества натуральных
чисел {1,2,…}. Выделим в графе G две несовпадающие вершины v
i
; и v
j
.
Длина кратчайшего маршрута (простой цепи) между v
i
; и v
j
называется
расстоянием между вершинами и обозначается через l(v
i
; v
j
). Для
фиксированной вершины v
i
; величина
e v
i
( )
T
j
l v
i
v
j
,
( )( )
←
v
j
V
∈
for
s max T( )
←
s
:=
называется эксцентриситетом вершины v
i
.
Максимальный среди всех эксцентриситетов эксцентриситет
вершины называется диаметром графа G и обозначается через D(G).
D G( )
K
i
e v
i
( )( )
←
v
i
V
∈
for
s max K( )
←
s
:=
Следовательно, вершина v
i
называется периферийной, если e(v
i
) =
d(G). Простая цепь длины d(G) называется диаметральной цепью.
4
                       Лабораторная работа № 1
МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ И ХАРАКТЕРИСТИКИ ГРАФОВ
     Цель работы - изучение форм представления графов на основе
матриц и вычисление их характеристик на ЭВМ.
                   Основные понятия и определения
     Пусть G - связный помеченный граф, содержащий непустое
множество вершин V и множество ребер U

                                         G       ( V, E)            .
     Вершинам графа присвоены метки из подмножества натуральных
чисел {1,2,…}. Выделим в графе G две несовпадающие вершины vi; и vj.
Длина кратчайшего маршрута (простой цепи) между vi; и vj называется
расстоянием между вершинами и обозначается через l(vi; vj). Для
фиксированной вершины vi; величина

                              ( i)
                          e v :=         for v ∈ V
                                                          j
                                             T ←
                                                  j               ( l( v i, v j) )
                                         s ← max( T )
                                         s

называется эксцентриситетом вершины vi.
     Максимальный     среди      всех            эксцентриситетов                    эксцентриситет
вершины называется диаметром графа G и обозначается через D(G).
                              D( G) :=       for v ∈ V
                                                              i
                                                 K ←
                                                      i            ( e( vi) )
                                             s ← max( K)
                                             s

     Следовательно, вершина vi называется периферийной, если e(vi) =
d(G). Простая цепь длины d(G) называется диаметральной цепью.




                                         4

Страницы