Унициклические факторизации сети типа свернутой бабочки
In this paper, we prove that the wrapped Butterfly graph M(k,n) of degree k and dimention n is decomposable into k edge-disjoint mutually isomorphic unicyclic factors with n -cycle each and is the union of these factors.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2004 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84874 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Унициклические факторизации сети типа свернутой бабочки / В.В. Строк, А.В. Чагарный // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 34-40. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860140103235534848 |
|---|---|
| author | Строк, В.В. Чагарный, А.В. |
| author_facet | Строк, В.В. Чагарный, А.В. |
| citation_txt | Унициклические факторизации сети типа свернутой бабочки / В.В. Строк, А.В. Чагарный // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 34-40. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | In this paper, we prove that the wrapped Butterfly graph M(k,n) of degree k and dimention n is decomposable into k edge-disjoint mutually isomorphic unicyclic factors with n -cycle each and is the union of these factors.
|
| first_indexed | 2025-12-07T17:49:00Z |
| format | Article |
| fulltext |
34 Теорія оптимальних рішень. 2004, № 3
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
В работе доказано, что струк-
турный граф сети типа сверну-
той бабочки ( )nkM , степени k и
размерностью n содержит k не-
пересекающихся по рёбрам изо-
морфных унициклических остов-
ных подграфов (с циклом длины n
в каждом) и является объедине-
нием данных k подграфов.
В.В. Строк, А.В. Чагарный,
2004
ÓÄÊ 519.175
Â.Â. ÑÒÐÎÊ, À.Â. ×ÀÃÀÐÍÛÉ
ÓÍÈÖÈÊËÈ×ÅÑÊÈÅ ÔÀÊÒÎÐÈÇÀÖÈÈ
ÑÅÒÈ ÒÈÏÀ ÑÂÅÐÍÓÒÎÉ ÁÀÁÎ×ÊÈ
Введение. Среди многих типов сетей внеш-
них связей, предлагаемых в качестве подхо-
дящих топологий для выполнения сортиров-
ки, быстрого преобразования Фурье и других
применений, особенно удобны сети в виде
бабочки. Рассматриваемая структура связей
принадлежит к числу наиболее удобных для
разработки сетей, предназначенных для мак-
симально параллельного решения задач (см.,
напр., [1]). При этом возникает необходи-
мость в построении определённых преобра-
зований структурного графа сети вычисли-
тельной системы, обеспечивающих реализа-
цию распределённых алгоритмов. Одним из
таких преобразований графа является разло-
жение его на непересекающиеся по рёбрам
остовные подграфы (задача факторизации
графа [2]).
Сеть типа свёрнутой бабочки (бинарный
случай) можно рассматривать как сеть быст-
рого преобразования Фурье, в которой вход-
ные вершины отождествлены с соответст-
вующими вершинами выхода. В данной ра-
боте исследуется разложение ориентирован-
ной сети типа свернутой бабочки, основан-
ное на существенном использовании тех её
свойств, которые следуют из математической
модели представления этой сети как некото-
рого обобщённого графа де Брёйна ( )nkM , .
Частный случай такого обобщения графа де
Брёйна ),( nkB малого порядка впервые был
предложен в [3] (построение С1) в связи с за-
УНИЦИКЛИЧЕСКИЕ ФАКТОРИЗАЦИИ СЕТИ ТИПА СВЕРНУТОЙ БАБОЧКИ
Теорія оптимальних рішень. 2004, № 3 35
дачей максимизации порядка графа при заданных степени и диаметре. В резуль-
тате исследования подхода, используемого в [4] при построении обобщённого
графа ( )nkM , , в [5] предложено представление этого обобщения как произведе-
ние ([6]) ),( nkBC × контура C длины n и орграфа ),( nkB порядка n
k . Случай
разложения структурного графа бинарной ориентированной сети ( )nM ,2 типа
свернутой бабочки на минимально возможное число униконтурных изоморфных
остовных подграфов впервые изучен в [7]. Здесь решается задача такого разло-
жения сети ( )nkM , , заданной на произвольном конечном алфавите, и тем са-
мым обобщаются соответствующие утверждения, содержащиеся в предыдущей
работе. Полученные результаты справедливы и для неориентированных сетей
этого типа. Сеть ( )nkM , иногда называют также графом типа „бабочки на ци-
линдре”. Вопросы разложения этого типа сильносвязной сети на непересекаю-
щиеся по дугам гамильтоновы циклы подробно рассматривались в [8]. При том,
что структурный граф сети типа свернутой бабочки в действительности является
ориентированным графом, иногда эти сети полагают ненаправленными. Мы
всегда будем считать их ориентированными.
Унициклические факторизации. В данной работе используем следующие
определения и обозначения, где kZ – множество целых неотрицательных чисел
по модулю k.
Определение 1. Орграфом сети типа бабочки ( )nkBF , степени k и размер-
ностью n называется орграф, вершинами которого являются упорядоченные па-
ры ( )xl; , где 110 ... −βββ= nx ( )ki
n
kx Ζ∈βΖ∈ , , а l - номер яруса ( )nl ≤≤0 . Для
nl < вершина ( )11110 ......; −+− βαββββ nlll l-го яруса соединена дугами с k верши-
нами соседнего яруса вида ( )11110 ......;1 −+− βωββββ+ nlll , где kΖ∈ωα, .
Таким образом, орграф ( )nkBF , состоит из ( ) n
kn 1+ вершин, организован-
ных в виде n + 1 ярусов из kn
вершин в каждом.
Определение 2. Орграфом сети типа свернутой бабочки ( )nkM , называется
орграф, полученный из орграфа ( )nkBF , в результате отождествления вершин
последнего и первого ярусов, а именно: вершины ( )ixn; с вершиной ( )ix;0 ,
n
kix Ζ∈ .
Следовательно, орграф ( )nkM , является k-регулярным орграфом с n
nk
вершинами, в котором любая вершина ( )11110 ......; −+− βαββββ nlll l-го яруса соеди-
нена дугами с k вершинами соседнего яруса вида
( )( )11110 ......;mod1 −+− βωββββ+ nllnl , где kΖ∈ωα, .
Определение 3. Орграфом де Брёйна ( )nkB , порядка n
k называется орг-
раф, множество вершин которого является множеством слов длины n на алфави-
В.В. СТРОК, А.В. ЧАГАРНЫЙ
36 Теорія оптимальних рішень. 2004, № 3
те { }1,...,2,1,0 −=Ζ kk . Дуги орграфа идут с вершины ( )1, −Ζ∈Ζ∈αΖ∈α n
kk
n
k xx в
каждую вершину n
kx Ζ∈β ( )kΖ∈β .
Матрицей смежностей орграфа ( )nkB , является k-циркулянт порядка n
k с
первой строкой вида ( )0,...,0,,...,, 21 kβββ , в которой 1...1 =β==β k .
Пусть Н - несвязный орграф, компонентами связности которого являются
1−k копий ориентированного с корневой вершины x полного k-арного дерева
xS высоты 1−n и одна изолированная вершина y. Орграф, полученный в ре-
зультате соединения дугой вершины y с вершиной x каждой компоненты xS
орграфа Н, будем называть деревом де Брёйна T (с корневой вершиной y). Се-
мейство подграфов mGG ,...,1 графа (орграфа) ( )EVG ,= называется разложени-
ем графа G на компоненты iG , если множества ( )iGE , mi ,...,2,1= образуют
разбиение множества ребер (дуг) ( )GE .
В дальнейшем нам понадобиться следующее утверждение, доказательство
которого содержится в [9].
Лемма 1. Существует разложение орграфа ( )nkB , на взаимно изоморфные
непересекающиеся по дугам униконтурные связные компоненты ( )
yyTU ii +=1 ,
TTi ≅ ( )ki ,...,2,1= , где T – дерево де Брёйна, а yy – контур длины 1 (петля) при
корневой вершине y этого дерева.
Здесь исследование сети ( )nkM , основано на существенном использовании
свойств матричного представления произведения 21 GG × орграфов 1G и 2G ,
которому соответствует кронекерово произведение их матриц смежностей
( ) ( )21 GAGA ⊗ (см. в [10]). Поэтому воспользуемся введенной в [5] формой
представления матрицы смежностей обобщенного графа де Брёйна и зададим
матрицу смежностей сети ( )nkM , в виде
BCM ⊗= , (1)
где C – матрица смежностей контура длины n, а B – матрица смежностей орг-
рафа де Брёйна ( )nkB , (доказательство изоморфности орграфов ( )nkBC ,× и
( )nkM , (см. в [8]).
Пусть C – контур длины 1≥n , а T – несвязный орграф, компонентами ко-
торого являются n копий дерева де Брёйна T порядка n
k . Рассмотрим уникон-
турный связный орграф ( )n
U , образованный отождествлением каждой из n вер-
шин контура C с корневой вершиной одной из компонент орграфа T. Не трудно
убедиться в том, что матрица смежностей орграфа ( )n
U имеет вид
( )( ) ( )( )1
UACUA
n ⊗= , (2)
УНИЦИКЛИЧЕСКИЕ ФАКТОРИЗАЦИИ СЕТИ ТИПА СВЕРНУТОЙ БАБОЧКИ
Теорія оптимальних рішень. 2004, № 3 37
где ( )
yyTU +=1 , T – дерево де Брёйна порядка n
k с корневой вершиной y, а
C – матрица смежностей контура C длины n.
Теорема 1. Пусть ( )nkM , – орграф сети типа свернутой бабочки порядка
n
nk , заданный на алфавите kΖ . Орграф ( )nkM , можно представить в виде сум-
мы k непересекающихся по дугам остовных униконтурных подграфов, содер-
жащих контур C длины n и изоморфных такому орграфу ( )n
U , что компонен-
тами леса ( )CEU
n − являются n копий полного k-арного корневого ордерева без
одной главной ветви (дерево де Брёйна).
Доказательство. Согласно леммы 1 орграф де Брёйна
( ) ( )1
1
, i
k
i
UnkB U =
= , ( ) ( ) ( )kiUU i ,...,2,111 =≅ . (3)
При этом матрица смежностей ( )( )1
iUA остовного униконтурного орграфа
( )1
iU , как показано в [5, 9], может быть представлена в блочной форме вида
( )( ) [1 =iUA О… О iF О … О ]′ , FFi = , (4)
с блочными размерами 1×k . Здесь [ ]1...111 ⊗= −n
k
IF – матрица с размерами
kk
n ×−1 , 1−n
k
I – единичная матрица порядка 1−n
k , О – нулевая матрица того же
порядка, а [ ]1...11 – строчная ( )k×1 – матрица. Разложению (3) и форме пред-
ставления (4) матрицы ( )( )1
iUA соответствует матричное представление орграфа
де Брёйна
1[FB = О … О [] + О 2F О … О [...] ++ О … О =]kF
( )( ) ( )( ) ( )( )11
2
1
1 ... kUAUAUA +++= , (5)
где ( )1
iU – остовный подграф графа ( )nkB , , изоморфный ордереву де Брёйна с
петлёй у корня.
В соответствии с разложением (5) матрицу смежностей орграфа сети
( )nkM , представим в виде
( )( )∑ =
=⊗=
k
i
n
iUABCM
1
, )()(
)1()(
i
n
i UACUA ×= . (6)
Изоморфность ( ) ( )nn
i UU 1≅ следует из того, что ( ) ( )1
1
1
UU i ≅ , ki ,...,2,1= . По-
кажем это, используя свойства кронекерового произведения и подобия квадрат-
ных матриц.
Поскольку ( ) ( )1
1
1
UU i ≅ , то существует такая матрица перестановок P порядка
n
k , что ( )( ) ( )( )PUAPUA i
1
1
1 ′= .
Тогда
В.В. СТРОК, А.В. ЧАГАРНЫЙ
38 Теорія оптимальних рішень. 2004, № 3
( )( ) ( )( ) ( )( )
( ) ( )( )( ) ( )
( )( )( ) ( )( ) ,1
11
11
QUAQQUACQ
PIUACPI
PUAPCUACUA
n
iin
n
n
in
i
n
′=⊗′=
=⊗⊗′⊗=
=′⊗=⊗=
(7)
где PIQ n ⊗= – матрица перестановок порядка n
nk , а nI – единичная матрица
порядка n.
Таким образом, матрицы ( )( )n
UA 1 и ( )( )n
iUA подобны. Следовательно, пред-
ставленные этими матрицами орграфы ( )n
iU и ( )n
U1 изоморфны. Далее, из (5)
следует, что орграф сети
( ) ( )n
i
k
i
UnkM U 1
,
=
= , ( ) ( )nn
i UU ≅ , ki ,...,2,1= , (8)
что и завершает доказательство теоремы.
Обозначим nT – дерево де Брейна порядка n
k и высоты n, а nS – полное
k-арное ордерево высоты n.
Следствие 1. Орграф сети типа свернутой бабочки ( )nkM , порядка n
nk
содержит: а) nk непересекающихся по дугам копий дерева nT ; б) n копий дере-
ва nT , не имеющих общих вершин; в) )1( −kn непересекающихся по вершинам
ордеревьев 1−nS высоты 1−n .
Эти утверждения получаются непосредственно из теоремы 1. Результат ра-
боты [10, следствие 3], следует из вышеприведённых общих утверждений, по-
скольку 1−nS содержиться в nT . На рисунке показано разложение структурного
орграфа сети )2,3(M на унициклические непересекающиеся по дугам остовные
изоморфные подграфы )2(
1U , )2(
2U и )2(
3U (с 2-циклом в каждом). При этом дуги
в )2,3(M ориентированы слева направо и (для наглядности) 0-й ярус повторен
дважды – одинаково обозначенные вершины отождествляются. В сети )2,3(M
жирными линиями обозначены дуги факторграфа )2(
2U
Заключение. Результаты исследования показывают, что сеть типа сверну-
той бабочки ),( nkM является )(n
U -факторизуемой, т.е. структурный граф этой
сети всегда может быть представлен как объединение k унициклических изо-
морфных )(n -факторов )(n
U , содержащих цикл C длины n, при этом компо-
нентами леса )()(
CEU
n − являются n копий дерева де Брёйна высоты n . Отме-
тим, что рассмотренный в [6] граф )( ,, mnkU Γ при nm = является структурным
графом неориентированной сети типа свернутой бабочки. Там же определены
УНИЦИКЛИЧЕСКИЕ ФАКТОРИЗАЦИИ СЕТИ ТИПА СВЕРНУТОЙ БАБОЧКИ
Теорія оптимальних рішень. 2004, № 3 39
число остовных деревьев, содержащихся в такой сети, и спектры ее структур-
ных ориентированных графов.
001
011
021
101
110
121
201
211
221
000
010
020
100
110
120
200
210
220
000
010
020
100
110
120
200
210
220
000
001
010
110
210
020
120
220
101
111
121
201
211
221
011
021
100
200
220
221
000
100
200
010
110
210
001
011
021
101
111
121
201
211
020
120
РИСУНОК
110
111
000
100
200
120
020
220
001
011
021
201
211
221
101
121
010
210
( )2
3U
( )2
2U
( )2
1UМ(3,2
)
В.В. СТРОК, А.В. ЧАГАРНЫЙ
40 Теорія оптимальних рішень. 2004, № 3
В.В. Строк, А.В. Чагарний
УНІЦИКЛІЧНІ ФАКТОРИЗАЦІЇ МЕРЕЖІ ТИПУ ЗГОРНУТОГО МЕТЕЛИКА
У роботі доведено, що структурний граф мережі типу згорнутого метелика ),( nkM степеню
k і розмірності n містить k взаємно ізоморфних уніциклічних факторграфів, які не перети-
наються по ребрах (з циклом довжини n у кожному). Мережа ),( nkM є об’єднанням цих
факторграфів.
V.V. Strok, O.V. Chagarnyi
ON UNICYCLIC FACTORIZATIONS OF THE WRAPPED BUTTERFLY NETWORK
In this paper, we prove that the wrapped Butterfly graph ),( nkM of degree k and dimention n is
decomposable into k edge-disjoint mutually isomorphic unicyclic factors with n -cycle each and is
the union of these factors.
1. Ульман Дж. Д. Вычислительные аспекты СБИС..– М: Радио и связь, 1990. – 480 с.
2. Харари Ф. Теория графов. – М: Мир, 1973. – 324 с.
3. Memmi G., Raillard Y. Some new results about the (d,k) graph problem // IEEE Trans.
Comput. – 1982. – C 31, N8. – P. 784 – 791.
4. Kim Y.S., Kim M. A generalization of the de Bruijn graph for dense symmetric intercon –
nection networks in multicomputer systems // Trans. IEICE. – 1989. – E 72, N6. – P. 691 –
694.
5. Строк В.В. Характеристические многочлены и спектры обобщенных графов де
Брёйна // Интеллектуализация систем обработки информационных сообщений.–
Киев: Ин-т математики НАН Украины, 1995. – С. 180 – 190.
6. Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. – Киев: Наук.
думка, 1984. – 384 с.
7. Строк В.В., Шлепаков Л.М. Уніконтурні факторграфи в орієнтованих мережах типу
згорнутого метелика // Доп. Національної академії наук України. – 2002. – № 10.–
С. 27 – 31.
8. Bermond J.C., Darrot E., Delmas O., Perrenes S. Hamilton circuits in the directed
wrapped Butterfly network // Discrete Applied Mathematics.– 1998.– 84.– P. 21 – 42.
9. Строк В.В. Униконтурные изоморфные факторизации орграфов де Брейна и Каутца
// Кибернетика и системный анализ. – 2004. – № 4. – С. 17 – 26.
10. Annexstein F., Baumschlag M., Rosenberg A.L. Group action graphs and parallel
architectures. COINS Technical Report 87 – 133.– Massachusetts: Computer and Infor-
mation Sci. Departament. Univ. of Massachusetts, 1987.– 23 p.
Получено 09.06.2004
|
| id | nasplib_isofts_kiev_ua-123456789-84874 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:49:00Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Строк, В.В. Чагарный, А.В. 2015-07-16T17:41:43Z 2015-07-16T17:41:43Z 2004 Унициклические факторизации сети типа свернутой бабочки / В.В. Строк, А.В. Чагарный // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 34-40. — Бібліогр.: 10 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84874 519.175 In this paper, we prove that the wrapped Butterfly graph M(k,n) of degree k and dimention n is decomposable into k edge-disjoint mutually isomorphic unicyclic factors with n -cycle each and is the union of these factors. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Унициклические факторизации сети типа свернутой бабочки On unicyclic factorizations of the wrapped butterfly network Article published earlier |
| spellingShingle | Унициклические факторизации сети типа свернутой бабочки Строк, В.В. Чагарный, А.В. |
| title | Унициклические факторизации сети типа свернутой бабочки |
| title_alt | On unicyclic factorizations of the wrapped butterfly network |
| title_full | Унициклические факторизации сети типа свернутой бабочки |
| title_fullStr | Унициклические факторизации сети типа свернутой бабочки |
| title_full_unstemmed | Унициклические факторизации сети типа свернутой бабочки |
| title_short | Унициклические факторизации сети типа свернутой бабочки |
| title_sort | унициклические факторизации сети типа свернутой бабочки |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84874 |
| work_keys_str_mv | AT strokvv unicikličeskiefaktorizaciisetitipasvernutoibabočki AT čagarnyiav unicikličeskiefaktorizaciisetitipasvernutoibabočki AT strokvv onunicyclicfactorizationsofthewrappedbutterflynetwork AT čagarnyiav onunicyclicfactorizationsofthewrappedbutterflynetwork |