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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Минимальный из эксцентриситетов вершин связного графа G
называется его радиусом и обозначается через r(G). Вычисление значения
радиуса осуществляется по формуле
r G( )
K
i
e v
i
( )
←
v
i
V
∈
for
s min K( )
←
s
:=
Вершина v
i
называется центральной, если e(v
i
) = r(G). Множество
всех центральных вершин графа называется его центром. Граф G может
иметь единственную центральную вершину или несколько центральных
вершин.
Степенью вершины графа G называется число инцидентных ей
ребер. Степень вершины v
i
: обозначается через deg(v
i
). Максимальная и
минимальная степени вершиy графа G обозначаются символами Δ(G), δ(G)
соответственно:
∆
G( )
K
i
deg v
i
( )
←
v
i
V
∈
for
s max K( )
←
s
:=
δ
G( )
K
i
deg v
i
( )
←
v
i
V
∈
for
s min K( )
←
s
:=
.
Список степеней вершин графа называется его степенней
последовательностью. Порядок членов в последовательности роли не
играет. Вершина степени 0 называется изолированной, степени 1 —
концевой (висячей). Ребро, инцидентное концевой вершине, также
5
     Минимальный из эксцентриситетов вершин связного графа G
называется его радиусом и обозначается через r(G). Вычисление значения
радиуса осуществляется по формуле

                                           r( G) :=       for v ∈ V
                                                                   i
                                                              K ← e v
                                                               i        ( i)
                                                          s ← min ( K)
                                                          s


     Вершина vi называется центральной, если e(vi) = r(G). Множество
всех центральных вершин графа называется его центром. Граф G может
иметь единственную центральную вершину или несколько центральных
вершин.
     Степенью вершины графа G называется число инцидентных ей
ребер. Степень вершины vi: обозначается через deg(vi). Максимальная и
минимальная степени вершиy графа G обозначаются символами Δ(G), δ(G)
соответственно:


                  ∆ ( G) :=   for v ∈ V                        δ ( G) :=       for v ∈ V
                                       i                                                i
                                  K ← deg v
                                   i             ( i)                              K ← deg v
                                                                                    i        ( i)
                              s ← max( K)                                      s ← min ( K)
                              s                                                s
                                                                                                     .
     Список   степеней            вершин              графа            называется           его     степенней
последовательностью. Порядок членов в последовательности роли не
играет. Вершина степени 0 называется изолированной, степени 1 —
концевой (висячей). Ребро, инцидентное концевой вершине, также




                                                      5

Страницы