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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

7
каждый уровень.
В СУС каждый уровень L
i
является разделителем графа.
Опр. Разбиение на УС называется корневым, если для
=
==
=∀
∀∀
∀
−
−−
−
=
==
=
Υ
1
0
:
i
j
ji
LAdjLi i= (1,..,m), а множество L
0
⊂ V - корнем разбиения.
Опр.
Если L
0
состоит из одной вершины, то эта вершина называется корневой.
В дальнейшем будем считать разбиение на УС корневым.
Алгоритм построения СУС
1) Выбирается некоторая вершина v ∈ V, которая берётся в качестве
корневой. Полагаем i=0, L
0
={v}.
2) Присваиваем этой вершине первый номер.
3) Перебираем все вершины множества L
i
и для каждой его вершины
определяем ещё не помеченную, смежную ей вершину. Эти смежные
вершины образуют уровень L
i+1
. Они помечаются (нумеруются по порядку)
и помещаются в L
i+1.
4) Если множество непомеченных вершин пусто, то алгоритм закончен,
иначе i=i+1 и идём на 3).
Задача 34.
Построить СУС для графа G. Найти её длину и ширину.
L
0
: 1
L
1
: 6, 10
L
2
: 9, 11
L
3
: 7, 8
L
4
: 4, 5
L
5
: 2, 3
Длина структуры уровней
m
1
равна 5, ширина − 2.
§ 4. Алгоритм Катхилл-Макки уменьшения ширины ленты
1) Корневая вершина v∈V в графе G(V,E) выбирается из множества вершин,
имеющих минимальную степень, и ей присваивается первый номер (т. е.
ставим соответствующую строчку на первое место): v→v
1
, L
0
={v
1
}.
2) Строится СУС с корнем v
1.
Для каждого номера i после построения УС L
i
перебираются все вершины, входящие в L
i
(при этом все вершины множеств
L
0
, L
1
,…, L
i-1
уже перенумерованы), и им присваиваются очередные
порядковые номера в порядке возрастания их степеней.
3
5
2
7
8
L
1
L
2
L
5
L
3
L
3
L
5
L
4
2
10
7
11
L
1
3
4
5
L
4
9
1
L
0
L
2
4
1
10
6
9
11
8
6 
                                     7


 каждый уровень.
   В СУС каждый уровень Li является разделителем графа.
Опр.     Разбиение           на   УС называется корневым, если для
                 i −1     
  ∀ i : Li = Adj 
                  Υ   L j 
                            i= (1,..,m), а множество L0 ⊂ V - корнем разбиения.
                 j =0 
Опр. Если L0 состоит из одной вершины, то эта вершина называется корневой.

    В дальнейшем будем считать разбиение на УС корневым.

                               Алгоритм построения СУС

1) Выбирается некоторая вершина v ∈ V, которая берётся в качестве
   корневой. Полагаем i=0, L0={v}.
2) Присваиваем этой вершине первый номер.
3) Перебираем все вершины множества Li и для каждой его вершины
    определяем ещё не помеченную, смежную ей вершину. Эти смежные
    вершины образуют уровень Li+1. Они помечаются (нумеруются по порядку)
    и помещаются в Li+1.
4) Если множество непомеченных вершин пусто, то алгоритм закончен,
   иначе i=i+1 и идём на 3).

Задача 34. Построить СУС для графа G. Найти её длину и ширину.
        1           L1
                          3          L3
                                          7
   L0       1       10                                   L0: 1
                                      8                  L1: 6, 10
                              L2
                                              L4         L2: 9, 11
                                                    9
   L1       6   2             11               5         L3: 7, 8
                                   L3 7
                         5
                                          6              L4: 4, 5
                                                         L5: 2, 3
   L2       9                  2     4         3        Длина структуры уровней
                         10               8        11
                4
                              L5     L4       L5        m1 равна 5, ширина −2.

        § 4. Алгоритм Катхилл-Макки уменьшения ширины ленты

1) Корневая вершина v∈V в графе G(V,E) выбирается из множества вершин,
   имеющих минимальную степень, и ей присваивается первый номер (т. е.
   ставим соответствующую строчку на первое место): v→ v1, L0={v1}.
2) Строится СУС с корнем v1. Для каждого номера i после построения УС Li
    перебираются все вершины, входящие в Li (при этом все вершины множеств
    L0, L1, , Li-1 уже перенумерованы), и им присваиваются очередные
    порядковые номера в порядке возрастания их степеней.

Страницы