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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

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




                                        4

Страницы