Об изоморфизме регулярных NM-графов
Regular natural modular graphs with arbitrary number of generatices are considered. The first classification of regular NM-graphs is made. For NM-graphs with two generatrices an isomorphizm problem is solved completely. The paper tries to enumerate isomorphic regular NM-graphs.
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2005 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84931 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Об изоморфизме регулярных NM-графов / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 100-106. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860267824852762624 |
|---|---|
| author | Шулинок, Г.А. |
| author_facet | Шулинок, Г.А. |
| citation_txt | Об изоморфизме регулярных NM-графов / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 100-106. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Regular natural modular graphs with arbitrary number of generatices are considered. The first classification of regular NM-graphs is made. For NM-graphs with two generatrices an isomorphizm problem is solved completely. The paper tries to enumerate isomorphic regular NM-graphs.
|
| first_indexed | 2025-12-07T19:03:23Z |
| format | Article |
| fulltext |
100 Теорія оптимальних рішень. 2005, № 4
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Впервые рассматриваются регу-
лярные NM-графы с произвольным
числом образующих. Проведена
первичная классификация регу-
лярных NM-графов. Полностью
решена проблема изоморфизма
регулярных NM-графов с двумя
образующими. Предпринята по-
пытка перечисления изоморфных
регулярных NM-графов.
Г.А. Шулинок, 2005
ÓÄÊ 519.1
Ã.À. ØÓËÈÍÎÊ
ÎÁ ÈÇÎÌÎÐÔÈÇÌÅ ÐÅÃÓËßÐÍÛÕ
NM-ÃÐÀÔÎÂ
Введение. Структура NM-графов (натураль-
ных модульных графов) как отдельного под-
класса числовых графов достаточно изучена
[1-3]. В последнее время особый интерес вы-
зывают вопросы изоморфизма числовых
графов [4-5]. Данная работа является про-
должением [5], которой дан исчерпывающий
ответ на вопрос об изоморфизме NM-графов
с двумя образующими. В работе делается по-
пытка обосновать общий подход к проблеме
изоморфизма произвольных NM-графов. При
этом особое внимание уделяется регулярным
NM-графам в предположении, что решение
задачи об изоморфизме этих графов даст не-
обходимые и достаточные условия для ре-
шения классической задачи изоморфизма в
применении к числовым графам.
Пусть заданы две матрицы инцидентности
вершин графов, из которых 1A соответствует
графу 1G , а 2A - графу 2G . Эти графы будут
изоморфными )( 21 GG ≅ , если найдется та-
кая перестановочная матрица P , для кото-
рой справедливо
T
PPAA 12 = .
Матрице P соответствует перестановка
=
niii
n
p
K
K
21
21
, такая, что если на мно-
жестве вершин графа 2G сделать переста-
новку p , то полученный граф станет полной
копией графа 1G . Рассмотрим матрицу обра-
зующих полного NM-графа.
ОБ ИЗОМОРФИЗМЕ РЕГУЛЯРНЫХ NM-ГРАФОВ
Теорія оптимальних рішень. 2005, № 4 101
−−−−
−
−
−
=
04321
31012
22101
13210
K
KKKKKK
K
K
K
nnnn
n
n
n
A . (1)
Каждой образующей 11 −≤≤ nu в матрице A соответствует две последова-
тельности чисел u , расположенных параллельно над и под главной диагональю,
состоящей из нулей. Матрица образующих произвольного NM-графа отличается
от матрицы (1) тем, что на месте несуществующих образующих стоят нули. По-
этому степень i -й вершины is в таких графах равна количеству ненулевых эле-
ментов в i -й строке (столбце) матрицы образующих. Построим график степеней
вершин графа исходя из указанных свойств матрицы образующих:
1) если 12 −≤ nu , то образующая u добавляет к степени вершины j величину
≤≤+−
−≤≤+
≤≤
=∆
;1для,1
;1для,2
;1для,1
)(
njun
unju
uj
uj (2)
2) если 12 −> nu , то образующая u добавляет к степени вершины j величину
≤≤+
≤≤+−
−≤≤
=∆
.1для,1
;1для,0
;1для,1
)(
nju
ujun
unj
uj (3)
Единственная образующая при )2(mod0≡n , которая добавляет всегда единицу
к степени произвольной вершины , это
2
n
u = . Построим на рис. 1 графики
1 2 3 2019181716151413121110987654 2221
1 2 3 2019181716151413121110987654 2221
б
a
j
j
S
j
S
j
РИС. 1. Графики образующих: а - 71 =u ; б - 162 =u
Г.А. ШУЛИНОК
102 Теорія оптимальних рішень. 2005, № 4
образующих используя (2) - (3) для }16,7{,22 == Un . Граф с множеством
образующих },,,{ 21 muuuU K= имеет вектор степеней ),,,( 21 nsssS K= , где
∑
∈
=∆=
Uu
jj njus ,,2,1);( K . (4)
Путем наложения таких графиков для каждой образующей получим суммар-
ный график функции степеней вершин, которую обозначим )(GS . Очевидно,
что если графики образующих имеют центральную ось симметрии, то и график
)(GS тоже будет симметричным. Поэтому все свойства таких графиков будут
изучаться только для их левой половины. Графики образующих для (2) имеют
подъем в точке uj = , а для образующих (3) – спуск в точке unj −= . При по-
строении графика функции )(GS некоторые подъемы могут накладываться на
спуски и нейтрализовать друг друга. Это возможно только в случае, если
)( lknuu lk ≠=+ . Если таких образующих нет, то число подъемов функции
)(GS будет равно числу образующих типа (2), а число спусков – числу обра-
зующих типа (3). В качестве примера рассмотрим график )(GS на рис. 2.
1 2 3 2019181716151413121110987654 2221 j
S
j
РИС. 2. График функции степеней вершин
Подсчитав число подъемов и спусков графика (напоминаем, что все делает-
ся для левой половины графика, т.е. 111 ≤≤ j ), находим, что оно равно 5 (три
спуска и два подъема). Это означает, что должно быть не меньше 5 образую-
щих. Так как 3)(min =GS , а 5)(max =GS , то число образующих должно быть в
этих пределах, что определяет окончательно число образующих, равное 5.
Подъемы на графике имеются в точках 8,6=j , что соответствует образующим
8,6 21 == uu , а спуски - в точках 10,4,2=j . Это соответствует отношениям
103 =− un , 44 =− un , 25 =− un , откуда 123 =u , 184 =u и 205 =u . Непосред-
ственно можно убедиться, что эти образующие соответствуют данному графику.
ОБ ИЗОМОРФИЗМЕ РЕГУЛЯРНЫХ NM-ГРАФОВ
Теорія оптимальних рішень. 2005, № 4 103
Вектор степеней графа )85,104,43(=S , где верхний индекс указывает чис-
ло вершин с данной степенью. Если вектор считать одним из инвариантов гра-
фа, то этому вектору соответствует много NM-графов. Назовем график функции
)(GS для заданного вектора S каноническим, если он является монотонно воз-
растающим, построим его на рис. 3.
1 2 3 2019181716151413121110987654 2221 j
S
j
РИС. 3. Канонический график функции степеней вершин
Граф, соответствующий каноническому графику функции )(GS , назовем
каноническим. Здесь число подъемов равно два, а спусков не будет никогда по
правилу построения. Но число образующих должно быть, по крайней мере, три.
Третья образующая не должна иметь ни подъемов, ни спусков, и такая обра-
зующая существует для четных n и имеет вид
2
3
n
u = . Таким образом, канони-
ческий график )(GS строится единственным образом с помощью трех обра-
зующих 21 =u (точка подъема 2=j ), 72 =u (точка подъема 7=j ) и 113 =u .
Очевидно, что число образующих канонического графа равно )(min GS . Если
значения графика увеличить всюду на единицу, то тогда пришлось бы использо-
вать четыре образующих, хотя подъемов было бы по-прежнему два. В этом слу-
чае две образующие в сумме должны не допускать ни подъемов, ни спусков.
Такие образующие существуют и имеют вид 3u и 34 unu −= , но при этом кано-
нический график строится не единственным образом. Все полученные результа-
ты можно подытожить в виде утверждений.
Утверждение 1. Для изоморфных NM-графов число образующих не являет-
ся инвариантом.
Утверждение 2. Канонический граф, реализующий заданный вектор степе-
ней ),,,( 21 nsssS K= , содержит наименьшее число образующих.
В процессе исследования проблемы изоморфизма NM-графов приходится
пользоваться графиком степеней вершин, при этом часть графика может при-
Г.А. ШУЛИНОК
104 Теорія оптимальних рішень. 2005, № 4
надлежать образующей
2
n
u = (для четных n ) или набору пар образующих типа
u и un − . Остальные образующие являются надстройкой над ними. Пары обра-
зующих, отдельно взятые в различных комбинациях, представляют собой регу-
лярные графы. Действительно, для них любой график степеней вершин не со-
держит ни подъемов, ни спусков, т.е. является константой, что и есть определе-
нием регулярности графа. Тем самым доказана
Лемма 1. Все регулярные NM-графы степени k2 имеют множество обра-
зующих вида },,,,,,,{ 1221 unununuuuU kk −−−= KK , где
−
≤≤
2
1
1 1
n
u ,
),,2,1( ki K= . Регулярный NM-граф степени 12 +k возможен лишь при четном
числе вершин и отличается от графа степени k2 дополнительной образующей
2
n
u = .
Отсюда вытекает, что регулярный граф с одной образующей существует
только для четного числа вершин. Рассмотрим регулярные графы степени 2,
множества образующих которых представляются в виде },{ unuU −= , где
11 −≤≤ nu . Таких множеств
−
2
1u
, но некоторые из них могут соответство-
вать изоморфным графам. Известно [5], что если 1u и 2u взаимно просты, а
также nuu =+ 21 , то такой граф является гамильтоновым циклом.
Лемма 2. Число NM-графов с двумя образующими, являющихся гамильто-
новыми циклами, равно
2
)(nϕ
, где )(nϕ - функция Эйлера.
Доказательство. Очевидно, что если 1),(НОД =− unu , то и 1),(НОД =nu ,
а всего таких значений u равно )(nϕ . Среди пар ),( unu − всегда unu −< , по-
этому таких пар, обе образующие которых взаимно просты, равно
2
)(nϕ
. Пока-
жем, что существует такая перестановочная матрица P , которая переводит лю-
бой гамильтонов цикл с образующими },{ unuU −= в такой же цикл с обра-
зующими }1,1{ −= nU . Этой матрице для nk ,,2,1 K= соответствует переста-
новка
−+
=
k
uk
p
)1(1
. Действительно, любая линейная форма 1)1( +−ku при
1),(НОД =nu пробегает все вычеты по umod , если k пробегает значения
от 1 до n .
Теперь можно полностью описать структуру регулярных графов с двумя
образующими.
ОБ ИЗОМОРФИЗМЕ РЕГУЛЯРНЫХ NM-ГРАФОВ
Теорія оптимальних рішень. 2005, № 4 105
Теорема. Граф ),( 21 uuGn - плоский граф; если 21 uun +≥ , то он состоит
из kuun +−− 21 циклов, из которых k циклов имеют длину
k
uu 21 +
и
21 uun −− циклов имеют длину 4, где ),(НОД 21 uuk = .
Доказательство. Если 21 uun +< , то граф является подграфом фактор-
графа, поэтому он плоский. Пусть 21 uun +≥ .
Рассмотрим подграф ),( 2121
uuG uu + графа ),( 21 uuGn . Он состоит из k цик-
лов ),,2,1( kiC K , где ),(НОД 21 uuk = . Цикл iC состоит из последовательности
вершин [ ])mod()( 211 uutui ++ , где 1,,1,0 21 −
+
=
k
uu
t K . Каждая новая вершина с
номером )1(,21 ≥++ juuj добавляется к внешней стороне цикла
( )( )][mod 21 uuijCi +≡ и окружает вершину j , образуя новый цикл длиной 4 с
вершинами ),,,( 2121 ujjujuuj ++++ . В результате длина внешнего цикла iC
не изменится, а вершина j закроется вершиной 21 uuj ++ . Этот процесс мо-
жет быть продолжен для всех циклов iC , пока j не достигнет 21 uun −− . В ито-
ге получаем k циклов длиной
k
uu 21 +
и 21 uun −− циклов длиной 4.
Пример. },{ 96=U . Для 15=n получим (рис. 4, ребра выделены полу-
жирным) три цикла длиной 5. Добавляя вершины (увеличивая n ) до 25 получа-
ем
вершина 16 окружает вершину 1, образуя цикл (16, 7, 1, 10);
вершина 17 окружает вершину 2, образуя цикл (17, 8, 2, 10);
… … …
вершина 25 окружает вершину 10, образуя цикл (25, 16, 10, 19).
1 2
4
13
7
15
3
10 8
145
11 9
6
12
16
22
25
19
17
20
23 24
18
21
РИС. 4. Циклы в графе с двумя образующими: },{ 96=U , 25=n
Г.А. ШУЛИНОК
106 Теорія оптимальних рішень. 2005, № 4
Таким образом, получаем еще 101525 =− четырехвершинных циклов.
Теорема позволяет построить алгоритм плоской укладки NM-графа с двумя
образующими.
Заключение. В данной работе заложены основы для определения достаточ-
ных условий изоморфности регулярных NM-графов. Из-за ограничения на объ-
ем статьи в ней представлены не все полученные результаты. В дальнейшем
планируется в двух-трех статьях представить полное и подробное решение этой
проблемы.
Г.О. Шулінок
ПРО ІЗОМОРФІЗМ РЕГУЛЯРНИХ МОДУЛЬНИХ ГРАФІВ
Розглядаються регулярні NM-графи з довільним числом твірних. Проведена первинна
класифікація регулярних NM-графів. Повністю розв’язана задача ізоморфізму регулярних
NM-графів з кількістю твірних до 2. Виконана спроба перелічення ізоморфних регулярних
NM-графів.
G.A. Shulinok
ISOMORPHIZM OF REGULAR NM-GRAPHS
Regular natural modular graphs with arbitrary number of generatices are considered. The first
classification of regular NM-graphs is made. For NM-graphs with two generatrices an isomorphizm
problem is solved completely. The paper tries to enumerate isomorphic regular NM-graphs.
1. Шулинок И.Э. Об одном классе числовых графов // Теория и приложения методов
оптимизации. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1998. –
С. 24–29.
2. Шулинок И.Э. О связности натуральных модульных графов // Кибернетика и
системный анализ. – 1998. – № 5. – С. 50–53.
3. Шулинок И.Э. О связности и цикломатическом числе натуральных модульных
графов // Теория оптимальных решений. – Киев: Ин-т кибернетики
им. В.М. Глушкова НАН Украины, 1999. – С. 51–57.
4. Донец Г.А, Шулинок Г.А. Об изоморфизме натуральных арифметических графов //
Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М. Глушкова
НАН Украины, 2003. – С. 47–53.
5. Шулінок Г.О. Про ізоморфізм натуральних модульних графів // Теорія оптимальних
рішень. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2004. –
С. 69–73.
Получено 23.03.2005
|
| id | nasplib_isofts_kiev_ua-123456789-84931 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T19:03:23Z |
| publishDate | 2005 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шулинок, Г.А. 2015-07-17T05:53:58Z 2015-07-17T05:53:58Z 2005 Об изоморфизме регулярных NM-графов / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 100-106. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84931 519.1 Regular natural modular graphs with arbitrary number of generatices are considered. The first classification of regular NM-graphs is made. For NM-graphs with two generatrices an isomorphizm problem is solved completely. The paper tries to enumerate isomorphic regular NM-graphs. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об изоморфизме регулярных NM-графов Isomorphizm of regular nm-graphs Article published earlier |
| spellingShingle | Об изоморфизме регулярных NM-графов Шулинок, Г.А. |
| title | Об изоморфизме регулярных NM-графов |
| title_alt | Isomorphizm of regular nm-graphs |
| title_full | Об изоморфизме регулярных NM-графов |
| title_fullStr | Об изоморфизме регулярных NM-графов |
| title_full_unstemmed | Об изоморфизме регулярных NM-графов |
| title_short | Об изоморфизме регулярных NM-графов |
| title_sort | об изоморфизме регулярных nm-графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84931 |
| work_keys_str_mv | AT šulinokga obizomorfizmeregulârnyhnmgrafov AT šulinokga isomorphizmofregularnmgraphs |