Однородные натуральные арифметические графы с нечетным числом вершин
A way of enumeration of regular graphs for natural arithmetical graphs was found. A definition of graphs decomposition of generatrixes was introduced. It is proved some statements about its properties. This gives a possibility to determine uniquely the structure of regular graphs.
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2006 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84953 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Однородные натуральные арифметические графы с нечетным числом вершин / И.Э. Шулинок, В.Ю. Каюров // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 48-54. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84953 |
|---|---|
| record_format |
dspace |
| spelling |
Шулинок, И.Э. Каюров, В.Ю. 2015-07-17T16:44:44Z 2015-07-17T16:44:44Z 2006 Однородные натуральные арифметические графы с нечетным числом вершин / И.Э. Шулинок, В.Ю. Каюров // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 48-54. — Бібліогр.: 7 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84953 519.1 A way of enumeration of regular graphs for natural arithmetical graphs was found. A definition of graphs decomposition of generatrixes was introduced. It is proved some statements about its properties. This gives a possibility to determine uniquely the structure of regular graphs. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Однородные натуральные арифметические графы с нечетным числом вершин Homogeneous natural arithmetical graphs with odd namber of vertices 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 |
2006 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Homogeneous natural arithmetical graphs with odd namber of vertices |
| description |
A way of enumeration of regular graphs for natural arithmetical graphs was found. A definition of graphs decomposition of generatrixes was introduced. It is proved some statements about its properties. This gives a possibility to determine uniquely the structure of regular graphs.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84953 |
| citation_txt |
Однородные натуральные арифметические графы с нечетным числом вершин / И.Э. Шулинок, В.Ю. Каюров // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 48-54. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT šulinokié odnorodnyenaturalʹnyearifmetičeskiegrafysnečetnymčislomveršin AT kaûrovvû odnorodnyenaturalʹnyearifmetičeskiegrafysnečetnymčislomveršin AT šulinokié homogeneousnaturalarithmeticalgraphswithoddnamberofvertices AT kaûrovvû homogeneousnaturalarithmeticalgraphswithoddnamberofvertices |
| first_indexed |
2025-11-25T23:26:44Z |
| last_indexed |
2025-11-25T23:26:44Z |
| _version_ |
1850580591668363264 |
| fulltext |
48 Теорія оптимальних рішень. 2006, № 5
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Для натуральных арифметиче-
ских графов найден способ пере-
числения регулярных графов. Для
этого вводится понятие графа
разложения образующих. Доказа-
но ряд утверждений о его свой-
ствах, что дает возможность
однозначно определить структу-
ру регулярных графов.
И.Э. Шулинок, В.Ю. Каюров,
2006
ÓÄÊ 519.1
È.Ý. ØÓËÈÍÎÊ, Â.Þ. ÊÀÞÐÎÂ
ÎÄÍÎÐÎÄÍÛÅ ÍÀÒÓÐÀËÜÍÛÅ
ÀÐÈÔÌÅÒÈ×ÅÑÊÈÅ ÃÐÀÔÛ
Ñ ÍÅ×ÅÒÍÛÌ ×ÈÑËÎÌ ÂÅÐØÈÍ
Введение. В своем развитии теория графов
соприкасается с различными задачами теоре-
тического и прикладного характера. Некото-
рые такие задачи решаются непосредственно
с помощью методов теории графов, а другие
задачи для своего решения требуют опреде-
ленной модификации обычных представле-
ний графов. Это приводит к выделению из
обширного класса графов таких подклассов,
которые имеют свою специфику и могут
быть по своей структуре и способу представ-
ления намного проще обычных графов.
Изучение числовых графов начато в 70-х
годах прошлого века [1–4]. Однако многие
свойства этих графов еще недостаточно изу-
чены. Рассмотрим некоторые необходимые
определения.
Определение 1. Числовым графом G на-
зывается тройка ),,( FUXG = , где =X {x1,
x2, …, xn} – множество вершин; =U {u1, u2,
…, un} – множество образующих; F – неко-
торая порождающая однозначная функция
двух аргументов, обладающая свойством
]),([),( uxxFXxxUu jiji =∈∃∈∀ . (1)
Относительно множеств X и U предпо-
лагается, что их элементами могут быть про-
извольные объекты: числа, векторы, матри-
цы и т.д. Однако наибольший интерес пред-
ставляет случай, когда элементы множеств
X и U – числа (целые, рациональные, дей-
ствительные, комплексные), а в качестве F
дана функция на множестве действительных
чисел. В зависимости от вида функции F
получаются различные графы, среди кото-
ОДНОРОДНЫЕ НАТУРАЛЬНЫЕ АРИФМЕТИЧЕСКИЕ ГРАФЫ С НЕЧЕТНЫМ ЧИСЛОМ ВЕРШИН
Теорія оптимальних рішень. 2006, № 5 49
рых наибольший интерес представляют натуральный арифметический
(NA-граф) и натуральный модульный (NM-граф). Это название они получили
потому, что для них { }.,,3,2,1 nNX n K==
Определение 2. Матрицей образующих для произвольного NA-графа
),( UXG = называется матрица )()( ijaGA = , у которой jiaij += , если сущест-
вует такое Uu ∈ , что jiu += , и 0=ija – для остальных значений ji, .
Матрица образующих для полного NA-графа имеет вид
−++++
−+++
++
++
++
+
=
0124321
120321
430765
327054
216503
15430
)(
nnnnn
nnnnn
nn
nn
nn
nn
GA
L
L
LLLLLLL
L
L
L
L
. (2)
Рассмотрим условия, при которых натуральный граф будет однородным
(регулярным), когда степени всех его вершин равны числу 1≥ρ . Частичные ре-
зультаты, когда натуральные графы являются набором циклов, получены в [5].
По определению матрицы образующих (2) степень любой вершины ix рав-
на числу ненулевых элементов матрицы в i -м столбце или строке с тем же но-
мером. Рассмотрим однородные степени ρ NA-графы, т.е. графы, у которых ка-
ждая строка или столбец матрицы образующих содержит ровно ρ ненулевых
элементов.
В отличие от главной диагонали матрицы, состоящей из элементов 0=iia ,
боковой диагональю назовем совокупность элементов ija , где 1+=+ nji .
Множества элементов матрицы, параллельных диагоналям, будем называть со-
ответственно главными или боковыми линиями. По определению каждая боко-
вая линия, содержащая хотя бы один ненулевой элемент, соответствует одной
образующей из множества (3, 4,…. , 2n-1). Если эта образующая нечетная, то ее
линия не пересекается с главной диагональю, и все ее элементы равны, если же
она четная, то один элемент ее линии принадлежит диагонали и равен нулю.
Определим условия, которым должно отвечать множество образующих,
чтобы NA-граф был регулярным степени 1=ρ .
Так как каждая боковая линия лежит либо выше боковой диагонали для
1+< nu , либо ниже для 1+> nu , то одной образующей не достаточно для регу-
лярности графа. Выберем две образующие. Если 11 +< nu , то первые 11 −u
И.Э. ШУЛИНОК, В.Ю. КАЮРОВ
50 Теорія оптимальних рішень. 2006, № 5
столбцов содержат по одному ненулевому элементу. Остальные столбцы долж-
на покрывать образующая 2u , поэтому ее значение определяется однозначно:
12 unu += .
Если хотя бы одна из образующих 1u или 1un + четная, то в соответствую-
щей линии матрицы существует нулевой элемент, который нарушает регуляр-
ность графа. Поэтому необходимо, чтобы 1u и 1un + обе были нечетными. То-
гда n всегда четное, поэтому справедлива
Лемма 1. Не существует регулярных степени 1 NA-графов с нечетным чис-
лом вершин.
Этот результат для обычных графов легко получить, так как регулярный
степени 1 граф является совершенным паросочетанием, а для нечетного n его
не существует. На основании этого утверждения можно сделать вывод, что для
регулярности графа к каждой образующей 1+< nu должна добавляться обра-
зующая un + , и наоборот, к каждой образующей 1+> nv должна добавляться
образующая nv − .
Кроме того, любой четной образующей iu в матрице на месте
2
,
2
ii uu
со-
ответствует нулевой элемент, что тоже может нарушать регулярность графа.
Поэтому для соблюдения регулярности графа необходимо ввести еще две обра-
зующих: левую 1
2
1 +=−
i
i
u
u и правую n
u
u i
i +=+
2
1 , которые компенсируют ука-
занный нулевой элемент, но в сумме увеличивают степень регулярности графа
на 1. Если какая-то из добавленных образующих окажется четной, то процесс
добавления двух новых образующих продлится до тех пор, пока либо он зацик-
лится, либо все новые образующие окажутся нечетными. Для количества левых
образующих существенную роль играет степень двойки в разложении образую-
щей u на множители, а для правых образующих – те же свойства числа n .
Для того чтобы изучить детальнее зависимости между образующими в ре-
гулярном графе, введем в рассмотрение граф разложения образующих )(nR ,
вершинами которого являются все образующие n -вершинного NA-графа, число
которых 32 −= nN . Все четные образующие u связаны ребрами с образующи-
ми 1
2
+
u
и
2
u
n + . Всем нечетным образующим соответствует висячая вершина,
так как на них процесс разложения образующих заканчивается. По понятным
причинам обозначим )(1 nR [ )(0 nR ] граф для нечетных (четных) n .
Пусть )2(mod1≡n . Если выбрать нечетную образующую, то ее дополнение
будет четной величиной, и необходимо добавить две образующие в процессе ее
разложения. Рассмотрим обратный процесс построения всех четных образую-
щих, начиная со всех нечетных, например для 29=n . На рисунке представлен
ОДНОРОДНЫЕ НАТУРАЛЬНЫЕ АРИФМЕТИЧЕСКИЕ ГРАФЫ С НЕЧЕТНЫМ ЧИСЛОМ ВЕРШИН
Теорія оптимальних рішень. 2006, № 5 51
граф )29(1R , состоящий из трех компонент: бинарное дерево с корнем 301 =+n
и два цикла длиной 3, вершинам которого инцидентны такие же бинарные дере-
вья.
37
30
16 44
9 51
23
52
24
13
41
55
27
46
3410
18
32
4517
31
3
4
38
4820
39
11
50
42
26
7
35 49
21
4012
22
54
28
15
43
56
29
57
1436
8
5
33
19
47
РИСУНОК. Граф 2,3,1)132(2),29( 2
1 =β=++⋅= mnR
Число возможных образующих 5532 =−n . Расположим на самом нижнем
(нулевом) уровне все нечетные образующие от 3 до 12 −n . Их можно разбить на
следующие пары: )2,12(),( 00 knkyx ++= , где
2
1
,,2,1
−
=
n
k K и разница между
ними равна 1−n . Очевидно, на эти пары разлагаются четные образующие вида
ku 4= . Будем считать, что эти образующие составляют первый уровень. Соеди-
ним их дугами, направленными сверху вниз, с соответствующими вершинами
нулевого уровня. Вершины первого уровня зависят от левых вершин нулевого
уровня по формуле kxx 4)1(2 01 =−= . Аналогично они зависят от правых вер-
шин нулевого уровня по формуле )(2 01 nyx −= . В данном примере это вершины
(4, 8, 12, ..., 52, 56). Если среди вершин первого уровня существуют пары вер-
шин ),( 11 yx , разница кодов которых 11 xy − равна 1−n , то их можно соединить
ребрами с вершиной второго уровня. Присваиваем ей код по тому же правилу:
)1(2 12 −= xx , где 1x – код левой вершины первого уровня, или )(2 12 nyx −= .
Очевидно, все остальные вершины первого уровня объединятся в такие пары и
будут вершинами второго уровня. В данном примере это вершины (6, 14, 22, 30,
38, 46, 54). На каждом уровне вершин в два раза меньше, чем на нижнем. По-
И.Э. ШУЛИНОК, В.Ю. КАЮРОВ
52 Теорія оптимальних рішень. 2006, № 5
добные построения закончатся тогда, когда на самом верхнем уровне коды лю-
бых вершин ji xx , будут удовлетворять условию 1−≠− nxx ji . Если взять ка-
кую-либо вершину k -го уровня и спуститься по левым ребрам в самую нижнюю
вершину 0x , то нетрудно установить зависимость 222 1
0 +−= +kk
k xx . По этой
причине коды k -го уровня ( 1≥k ) составляют арифметическую прогрессию с
начальным элементом 2223 1 +−⋅= +kk
a и разностью 12 += k
d , т.е. коды
22)12( +− k
l , где K,2,1=l .
Лемма 2. Число уровней графа разложения )(1 nR равно β , которое опреде-
ляется из условия 1)12(2 ++= β
mn .
Очевидно, 1≥β , поэтому первый уровень всегда существует для любого
NA-графа. На нулевом уровне число вершин )12(212/)1(2 +=−=− β
mnn . Затем
оно уменьшается в два раза на каждом уровне и на самом верхнем уровне ста-
новится равным 12 +m . В сумме число вершин на всех уровнях равно
)12)(12()2421)(12( 1 −+=+++++ +ββ
mm L . Так как все нечетные образующие
учтены на нулевом уровне, а всего образующих 1)12(232 1 −+=− +β
mn , то ос-
таются еще четные образующие, не принадлежащие ни одному уровню, и их
количество равно m2 . Назовем эти образующие остаточным множеством. Дан-
ные значения составляют арифметическую прогрессию с начальным членом
22 1 += +β
a и разностью 12 +β=d , т.е. )2,2,1(22 1
miiui K=+⋅= +β . В этом
примере это (10, 18, 26, 34, 42, 50). Каждая такая образующая разлагается на
221
2
1 +⋅=+= β
i
u
v i и 2)12(212
2
2 +++=++⋅=+= ββ
imnin
u
v i . Если li 2=
четное, то 22)122(2 +++= β
lmv принадлежит наименьшему уровню, а =2v
22 1 +⋅= +β
l – остаточному множеству. Если 12 −= li нечетное число, то обра-
зующая 22)12(1 +−= β
lv принадлежит наивысшему уровню, а ++= β )22(22 lmv
2)(22 1 ++=+ +β
lm – остаточному множеству. Это означает, что образующая из
верхнего уровня является корнем бинарного дерева, висячие вершины которого
принадлежат нулевому уровню. Другим ребром образующие верхнего уровня
соединены с образующими из остаточного множества. Так как вершины оста-
точного множества – четные образующие, то от них идет одно ребро в вершины
верхнего уровня, а другое – в вершину этого же множества. Поэтому подграф
графа )(1 nR на данном множестве образует циклы.
Образующая 1+= nu принадлежит наивысшему уровню β , так как
2)12(21 ++=+ β
mn . С другой стороны она не связана с остаточным множест-
ОДНОРОДНЫЕ НАТУРАЛЬНЫЕ АРИФМЕТИЧЕСКИЕ ГРАФЫ С НЕЧЕТНЫМ ЧИСЛОМ ВЕРШИН
Теорія оптимальних рішень. 2006, № 5 53
вом, так как иначе существовала бы образующая из этого множества χ , которая
по формулам должна быть либо nn 2)11(2 =−+ , либо 2)1(2 =−+ nn . Однако
таких образующих в NA-графе не существует, так как 123 −≤≤ nui .
Таким образом, конструкция графа )(1 nR становится ясной. Он состоит из
набора циклов одинаковой длины с общим числом вершин m2 , и каждая из
этих вершин соединена с бинарным деревом с наибольшим уровнем β . Кроме
того, существует отдельная компонента, которая является таким же деревом с
верхней вершиной (корнем) 1+= nu .
Заключение. Изучение регулярности натуральных арифметических графов
может послужить началом для решения проблемы изоморфизма числовых гра-
фов; структура регулярных графов определяется заданием числа вершин и их
степенью. Это поможет в дальнейшем решать новые проблемы, которые час-
тично уже затронуты в [6–7].
І.Е. Шулінок, В.Ю. Каюров
ОДНОРІДНІ НАТУРАЛЬНІ АРИФМЕТИЧНІ ГРАФИ З НЕПАРНИМ ЧИСЛОМ ВЕРШИН
Для натуральних арифметичних графів знайдено спосіб переліку регулярних графів. Вводить-
ся поняття графа розкладу твірних. Доведено низку тверджень про його властивості, що дає
змогу однозначно визначати структуру регулярних графів.
I.E. Shulinok, V.Yu. Kayurov
HOMOGENEOUS NATURAL ARITHMETICAL GRAPHS WITH ODD NAMBER OF
VERTICES
A way of enumeration of regular graphs for natural arithmetical graphs was found. A definition of
graphs decomposition of generatrixes was introduced. It is proved some statements about its proper-
ties. This gives a possibility to determine uniquely the structure of regular graphs.
1. Асельдеров З.М., Донец Г.А. Представление и восстановление графов. - Киев: Наук.
думка, 1991. – 178 с.
2. Григорьян Ю.Г. Классификация и статистические свойства арифметических графов //
Кибернетика. – 1979. – №6. – С. 9–12.
3. Григорьян Ю.Г., Адонц А.М. Свойства регулярних натуральних арифметических гра-
фов // Там же. – 1990. – №5. – С. 112–113.
4. Донець Г.П., Нєженцев Ю.І. Арифметичні графи та їх представлення // Доп.
АН УРСР. Сер.А. – 1990. – №11. – С. 5–8.
5. Донец Г.А., Шулинок И.Э. Оптимальное представление однородных деревьев первого
ранга в классе А-графов // Компьютерная математика. – Киев: Ин-т кибернетики
им. В.М.Глушкова НАН Украины, 2001. –Т.2. – С. 61–68.
И.Э. ШУЛИНОК, В.Ю. КАЮРОВ
54 Теорія оптимальних рішень. 2006, № 5
6. Донец Г.А. Необходимые и достаточные условия связности арифметических графов
// Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова
НАН Украины, 1992. – С. 69–74.
7. Донец Г.А., Асельдерова И.М. Условия однородности арифметических графов //
Оптимизация и ее приложения. –Киев: Ин-т кибернетики им. В.М.Глушкова
НАН Украины, 1993. – С. 23–30.
Получено 07.07.2006
|