О гамильтоновости арифметических графов
Исследуются вопросы существования гамильтонова цикла в арифметических графах. Рассматриваются различные разности между двумя наибольшими образующими. Доказываются теоремы о существовании гамильтоновых циклов для разностей, равных 1, 2, 3, 4....
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/85037 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О гамильтоновости арифметических графов / А.Г. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 24-28. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85037 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-850372015-07-19T03:02:27Z О гамильтоновости арифметических графов Донец, А.Г. Исследуются вопросы существования гамильтонова цикла в арифметических графах. Рассматриваются различные разности между двумя наибольшими образующими. Доказываются теоремы о существовании гамильтоновых циклов для разностей, равных 1, 2, 3, 4. Досліджуються питання існування гамільтонових циклів у арифметичних графів. Розглядаються всілякі різниці між двома найбільшими твірними. Доводяться теореми про існування гамільтонових циклів для різниць, рівних 1, 2, 3, 4. This paper presents some investigations on existence Hamiltonian circle in arithmetical graphs. It was shown that only various relations between two largest generatricsas can be used for the addressing questions. We proved some new theorems about existence Hamiltonian circles with relations 1, 2, 3, 4. 2013 Article О гамильтоновости арифметических графов / А.Г. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 24-28. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85037 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Исследуются вопросы существования гамильтонова цикла в арифметических графах. Рассматриваются различные разности между двумя наибольшими образующими. Доказываются теоремы о существовании гамильтоновых циклов для разностей, равных 1, 2, 3, 4. |
| format |
Article |
| author |
Донец, А.Г. |
| spellingShingle |
Донец, А.Г. О гамильтоновости арифметических графов Теорія оптимальних рішень |
| author_facet |
Донец, А.Г. |
| author_sort |
Донец, А.Г. |
| title |
О гамильтоновости арифметических графов |
| title_short |
О гамильтоновости арифметических графов |
| title_full |
О гамильтоновости арифметических графов |
| title_fullStr |
О гамильтоновости арифметических графов |
| title_full_unstemmed |
О гамильтоновости арифметических графов |
| title_sort |
о гамильтоновости арифметических графов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85037 |
| citation_txt |
О гамильтоновости арифметических графов / А.Г. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 24-28. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT donecag ogamilʹtonovostiarifmetičeskihgrafov |
| first_indexed |
2025-07-06T12:12:03Z |
| last_indexed |
2025-07-06T12:12:03Z |
| _version_ |
1836899552137838592 |
| fulltext |
24 Теорія оптимальних рішень. 2013
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Исследуются вопросы существо-
вания гамильтонова цикла в ариф-
метических графах. Рассматри-
ваются различные разности меж-
ду двумя наибольшими образую-
щими. Доказываются теоремы о
существовании гамильтоновых цик-
лов для разностей, равных 1, 2, 3, 4.
А.Г. Донец, 2013
ÓÄÊ 519.8
À.Ã. ÄÎÍÅÖ
Î ÃÀÌÈËÜÒÎÍÎÂÎÑÒÈ
ÀÐÈÔÌÅÒÈ×ÅÑÊÈÕ ÃÐÀÔÎÂ
Введение. Арифметический граф (А-граф)
принадлежит к общему классу числовых
графов
∗
и представляет собой пару (X,U),
где nNX ∈ – множество вершин, а NU ∈ –
множество образующих, и ji xx < смежны,
если ( )njiUxx ji ≤≤∈+ ,1 .
Если u < n + 1, то вершина n не охвачена
этой образующей, если u > n + 1, то вершина
1 не охвачена этой образующей. Вопрос о
существовании в арифметическом графе га-
мильтонова цикла упирается в анализ обра-
зующих этого графа, так как степень каждой
вершины при этом должна быть ≥ 2. В дан-
ном случае особую роль приобретает обра-
зующая u = n + 1, которая охватывает обе
вершины 1 и n. Будем искать минимальное
количество образующих, для которых граф
будет гамильтоновым. Очевидно, что для лю-
бых двух образующих граф не будет гамиль-
тоновым, так как при этом либо вершина 1,
либо вершина n будет иметь степень ≤ 1.
Теорема 1. Арифметический граф с образу-
ющими
1
, 1,
2
n
U n n n
+
= + +
гамильтонов.
Доказательство. Первые две образующие
представляют собой цепь, начинающуюся в
вершине n, и образуют последовательность
n, 1, n – 1, 2, n – 2, … . Если n = 2k, то она
заканчивается в вершине k, а если n = 2k+1,
то цепь заканчивается в вершине k + 1.
∗
Шулинок Г.А. О поиске кратчайших путей в
числовых графах // Теория оптимальных решений. –
2012. – С. 42–46.
О ГАМИЛЬТОНОВОСТИ АРИФМЕТИЧЕСКИХ ГРАФОВ
Теорія оптимальних рішень. 2013 25
Чтобы образовать гамильтонов цикл, необходимо эту конечную вершину
соединить с вершиной n. Для этого и необходима образующая
1
.
2
n
u n
+
= +
Следствие. Двойственный арифметический граф будет иметь образующие
1
1, 2, 1 .
2
n
U n n
+
= + + +
Действительно, тогда соответствующая цепь будет иметь конечные
вершины 1 и
+
2
1n
, чем и определяется последняя образующая. Из теоремы
и следствия логично сделать также вывод о том, что любой гамильтонов граф с
минимальным числом образующих должен всегда иметь образующую u = n + 1.
Пример гамильтонова графа для n = 11 и двойственного к нему показан на рис. 1.
РИС. 1. А-граф с U = (11,12,17) и двойственный с U = (7,12,13)
Будем обозначать ∆ – разницу между образующей u = n + 1 и ближайшей к
нему. В теореме были рассмотрены графы с 1=∆ . Рассмотрим графы с 2=∆ ,
т. е. графы с u = n + 1 и u = n – 1. Здесь возможны различные случаи:
а) пусть 2n k= . Тогда эти образующие обеспечивают получение одной цепи
,1, 2,3, 4,5, ,2, 1n n n n− − −K . Тогда достаточно одной образующей 12 −= nu ,
чтобы объединить эту цепь в гамильтонов цикл;
б) 12 += kn . Тогда образующие создают две цепи – одна с четными
номерами, одна – с нечетными. В зависимости от значения k это приводит к
двум вариантам;
б1) 14 += ln . При этом нечетные номера образуют цепь 4 1,1,4l l+ −
1,3,4 3,5, ,2 1l l− − +K , а четные номера образуют цепь 4 ,2,4 2,4,4 ,2,4 2,4,l l l l− −
4 4,6, ,2 .l l− K Здесь достаточно добавить одну образующую 6 1u l= + , чтобы
соединить две цепи в гамильтонов цикл. При этом соединятся максимальный
номер одной цепи с минимальным номером другой;
1
2
3
4
5
11
10
9
8
7
6
1
2
3
4
5
6
11
10
9
8
7
А.Г. ДОНЕЦ
26 Теорія оптимальних рішень. 2013
б2) 34 += ln . При этом нечетные номера образуют цепь
4 3,1,4 1,3,4 1,5, ,2 1l l l l+ + − +K , а четные номера – цепь 4 2,2,4 ,4,l l+
4,4 2,6, ,2 2l l− +K . Здесь не существует одной образующей, достаточной, для
того, чтобы объединить две цепи в гамильтонов цикл. Поэтому необходимо две
образующие: либо 1 6 3u l= + , 2 6 5u l= + , либо 1 8 5u l= + , 2 4 3.u l= + Но послед-
ний случай сводится к случаю 1,∆ = поэтому он отпадает. Остается первый
случай. Таким образом, была доказана
Теорема 2. При 2=∆ для гамильтоновости графа достаточно трех
образующих, за исключением 34 += ln , когда требуется четыре образующих.
Для двойственного графа имеем те же случаи. На рис. 2 показан пример
графа для 13.n =
РИС. 2. А-граф с n = 13, U = (12, 14, 19)
Рассмотрим теперь А-графы с 3=∆ .
Теорема 3. Для гамильтоновости А-графа с 3=∆ необходимо и достаточно
четных образующих.
Доказательство. В этом случае две первые образующие 1 1,u n= +
2 2.u n= − Они образуют две цепи, для превращения их в гамильтонов цикл
понадобятся еще две образующих. Рассмотрим три случая:
а) ( )0 mod 3n ≡ . Первую цепь составляют вершины ,1, 3,4, ,3, 2.n n n− −K
Вторую цепь составляют вершины, номера которых равны ( )1 mod 3− .
Начальный отрезок цепи ,,5,4,2,1 K−− nn . Конец цепи зависит от значения n.
Если 2n k= , то конец цепи равен 1k − , а если n =2k + 1, то – 1k + ;
б) ( )1 mod 3 .n ≡ Первая цепь состоит из вершин, номера которых равны
( )1 mod 3 . Начальный отрезок цепи ,1, 3,4, ,n n − K а конечная вершина находит-
ся так же, как и в случае а).
Вторая цепь состоит из вершин 1,2, 4,5, ,3, 2;n n n− − −K
в) ( )2 mod 3 .n ≡ Первую цепь составляют последовательность вершин
,1, 3,4, ,2, 1.n n n− −K Вторая цепь состоит из вершин, номера которых равны
( )0 mod 3 . Начальный отрезок цепи 2,3, 5,6, .n n− − K А конечная вершина
определяется как: для kn 2= конец цепи равен 2+k , а для 12 += kn конец
цепи равен 1k + .
1
3
5
7
9
1
1 2
4
6
8
1
1
О ГАМИЛЬТОНОВОСТИ АРИФМЕТИЧЕСКИХ ГРАФОВ
Теорія оптимальних рішень. 2013 27
Во всех случаях для образования гамильтонова цикла необходимо добавить
еще две образующих, а меньшим количеством нельзя обойтись. На рис. 3
показан пример для А-графа с 16.n =
РИС. 3. А-граф с n = 16, U = (14, 17, 21, 31)
Рассмотрим теперь А-графы с номер 4.∆ = Для них справедлива
Теорема 4. Для гамильтоновости А-графов с 4∆ = при 4n k= , 4 3k +
достаточно четырех образующих, при 4 2n k= + достаточно трех образующих и
при 4 1n k= + необходимо 5 образующих.
Доказательство. Рассмотрим последовательно все случаи, учитывая то, что
образующие равны 1 1,u n= + 2 3;u n= −
а) 4 .n k= Образующие составляют две цепи. Первая проходит по вершинам
,1, 4,5, ,4, 3.n n n− −K Вторая цепь проходит по вершинам 1,2,n −
5,6, ,3, 2n n− −K . Чтобы объединить эти цепи в гамильтонов цикл, необходимо
добавить две образующих 1 22 1, 2 5,u n u n= − = − либо 1 22 2, 2 4;u n u n= − = −
б) 4 3.n k= + Образующие составляют три цепи. Первая цепь проходит по
вершинам ,1, 4,5, ,3, 2.n n n− −K Вторая цепь проходит по вершинам 1,2,n −
5,6, ,2 2.n k− +K И третья цепь составляет последовательность 3,4,n n− −
7,8, ,2k− K . Здесь существуют два способа добавления двух образующих, чтобы
получить гамильтонов цикл. Первый: 1 22 3, 4 2.u n u k= − = + Но последняя
образующая равна 1,n − и тогда приходим к случаю 2,∆ = что по теореме 2
достаточно четырех образующих. Второй способ: 1 22 , 8 2.u n k u k= + = + Это
дает четыре образующих;
в) 4 2.n k= + В этом случае две образующие составляют две цепи. В первой
цепи чередуются вершины, номера которых имеют номера ( )1 mod 4 и
( )2 mod 4 . Во второй цепи чередуются вершины с номерами ( )3 mod 4 и
( )0 mod 4 . Первая цепь имеет вид ,1, 4,5, ,2, 1,n n n− −K а вторая имеет вид
2,3, 7,7, ,4, 3.n n n− − −K Очевидно, что здесь достаточно одной образующей
4 3,u n= − чтобы объединить две цепи в гамильтонов цикл;
г) 4 1.n k= + В этом случае образующие составляют три цепи. В первой
цепи находятся все вершины, номера которых равны ( )1 mod 4 , а именно
1
13
4
10
2
5
8
16
11
14
15
12
9
6
3
7
А.Г. ДОНЕЦ
28 Теорія оптимальних рішень. 2013
,1, 4,5, ,2 1.n n k− +K Во второй цепи чередуются вершины, номера которых
равны ( )2 mod 4 и ( )0 mod 4 , а именно: 1,2, 5,6, ,4, 3.n n n− − −K В третьей цепи
находятся все вершины, номера которых равны ( )3 mod 4 , а именно:
2,3, 5,7, ,2 1.n n k− − −K Существует единственная возможность объединить три
цепи в гамильтонов цикл с помощью двух образующих. Это 1 22 3, 4 .u n u k= − =
Но последняя образующая равна 1,n − а это случай 2,∆ = и по теореме 2
достаточно трех образующих. Следовательно, необходимо добавить 3 обра-
зующих, что в сумме дает пять образующих.
На рис. 4 показан пример для А-графа с 18.n =
РИС. 4. А-граф с n = 18, U = (15, 19, 33)
Можно продолжать исследования для А-графов с большим числом ,∆
используя те же приемы. Вопрос сводиться к перечислению цепей, где встре-
чаются различные вершины с номерами ( )mod .i ∆
А.Г. Донець
ПРО ГАМІЛЬТОНОВІСТЬ АРИФМЕТИЧНИХ ГРАФІВ
Досліджуються питання існування гамільтонових циклів у арифметичних графів. Розгля-
даються всілякі різниці між двома найбільшими твірними. Доводяться теореми про існування
гамільтонових циклів для різниць, рівних 1, 2, 3, 4.
A.G. Donets
WHETHER ARITHMETICAL GRAPHS ARE HAMILTONIAN
This paper presents some investigations on existence Hamiltonian circle in arithmetical graphs. It was
shown that only various relations between two largest generatricsas can be used for the addressing
questions. We proved some new theorems about existence Hamiltonian circles with relations 1, 2, 3, 4.
Получено 14.03.2013
1
5
9
13
17
18
14
10
6
2 15
11
7
3
4
8
12
16
|