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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

5
Минимальный из эксцентриситетов вершин связного графа G
называется его радиусом и обозначается через r(G). Вычисление значения
радиуса осуществляется по формуле
rG()
K
i
ev
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 —
концевой (висячей). Ребро, инцидентное концевой вершине, также 
     Минимальный из эксцентриситетов вершин связного графа G
называется его радиусом и обозначается через r(G). Вычисление значения
радиуса осуществляется по формуле

                                   r( G) :=        for v ∈ V
                                                            i
                                                       K ←ev
                                                        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

Страницы