Об изоморфизме регулярных NM-графов

Об изоморфизме регулярных 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:
Bibliographische Detailangaben
Datum:2005
1. Verfasser: Шулинок, Г.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2005
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:http://dspace.nbuv.gov.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
id irk-123456789-84931
record_format dspace
spelling irk-123456789-849312015-07-18T03:01:35Z Об изоморфизме регулярных 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. 2005 Article Об изоморфизме регулярных NM-графов / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 100-106. — Бібліогр.: 5 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84931 519.1 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
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.
format Article
author Шулинок, Г.А.
spellingShingle Шулинок, Г.А.
Об изоморфизме регулярных NM-графов
Теорія оптимальних рішень
author_facet Шулинок, Г.А.
author_sort Шулинок, Г.А.
title Об изоморфизме регулярных NM-графов
title_short Об изоморфизме регулярных NM-графов
title_full Об изоморфизме регулярных NM-графов
title_fullStr Об изоморфизме регулярных NM-графов
title_full_unstemmed Об изоморфизме регулярных NM-графов
title_sort об изоморфизме регулярных nm-графов
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2005
url http://dspace.nbuv.gov.ua/handle/123456789/84931
citation_txt Об изоморфизме регулярных NM-графов / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 100-106. — Бібліогр.: 5 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT šulinokga obizomorfizmeregulârnyhnmgrafov
first_indexed 2025-07-06T12:03:11Z
last_indexed 2025-07-06T12:03:11Z
_version_ 1836898993702961152
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

Ähnliche Einträge