Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 50

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Поставим в соответствие триангуляции T нео-риентированныйтраф G = (Т, U), где T = (Т1,..., T M ) множество вершин и U = uN"^) множество ребер графа, Nu общее количество ребер (рис. 2.) по следующим правилам:

1) каждому треугольнику Tk <eT соответствует вершина Tk є G, k = 1, M ;

2) если два треугольника Tp єT и Tq єT име­ют общую сторону, то вершины Tp єG и Tq єG объединены ребром U = (Тр,Tq).

Граф G обладает следующими свойствами:

1) из каждой вершины графа G выходит не бо­лее трёх ребер, так как треугольник имеет не более трёх сторон, имеющих общую сторону с другими треугольниками;

2) всегда существуют вершины, имеющие менее трёх смежных ребер. Этим вершинам соответствуют треугольники, образующие границу триангуляции.

Задача построения четырехугольной карты эк­вивалента задаче построения остового леса Ol єО графа G , где О множество всех остовных лесов, i єN . В остовном лесе все вершины попарно со­единены, при этом из каждой вершины выходит одно и только одно ребро. Построение всех остов-ных лесов О схоже с построением всех остовых де­ревьев графа G [6].

Построение всех остовых лесов О заключается в построении графа D , вершинами которого явля­ются ребра {и' |ui єG,uU єО^ из графа G , принад­лежащие остовому лесу О!. Процедура построе­ния позволяет найти все остовые леса О1 графа G , образованные объединением ребер в вершинах ветвей графа D . На рис. 3 приведен пример по­строения графа D для графа G (рис. 2б), а на рис. 4 представлен процесс построения остовного леса на каждой итерации.

Процедура построения остовных лесов О.

1) Установим вершину графа D с пустым мно­жеством ребер графа G.

2) Найдем среди всех вершин графа G такие вершины Th єG , из которых выходит одно и толь­ко одно ребро uh є U . Эти ребра принадлежат ос­

а

Рис. 2. а

товному лесу (uh єО1) и помещаются в вершину графа D.

3) Если таких вершин в графе G нет, выбираем любую вершину T' єG , имеющую два смежных ребра U,U єи (по свойству 2 графа G такая вер­шина существует) и рассмотрим два случая при­надлежности остовому лесу ребер U єО1 и U є О1. При этом имеем раздвоение графа D на две ветви. В каждую новую вершину графа D помещаем рас­сматриваемое ребро.

4) Удаляем из графа G

а) ребра, принадлежащие остовому лесу,

б) вершины, в которые входят удаленные ре­бра,

в) все ребра, которые выходят из удаленных вершин.

5) Если в графе G не осталось ни одной верши­ны, то остовые леса О построены.

6) Если в подмножестве вершин графа G , из которых исходят удаленные ребра на шаге 4в, об­разовались изолированные вершины (вершины, из которых не исходит ни одно ребро), то остовой лес при данном выборе вершин в шагах 3 или 7 не существует, и данную ветвь в графе D далее не следует рассматривать. Если эта ветвь была единс­твенная, то остовой лес О1 для данного графа G не существует.

7) Среди вершин графа G , из которых исходят удаленные ребра на шаге 4в, найдем такие h вер­шин Th єG , из которых исходит одно и только одно ребро uh єи . Эти ребра принадлежат остов-ному лесу (uh єО1). Если таких вершин в графе G нет, то в подмножестве вершин графа G , из кото­рых исходят удаленные ребра на шаге 4в, выбираем любую вершину T' єG , из которой исходят два ре­бра и',uj єи . Рассмотрим два случая принадлеж­ности ребер U єО1 и U є О1 остовному лесу. До­строим граф D аналогично шагам 2 и 3.

8) Переход к шагу 4.

Граф D состоит из нескольких ветвей, каждая из которых представляет собой остовной лес О графа G. Каждый остовной лес получается путем объеди-

б

Делоне T , б граф G

А.В. Шкловец, Н.П Аксак

Рис. 3. Построенный граф D для графа G Остовые леса графа G

Таблица 1

Остовые леса О графа G

Остовые леса О графа G

(\

{u30,u 2WV,«V2,« 4,«WV3}

O5

{u30,u WW^u WW4}

O2

{u30,u 27,u26,u20,u7,u2,u12,u 4,u6,u15,u18,u24}

 

{u30,u 27,u17,u 25,u16,uv,u13,u23,u19,u9,u6}

O3

{u30,u vyvvuvwvu6}

 

{u30,u 27,u17,u 25,и16,и\и\и 4,u6,u19,u14,u23}

O4

{u30,u 2WW,«8,« WW3}

о8

{u30,u 27,u17,u 2w,u8,u 4,u6,u15,u18,u25}

нения всех ребер одной ветви, записанньгх в верши­нах графа D. Согласно рис. 5 для графа G, приве­денного на рис. 4а, существует 8 остовных лесов.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа