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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

10
§6. Алгоритм отыскания ППВ графа
Алгоритм Катхилл-Макки будет работать эффективнее, если в качестве
стартовой брать не вершину с минимальной степенью, а периферийную
вершину. Но известные алгоритмы отыскания периферийных вершин весьма
трудоемки, а для отыскания ППВ существуют более эффективные алгоритмы,
которые в большинстве случаев позволяют находить и периферийные вершины.
Алгоритм
1) Выбираем в исходном графе G некоторую вершину v минимальной степени
из V.
2) Строим СУС с корнем в выбранной вершине v: L
0
, L
1
, …,L
k
.
3) Выделяем множество L
k
(последний уровень) и для каждой
вершины из L
k
= {v
1
(k)
, v
2
(k)
, …, v
p
(k)
} строим свою корневую СУС с корнем
в этой вершине:
v
1
(k)
: L
0
1,k
, L
1
1,k
, …L
S
1
1,k
v
2
(k)
: L
0
2,k
, L
1
2,k
, …L
S
2
2,k
…………………………………….
v
p
(k)
: L
0
p,k
, L
1
p,k
, …L
S
p
p,k
4) Из всех построенных на 3) структур выбираем структуру максимальной
длины, и если длина S
i
этой структуры больше k, то полагаем k = S
i
и v = v
i
(то есть корень этой структур ы рассматриваем в качестве кандидата на ППВ).
5) Полагаем
Υ
P
i
ki
Sk
i
LL
1
,
=
==
=
=
==
=
(то есть объединяем последние уровни всех структур,
построенных на шаге 3).
6) Переходим к 3). Если в течение двух таких переходов длина максимальной
СУС не увеличилась, то вершина является ППВ, и алгоритм заканчивает
свою работу.
Задача 38
.
Реализовать алгоритм отыскания ППВ для графа G.
m
2
=3
m
7
=4
v= 2: L
0
={2}, L
1
={1,5}, L
2
={3,4,6,8}, L
3
={7};
v= 7: L
0
={7}, L
1
={6,8}, L
2
={5}, L
3
={2,4}, L
4
={1,3};
1
3
2
4
5
6
8
7
L
1
L
2
L
0
L
2
L
2
L
3
L
2
L
1
1-2
)
1
3
2
4
5
6
8
7
L
4
L
4
L
L
3
L
1
L
0
L
1
L
2
3-4
)
                                                    10

                              §6. Алгоритм отыскания ППВ графа

  Алгоритм Катхилл-Макки будет работать эффективнее, если в качестве
стартовой брать не вершину с минимальной степенью, а периферийную
вершину. Но известные алгоритмы отыскания периферийных вершин весьма
трудоемки, а для отыскания ППВ существуют более эффективные алгоритмы,
которые в большинстве случаев позволяют находить и периферийные вершины.
                                               Алгоритм

1) Выбираем в исходном графе G некоторую вершину v минимальной степени
   из V.
2) Строим СУС с корнем в выбранной вершине v: L0, L1, ,Lk.
3) Выделяем множество Lk (последний уровень) и для каждой
   вершины из Lk = {v1(k), v2(k), , vp(k)} строим свою корневую СУС с корнем
   в этой вершине:
                             v1(k): L01,k, L11,k, LS 1 1,k
                             v2(k): L02,k, L12,k, LS 2 2,k
                                                                     .

                              vp(k): L0p,k, L1p,k, LS p p,k
4) Из всех построенных на 3) структур выбираем структуру максимальной
   длины, и если длина Si этой структуры больше k, то полагаем k = Si и v = vi
   (то есть корень этой структуры рассматриваем в качестве кандидата на ППВ).
                          P
5) Полагаем Lk = Υ LiS, ik (то есть объединяем последние уровни всех структур,
                         i =1
   построенных на шаге 3).
6) Переходим к 3). Если в течение двух таких переходов длина максимальной
   СУС не увеличилась, то вершина является ППВ, и алгоритм заканчивает
   свою работу.

Задача 38. Реализовать алгоритм отыскания ППВ для графа G.

       L1           L0                                      L4               L3
            1   2                 6   L2                                                      L1
                          L1                                     1       2                6
1-2)                                                                              L2
                           5               7   L3    3-4)
       L2                                                                         5                7   L0
                                                            L4
            3   4                 8
                    L2                L2                         3       4                8
                                                                             L3               L1
                           m2=3                                                    m7=4

  v= 2: L0={2}, L1={1,5}, L2={3,4,6,8}, L3={7};
  v= 7: L0={7}, L1={6,8}, L2={5}, L3={2,4}, L4={1,3};

Страницы