Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 11 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

11
m
1
=4 m
3
=4
v= 1: L
0
={1}, L
1
={2,3}, L
2
={4,5}, L
3
={6,8}, L
4
={7};
v= 3: L
0
={3}, L
1
={1,4}, L
2
={2,5}, L
3
={6,8}, L
4
={7}.
Таким образом, вершины {1,3,7} – ППВ. Более того, они являются
периферийными, т.к. diam G = 4.
§7. Алгоритм отыскания вершины с большим значением эксцентриситета
Этот алгоритм хуже предыдущего, но лучше любого другого.
1) Выбираем некоторую вершину минимальной степени.
2) Строим СУС с корнем в этой вершине: L
0
, L
1
,…, L
k
.
3) Определяем компоненты связности последнего уровня L
k
построенной
структуры: L
k
, L
k
1
, L
k
2
, …, L
k
p
. Если такая компонента одна и состоит из
одной вершины, то алгоритм закончен, если нет, то идем на 4).
4) Для каждой компоненты связности находим вершину минимальной степени
и строим корневую структуру с корнем в этой вершине.
5) Из всех построенных структур выбираем структуру максимальной длины.
Корень этой структуры и будет искомой вершиной.
Задача 39.
Реализовать алгоритм отыскания вершины с большим значением
эксцентриситета для заданного графа G.
v = 10, m
10
= 3, L
3
= {2,4,5}.
v = 2 или v = 5: m
2
= m
5
= 4.
1
3
2
4
5
6
8
7
L
0
L
1
L
1
L
2
L
3
L
4
L
3
L
2
5)
1
3
2
4
5
6
8
7
L
1
L
0
L
L
1
L
3
L
4
L
3
L
2
3
1
6
10
9 2
11
8
4 7
5
L
1
L
2
L
2
L
3
L
3
L
2
L
2
L
3
L
2
L
1
L
0
3
1
6
10
9 2
11
8
4
7
5
L
3
L
2
L
1
L
0
L
1
L
2
L
3
L
4
L
3
L
2
L
3
                                                        11

      L0                L1                                       L1                L2
           1        2        L2      6    L3                           1       2        L2        6   L3
 5)
                             5                 7   L4                                   5                  7   L4
      L1                                                         L0
           3        4                8                                 3       4                  8
                        L2                L3                                       L1                 L3
                             m1=4                                                       m3=4
 v= 1: L0={1}, L1={2,3}, L2={4,5}, L3={6,8}, L4={7};
 v= 3: L0={3}, L1={1,4}, L2={2,5}, L3={6,8}, L4={7}.
  Таким образом, вершины {1,3,7} – ППВ. Более того, они являются
периферийными, т.к. diam G = 4.

§7. Алгоритм отыскания вершины с большим значением эксцентриситета
   Этот алгоритм хуже предыдущего, но лучше любого другого.
1) Выбираем некоторую вершину минимальной степени.
2) Строим СУС с корнем в этой вершине: L0, L1, , Lk.
3) Определяем компоненты связности последнего уровня Lk построенной
    структуры: Lk, Lk1, Lk2, , Lkp. Если такая компонента одна и состоит из
    одной вершины, то алгоритм закончен, если нет, то идем на 4).
4) Для каждой компоненты связности находим вершину минимальной степени
   и строим корневую структуру с корнем в этой вершине.
5) Из всех построенных структур выбираем структуру максимальной длины.
   Корень этой структуры и будет искомой вершиной.

Задача 39. Реализовать алгоритм отыскания вершины с большим значением
       эксцентриситета для заданного графа G.
           L1           L0           L1            L2             L3
                1             10          11                 8             5
                                                                                             L2
                                                                                             3

           L2   6       L2       9   L3   2        L3        4    L2       7

v = 10, m10 = 3, L3 = {2,4,5}.
           L3           L3           L2            L3             L4
                1             10          11                 8             5                L3
                                                                                             3

           L2   6       L1       9   L0   2        L1        4    L2       7


v = 2 или v = 5: m2 = m5 = 4.

Страницы