О структуре графа разложений образующих однородных натуральных арифметических графов
The paper is finished investigated of the homogenous natural arithmetic graphs using the generatrixes separation graph. A number of the assertions were proved. Structure of the ones graphs were described and investigated both for even and odd cases.
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2007 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84991 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О структуре графа разложений образующих однородных натуральных арифметических графов / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 31-40. — Бібліогр.: 2 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84991 |
|---|---|
| record_format |
dspace |
| spelling |
Шулинок, И.Э. 2015-07-18T06:07:00Z 2015-07-18T06:07:00Z 2007 О структуре графа разложений образующих однородных натуральных арифметических графов / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 31-40. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84991 519.1 The paper is finished investigated of the homogenous natural arithmetic graphs using the generatrixes separation graph. A number of the assertions were proved. Structure of the ones graphs were described and investigated both for even and odd cases. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О структуре графа разложений образующих однородных натуральных арифметических графов About structure of the generatrixes separation graph of the homogenous natural arithmetic graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О структуре графа разложений образующих однородных натуральных арифметических графов |
| spellingShingle |
О структуре графа разложений образующих однородных натуральных арифметических графов Шулинок, И.Э. |
| title_short |
О структуре графа разложений образующих однородных натуральных арифметических графов |
| title_full |
О структуре графа разложений образующих однородных натуральных арифметических графов |
| title_fullStr |
О структуре графа разложений образующих однородных натуральных арифметических графов |
| title_full_unstemmed |
О структуре графа разложений образующих однородных натуральных арифметических графов |
| title_sort |
о структуре графа разложений образующих однородных натуральных арифметических графов |
| author |
Шулинок, И.Э. |
| author_facet |
Шулинок, И.Э. |
| publishDate |
2007 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
About structure of the generatrixes separation graph of the homogenous natural arithmetic graphs |
| description |
The paper is finished investigated of the homogenous natural arithmetic graphs using the generatrixes separation graph. A number of the assertions were proved. Structure of the ones graphs were described and investigated both for even and odd cases.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84991 |
| citation_txt |
О структуре графа разложений образующих однородных натуральных арифметических графов / И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 31-40. — Бібліогр.: 2 назв. — рос. |
| work_keys_str_mv |
AT šulinokié ostrukturegrafarazloženiiobrazuûŝihodnorodnyhnaturalʹnyharifmetičeskihgrafov AT šulinokié aboutstructureofthegeneratrixesseparationgraphofthehomogenousnaturalarithmeticgraphs |
| first_indexed |
2025-11-26T02:45:07Z |
| last_indexed |
2025-11-26T02:45:07Z |
| _version_ |
1850609198200520704 |
| fulltext |
Теорія оптимальних рішень. 2007, № 6 31
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Работа завершает исследование
однородных NA-графов, обращая
внимание, в основном, на графы с
четным числом вершин. Подробно
исследована структура графа
разложений образующих данного
NA-графа.
И.Э. Шулинок, 2007
ÓÄÊ 519.1
È.Ý. ØÓËÈÍÎÊ
Î ÑÒÐÓÊÒÓÐÅ ÃÐÀÔÀ
ÐÀÇËÎÆÅÍÈÉ ÎÁÐÀÇÓÞÙÈÕ
ÎÄÍÎÐÎÄÍÛÕ ÍÀÒÓÐÀËÜÍÛÕ
ÀÐÈÔÌÅÒÈ×ÅÑÊÈÕ ÃÐÀÔÎÂ
Введение. Проведено исследование одно-
родных натуральных арифметических гра-
фов (NA-графов) с нечетным числом вершин
[1]. Был введен граф разложений образую-
щих )(nR и выявлен ряд свойств таких гра-
фов. Данная работа продолжает начатое ис-
следование в [2] и предполагает провести
анализ структуры однородных натуральных
арифметических графов с четным числом
вершин.
Прежде чем, рассматривать регулярные
NA-графы с четным числом вершин, рас-
смотрим некоторые операции на графе раз-
ложений )(1 nR . Как известно, элементарным
гомоморфизмом в графах называется ото-
ждествление (стягивание) двух смежных
вершин. Назовем радиальным гомоморфиз-
мом графа )(1 nR , у которого 1≥β , последо-
вательность операций:
а) удаление всех висячих вершин;
б) перекодировка оставшихся вершин по
правилу 1
2
+= i
i
x
y .
Полученный граф в результате этой опе-
рации обозначим ( ))(1 nRGr . Так как после
удаления висячих вершин останутся только
четные вершины, то вторая операция кор-
ректна. После выполнения первой операции
коды висячих вершин в графе имеют вид i4 ,
И.Э. ШУЛИНОК
32 Теорія оптимальних рішень. 2007, № 6
где
2
1
,,2,1
−
=
n
i K . Применяя операцию б) к этим вершинам, получим все нечетные
коды от 3 до n . Число удаленных вершин равно )12(21 +=− mn
β , а число остав-
шихся вершин равно )1(32 −−− nn = 2−n = 1)12(2 −+m
β .
Структура оставшегося графа совпадает со структурой )(1 nR ′ , где
1)12(2 1 ++=′ −
mn
β . Операция б) превращает коды графа )(1 nR в коды графа
)(1 nR ′ , у которого 1)12(23]1)12(2[232 1 −+=−++=−′=′ −
mmnN
ββ . Если обозна-
чить зависимость графа )(nR от параметров β и m как ),( βmR , то в результате
радиального гомоморфизма получаем зависимость )1,()),(( −= ββ mRmRGr .
Это означает, что в результате радиального гомоморфизма в графе )(1 nR
удаляются все висячие вершины, образующие вилки. После 1−β операций ради-
ального гомоморфизма в графе останется 1)12(2 ++m вершин.
Лемма 1. Граф разложений )12(1 +β
R представляет собой бинарное дерево с
корневой вершиной 1+= nu .
Действительно, 12 += β
n только при 0=m . После 1−β последовательных
радиальных гомоморфизмов получаем 3=′n с }5,4,3{=U . Это вилка с вершиной
4=u , т. е. 1+′= nu . Путем добавления β раз вилок к висячим вершинам можно
восстановить исходный граф, который будет бинарным деревом. Вершина самого
верхнего уровня имеет код 22 +β , т. е. 1+= nu , что и требовалось доказать.
Таким образом, все графы )(1 nR можно свести к )1,()34(1 mRmR =+ , где
0>m .
Число m будем называть кардинальным числом графа разложений )(1 nR .
Обозначим )(2 bµ наибольшее нечетное число, на которое делится b .
Если 34 += mn , то все графы )(1 nR будут иметь только один уровень, где бу-
дут все числа вида )12,,2,1(4 += mkk K . От этих вершин идут ребра в остаточное
множество, которое можно разделить на две равные части V и W в зависимости от
формул, по которым они образовываются
}.12,,3,2,2)1(8)4(2{
,},,2,1,28)14(2{
+++=+−−=−==
=−=−==
mmmkmknkwW
mlllvV
k
l
K
K
О СТРУКТУРЕ ГРАФА РАЗЛОЖЕНИЙ ОБРАЗУЮЩИХ ОДНОРОДНЫХ …
Теорія оптимальних рішень. 2007, № 6 33
Рассмотрим множество перестановок mS из m элементов
=
m
m
iii
m
S
K
K
21
21
.
Определение 1. Характеристической перестановкой для графа разложений об-
разующих )34(1 +mR назовем такую перестановку }
2
1)(
{ 2 ++
⇒=
im
ifm
µ
, где
mi ,,2,1 K= .
Очевидно, что данное отображение будет перестановкой, т. е., при этом полу-
чаются все числа от 1 до m . Предположим обратное, что в результате получаем два
одинаковых числа:
2
)(
,
2
1)( 2
2
2
1
jm
i
im
i
+µ
=
++µ
= , где mji ≤≤ ,1 . Если ji > , то
)1(2)12( ≥⋅+−= pjmi
pp . Отсюда следует, что mi > , а это не может быть по ви-
ду самого определения функции )(2 bµ . Поэтому получаются все числа разные и не
больше m .
Определение 2. Весом элемента i на перестановке mS называется величина
2
12
log)( 2 +
−
=
i
m
iλ .
Теорема 1. Граф разложений образующих )34(1 +mR состоит из 1+p компо-
нент связности, из них одна – цепь длиной 3, а остальные компоненты содержат
ровно один цикл из вершин остаточного множества. Число p равно числу циклов в
характеристической перестановке mm Sf ∈ , а длина каждого цикла равна сумме ве-
сов элементов соответствующего цикла в mf .
Покажем, что множества V и W не пересекаются. Действительно, если это так,
то найдутся k и l , такие, что 2828 −=− lnk , или 28688 −=−− lmk . Отсюда сле-
дует: 1)(22 −−= mkl , что невозможно.
Рассмотрим последовательность 22 1 −= −ss xx , где Vx ∈1 . Для любого 2≥s
всегда 222 1
1 +−= − ss
s xx . Если подставить значение Vlx ∈−= 281 , получаем
2)12(2 1 +−⋅= +
lx
s
s , т.е., для 2≥s все члены последовательности принадлежат
W . При этом для разных 1l и 2l данные последовательности не имеют общих чле-
нов. В противном случае, если какие-то rs xx = , или )12(2)12(2 2
1
1
1 +=+ ++
ll
rs , то
И.Э. ШУЛИНОК
34 Теорія оптимальних рішень. 2007, № 6
это возможно только при rs = и 21 ll = , что противоречит предположению. Итак,
каждый элемент множества V служит начальным членом последовательности, в
которой последующие члены принадлежат W . Так как V и W равномощны, то эти
последовательности исчерпывают множество W . Наибольший член данного мно-
жества kw получим при 12 += mk , т.е. 28max += mw . Так как maxwxs ≤ , решая
неравенство при фиксированном i в последовательности будет
2
12
log2max +
−
=
i
m
s членов. Будем различать наименьший и наибольший члены
данной последовательности. Каждая последовательность – цепочка разложений
наибольшей образующей данной последовательности на левые составляющие раз-
ложений. Это разложение можно продлить на один шаг вниз, полагая 0=s , получа-
ем lx 40 = , т.е. первую половину вершин первого уровня. Аналогично, приходим к
выводу, что максимальные значения последовательностей составляют остаточные
элементы, превышающие 1+n , но их порядок зависит от конкретного значения m .
Однако каждый элемент множества Vvi ∈ разлагается на образующую i4 и на ко-
нечный элемент последовательности, начальный элемент которой jx 40 = . Так как
разница между i4 и этим конечным элементом должна быть 241 +=− mn , то j
находим из уравнения
),2,1(),0(222)4(244 1
misjmi
ss
K=>+−⋅=++ + . (1)
Отсюда находим )(
2
12 2 mi
mi
j +=
+
=− µ , так как 12 −j – нечетное число. В
результате
2
1)(2 ++
=
mi
j
µ
. Рассмотрим отображение
2
1)(2 ++
⇒
mi
i
µ
. Докажем,
что оно является перестановкой из mS , т.е. при изменении i от 1 до m j пробега-
ет разные значения. Для 3,2=m можно проверить непосредственно, это переста-
новки (2, 1) и (1, 3, 2). Пусть утверждение справедливо для произвольного m , до-
кажем то же самое для 1+m . Так как )1()1( ++−=+ mimi , начиная с 2=i и до
mi = , элементы в mf равны соответствующим элементам в 1+mf , начиная с 1=i и
до 1−= mi . Все они по индукции различны, остается определить два элемента для
mi = и 1+= mi .
О СТРУКТУРЕ ГРАФА РАЗЛОЖЕНИЙ ОБРАЗУЮЩИХ ОДНОРОДНЫХ …
Теорія оптимальних рішень. 2007, № 6 35
Первый элемент равен 1
2
112
2
1)1(2 +=
++
=
+++
m
mmmµ
, а второй –
2
1)1(
2
1)11( 22 ++
=
++++ mmm µµ
, т.е. первому элементу в mf . Оба данные эле-
менты прежде не появлялись, поэтому имеем способ построения с перестановкой.
Это доказательство дает способ построения всех перестановок для произвольного
m по индукции. Для того, чтобы записать все mf , считая 2f и 3f заданными, не-
обходимо следовать таким правилам:
переписать все, кроме первого, элементы из 1−mf ;
записать элемент m ;
записать первый элемент из 1−mf .
Все эти перестановки для 20,,3,2 K=m приведены в табл.1, а их представление
в виде циклов – в табл. 2 (для 16≤m ).
Заметим общие закономерности табл. 1:
– номер числа m находится на )1( −m -м месте в перестановке;
– число i в следующей перестановке находится на месте, номер которого на
)(modml меньше, чем в предыдущей перестановке.
Достаточно двух правил , чтобы построить полную таблицу.
ТАБЛИЦА 1. Перестановки при 202 ≤≤ m
m Перестановки
2 2, 1
3 1, 3, 2
4 3, 2, 4, 1
5 2, 4, 1, 5, 3
6 4, 1,5, 3, 6, 2
7 1, 5, 3, 6, 2, 7, 4
8 5, 3, 6, 2, 7, 4, 8, 1
9 3, 6, 2, 7, 4, 8, 1, 9, 5
10 6, 2, 7, 4, 8, 1, 9, 5,10, 3
11 2, 7, 4, 8, 1, 9, 5,10, 3,11, 6
12 7, 4, 8, 1, 9, 5,10, 3,11, 6,12, 2
13 4, 8, 1, 9, 5,10, 3,11, 6,12, 2,13, 7
И.Э. ШУЛИНОК
36 Теорія оптимальних рішень. 2007, № 6
Окончание табл.1
m Перестановки
14 8, 1, 9, 5,10, 3,11, 6,12, 2,13, 7,14, 4
15 1, 9, 5,10, 3,11, 6,12, 2,13, 7,14, 4,15, 8
16 9, 5,10, 3,11, 6,12, 2,13, 7,14, 4,15, 8,16, 1
17 5,10, 3,11, 6,12, 2,13, 7,14, 4,15, 8,16, 1,17, 9
18 10, 3,11, 6,12, 2,13, 7,14, 4,15, 8,16, 1,17, 9,18, 5
19 3,11, 6,12, 2,13, 7,14, 4,15, 8,16, 1,17, 9,18, 5,19,10
20 11, 6, 12, 2, 13, 7, 14, 4, 15, 8, 16, 1, 17, 9, 18, 5, 19, 10, 20, 3
ТАБЛИЦА 2. Таблица циклов в перестановках
m Коды циклов
2
)2,1( 13
3
)3,2)(1( 123
4
)2)(4,3,1( 2114
5
)3,5,4,2,1( 21124
6
)2,6,5,3,4,1( 311214
7
)7,6,4)(3)(5,2)(1( 1122134
8
)4,6,3,2)(8,7,5,1( 21231115
9
)7,4,5,9,8,6,2,3,1( 122111325
10
)8,5)(4)(10,9,7,3)(2)(6,1( 1221113315
11
)9,6,11,10,8,4,3)(5,7,2,1( 12111232135
12
)8,3)(4,2,12,11,9,5,6,10,7,1( 132411122115
13
)5)(11,8,2)(3,7,13,12,10,6,9,4,1( 2114321112125
14
)2,10,5,4,14,13,11,7,12,9,3,6,8,1( 41231112113215
15
)15,14,12,8)(7,11,6)(8,10,4)(5,3)(9,2)(1( 111221211323145
16 )6)(4,12,7,10,3)(8,14,11,5,2)(16,15,13,9,1( 2312132112411116
Число циклов или компонент на множестве вершин остаточного множества оп-
ределяется числом циклов в соответствующей перестановке. Еще одну компоненту
О СТРУКТУРЕ ГРАФА РАЗЛОЖЕНИЙ ОБРАЗУЮЩИХ ОДНОРОДНЫХ …
Теорія оптимальних рішень. 2007, № 6 37
в )(1 nR дает образующая )1(41 +=+ mn , которая разлагается на две нечетные обра-
зующие 321 += mu и 56)1(22 +=++= mnmu , что в сумме дает цепь длиной 3.
Циклам в перестановке из mf соответствует цикл в графе )(1 nR , если вместо одно-
го элемента перестановки брать соответствующую последовательность вершин.
Теперь можно выбирать любые образующие для регулярного графа. Если взять
нечетную образующую, то ее дополнением может быть четная образующая либо
типа i4 , либо из остаточного множества. Второй случай исключается, следователь-
но, остается i4 , которая разлагается на две нечетные. Всего получается 4 обра-
зующие и граф регулярный степени 2. Если взять четную образующую типа i4 , то
вместе с дополняющей нечетной и двумя нечетными по разложению получатся те
же 4, которые дают регулярный граф степени 2. Если взять четную образующую из
остаточного множества, то нужно брать все образующие одной компоненты, кото-
рые дают регулярный граф степени z2 , где z – число вершин в цикле. Пользуясь
теоремой 1 и табл. 1 и 2, можно построить граф )(1 nR для любого )2(mod1≡n .
Рассмотрим пример: 15,3 == nm .
По табл. 1 и 2 находим перестановку и ее представление в циклах )3,2)(1( 123 .
Граф )15(1R состоит из трех компонент. Для 1=i находим образующую
6281 =−= iv . Вес элемента 1 равен 3, т.е. цепочка длиной 3 составляет цикл. Нахо-
дим его элементы: 1022 12 =−= vv , 1822 23 =−= vv . Первая компонента составляет
цикл из остаточных образующих (6, 10, 18) и всех образующих после их разложе-
ния. Для второй компоненты находим 1428,2 1 =−== ivi . Эта цепочка состоит из
двух вершин, поэтому 2622 12 =−= vv . Для третьей вершины 3=i ,
22283 =−= iv Таким образом, вторая компонента состоит из цикла (14, 26, 22) и
образующих, полученных от их разложения. Третья компонента состоит из обра-
зующей 161 =+n и ее разложения 9 и 23. Граф )15(1R показан на рисунке.
Рассмотрим случай )2(mod0≡n . Так как нечетная образующая имеет своим
дополнением также нечетную образующую, то степень регулярности графа может
быть любой, если выбирать только нечетные образующие. Если взять четную обра-
зующую, то для выяснения вопроса о существовании регулярных графов необходи-
мо построить граф разложения образующих )(0 nR , который строится по тому же
принципу, что и )(1 nR . Каждая четная образующая разлагается обязательно на одну
четную и одну нечетную, так как разница между их значениями равна 1−n , т.е. не-
четному числу.
И.Э. ШУЛИНОК
38 Теорія оптимальних рішень. 2007, № 6
5
9 23
16
15
7
3
11
13
8
14
12
6
4
10
29
15
28
14
26
22
1219
5
21
7
27
13
24
18
10
20 2511
6
63
17
8
9
РИСУНОК. Граф 3)),15(()8()),29(()15( 1011 === mRGrRRGrR
Теорема 2. Граф разложений )22(0 +mR состоит из 1+p компонент связно-
сти, из которых одна является вершиной 1−n , а остальные компоненты содержат
ровно один цикл из вершин остаточного множества. Число p равно числу циклов в
перестановке mm Sf ∈ , }
2
1)(
{ 2 ++
⇒=
im
ifm
µ
, а длина каждого цикла в графе
равна сумме весов элементов соответствующего цикла в mf . При этом
2
2−
=
n
m , а
вес элемента определяется так же, как и в )(1 nR .
Образуем последовательности такого же типа, как и для )(1 nR
222 1
1 +−= − ss
s xx , где в качестве 1x берем образующую i4 . Наибольшее значе-
ние образующей равно 12 −n , поэтому 1
2
,,2,1 −=
n
i K . Нетрудно показать, что
ixs 4≠ при любом is, и 1≥k . Обозначим 1
2
−=
n
m и, как прежде, будем называть
его кардинальным числом графа )(0 nR . Тогда получаем m разных непересекаю-
щихся последовательностей, таких, как и для )(1 nR , с единственным отличием, что
О СТРУКТУРЕ ГРАФА РАЗЛОЖЕНИЙ ОБРАЗУЮЩИХ ОДНОРОДНЫХ …
Теорія оптимальних рішень. 2007, № 6 39
здесь 1x принадлежит последовательности, и sx не должно превышать макси-
мальное значение четных образующих, что так же s
i 2)4( 2422 1 +≤+− +
m
s . От-
сюда длина цепочки 2
12
log)( 2 +
−
==
i
m
siλ . Так как начальный элемент це-
почки i4 разлагается на нечетную образующую 12 +i и четную образую-
щую 2)(22 ++=+ mini , которая должна быть максимальным элементом другой
цепочки, то решив уравнение
22242)(2 1 +−⋅=++ +ss
ijmi (2)
находим )(2/][12 2 mimij
s +=+=− µ . Так как 12 −j – нечетное число, тогда
2
1)(2 ++
=
mi
j
µ
, приходим к тому же результату, что в теореме 1.
Таким образом, для определения структуры графа )(0 nR можно воспользо-
ваться табл.1 и 2, которые составлены для )(1 nR , выбирая строку с заданным m .
Рассмотрим граф )(0 nR для 8=n . При этом 3=m и в табл.1 находим соот-
ветствующую перестановку (1,3,2), состоящую из двух циклов. Подставим в них вес
элементов: 1)3(,2)2(,3)1( === λλλ . В результате получаем граф (на рисунке
справа). Из рисунка видно, что этот граф получен из графа )(1 nR для 3=m путем
радиального гомоморфизма.
Следствие. Граф, полученный с помощью радиального гомоморфизма графа
разложений )34(1 +mR совпадает с графом разложений образующих )22(0 +mR ,
т. е. )22())34(( 01 +=+ mRmRGr .
І.Е. Шулінок
ПРО СТРУКТУРУ ГРАФА РОЗКЛАДІВ ТВІРНИХ ОДНОРІДНИХ НАТУРАЛЬНИХ
АРИФМЕТИЧНИХ ГРАФІВ
Робота завершує дослідження однорідних натуральних арифметичних графів за допомогою гра-
фів розкладів твірних. Доведено ряд тверджень, які описують структуру графів розкладів твір-
них, як для парного так і для непарного випадків.
И.Э. ШУЛИНОК
40 Теорія оптимальних рішень. 2007, № 6
I.E. Shulinok
ABOUT STRUCTURE OF THE GENERATRIXES SEPARATION GRAPH OF THE
HOMOGENOUS NATURAL ARITHMETIC GRAPHS
The paper is finished investigated of the homogenous natural arithmetic graphs using the generatrixes
separation graph. A number of the assertions were proved. Structure of the ones graphs were described
and investigated both for even and odd cases.
1. Шулинок И.Э. Структура натуральных арифметических графов с нечетным числом вер-
шин // Оптимизация и ее приложения. – Киев: Ин-т кибернетики им. В.М. Глушкова
НАН Украины, 1997. – С. 54 – 60.
2. Шулинок И.Э., Каюров В.Ю. Однородные натуральные арифметические графы с
нечетным числом вершин // Теория оптимальных решений. – Киев: Ин-т кибернетики
им. В.М. Глушкова НАН Украины, 2006. – № 5. – С. 48 – 53.
Получено 29.04.2007
|