О минимальном числе образующих полного подграфа NA-графа
Исследуются натуральные арифметические графы. Определяются необходимые и достаточные условия существования полных подграфов в таких графах. Досліджуються натуральні арифметичні графи. З’ясовується мінімальна кількість твірних для існування повного підграфа заданого порядку. Доведено ряд тверджень, щ...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2009 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46640 |
| 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: | О минимальном числе образующих полного подграфа NA-графа / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 61-68. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46640 |
|---|---|
| record_format |
dspace |
| spelling |
Шулинок, Г.А. 2013-07-04T18:56:12Z 2013-07-04T18:56:12Z 2009 О минимальном числе образующих полного подграфа NA-графа / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 61-68. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46640 519.8 Исследуются натуральные арифметические графы. Определяются необходимые и достаточные условия существования полных подграфов в таких графах. Досліджуються натуральні арифметичні графи. З’ясовується мінімальна кількість твірних для існування повного підграфа заданого порядку. Доведено ряд тверджень, що дозволяють визначати наявність повного підграфа у заданому довільному натуральному арифметичному графі. Natural arithmetic graphs are considered. Minimal generatrixes set for existence of complete graph of appropriate level is investigated. A number of proposition was proved to determine existence of complete subgraph in the target natural arithmetic graph. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О минимальном числе образующих полного подграфа NA-графа Про мінімальну кількість твірних повного підграфа NA-графа About minimal generatrixes set for complete subgraph of the NA-graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О минимальном числе образующих полного подграфа NA-графа |
| spellingShingle |
О минимальном числе образующих полного подграфа NA-графа Шулинок, Г.А. |
| title_short |
О минимальном числе образующих полного подграфа NA-графа |
| title_full |
О минимальном числе образующих полного подграфа NA-графа |
| title_fullStr |
О минимальном числе образующих полного подграфа NA-графа |
| title_full_unstemmed |
О минимальном числе образующих полного подграфа NA-графа |
| title_sort |
о минимальном числе образующих полного подграфа na-графа |
| author |
Шулинок, Г.А. |
| author_facet |
Шулинок, Г.А. |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про мінімальну кількість твірних повного підграфа NA-графа About minimal generatrixes set for complete subgraph of the NA-graph |
| description |
Исследуются натуральные арифметические графы. Определяются необходимые и достаточные условия существования полных подграфов в таких графах.
Досліджуються натуральні арифметичні графи. З’ясовується мінімальна кількість твірних для існування повного підграфа заданого порядку. Доведено ряд тверджень, що дозволяють визначати наявність повного підграфа у заданому довільному натуральному арифметичному графі.
Natural arithmetic graphs are considered. Minimal generatrixes set for existence of complete graph of appropriate level is investigated. A number of proposition was proved to determine existence of complete subgraph in the target natural arithmetic graph.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46640 |
| citation_txt |
О минимальном числе образующих полного подграфа NA-графа / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2009. — № 8. — С. 61-68. — Бібліогр.: 2 назв. — рос. |
| work_keys_str_mv |
AT šulinokga ominimalʹnomčisleobrazuûŝihpolnogopodgrafanagrafa AT šulinokga promínímalʹnukílʹkístʹtvírnihpovnogopídgrafanagrafa AT šulinokga aboutminimalgeneratrixessetforcompletesubgraphofthenagraph |
| first_indexed |
2025-11-25T22:51:28Z |
| last_indexed |
2025-11-25T22:51:28Z |
| _version_ |
1850574828759678976 |
| fulltext |
Теорія оптимальних рішень. 2009, № 8 61
ÒÅÎÐIß
ÎÏÒÈÌÀËÜÍÈÕ
ÐIØÅÍÜ
Исследуются натуральные ариф-
метические графы. Определяют-
ся необходимые и достаточные
условия существования полных
подграфов в таких графах.
Г.А. Шулинок, 2009
ÓÄÊ 519.8
Ã.À. ØÓËÈÍÎÊ
Î ÌÈÍÈÌÀËÜÍÎÌ ×ÈÑËÅ
ÎÁÐÀÇÓÞÙÈÕ ÏÎËÍÎÃÎ ÏÎÄÃÐÀÔÀ
NA-ÃÐÀÔÀ
Введение. Существование полного подграфа
в NA-графах – интересная проблема, приме-
нима к поиску хроматического числа, изомор-
физма и другим задачам [1]. Несмотря на ее
важность, проблема рассматривается впервые.
Данная работа ставит перед собой цель на-
хождения необходимых и достаточных усло-
вий существования полного подграфа поряд-
ка h , т. е. существования подграфа
h
K в
произвольном натуральном арифметическом
графе )(UG
n
.
В работе [2] дан исчерпывающий ответ по
поводу существования подграфа порядка 3.
Относительно полного подграфа порядка 4
имеет место следующее свойство.
Лемма 1. Минимальное число образую-
щих, необходимых для построения полного
подграфа порядка 4 в связном NA-графе, со-
ставляет 5.
Доказательство. Предположим, что суще-
ствует подграф NA-графа, а именно 4K с че-
тырьмя образующими. В нем должно быть
четыре треугольных грани (рис. 1). Согласно
лемме 3 и свойству в доказательстве теоремы
1 из [2] в треугольнике число нечетных обра-
зующих равно нулю или двум. Если все об-
разующие графа – четные, то это противоре-
чит условию связности графа. Остаются
только два варианта: три образующих – чет-
ные и три – нечетные; четыре образующих –
нечетные и две – четные. Первый случай воз-
можен только при нечетных образующих
),( 41 xx , ),( 42 xx и ),( 43 xx . Если четырем
образующим соответствует шесть ребер, то
двум парам ребер должны соответствовать
Г.А. ШУЛИНОК
62 Теорія оптимальних рішень. 2009, № 8
одинаковые образующие. Учитывая четность образующих, равные образующие
соответствуют двум ребрам, обязательно имеющие общую вершину. Но это
противоречит общему определению NA-графов. Таким образом, первый случай
возможен только при шести образующих. Во втором случае четыре нечетных
образующих можно выстроить в последовательность, в которой две соседние
образующие принадлежат одному треугольнику. Не нарушая общности, пусть
они соответствуют ребрам ),( 41 xx , ),( 43 xx , ),( 32 xx и ),( 21 xx . Здесь можно вы-
брать две пары одинаковых образующих, каждая из которых не имеет общей
вершины – это ),(),( 4231 xxxx = и ),(),( 2143 xxxx = . Однако, в этом случае два
треугольника 431 xxx и 421 xxx совпадают, а 32 xx = , что противоречит началь-
ным условиям. Если оставить только одну пару одинаковых образующих, про-
тиворечия не будет. Это и доказывает лемму.
x4
x1
x
2
x
3
РИС. 1. Полный подграф порядка 4
Из леммы 1 можно определить критерий для полного подграфа 4K .
Лемма 2. Для того чтобы в NA-графе с пятью образующими
),,,,( 54321 uuuuuGn был полный подграф, достаточно, чтобы образующие отве-
чали следующим свойствам:
1) 54321 uuuuu <<<< ;
2) 321 uuu >+ ;
3) )2(mod0321 ≡++ uuu ;
О МИНИМАЛЬНОМ ЧИСЛЕ ОБРАЗУЮЩИХ ДЛЯ ПОЛНОГО ПОДГРАФА NA-ГРАФА
Теорія оптимальних рішень. 2009, № 8 63
4)
2
321
3
uuu
un
−+
−≥ ;
5) 425132 uuuuu +=+= .
Доказательство. Рассмотрим полный подграф на рис. 1, в котором есть
3 треугольные циклы, содержащие вершину 1x . Определим из образующих дан-
ную вершину согласно свойствам треугольной грани. Имеем:
2
321
1
uuu
x
−+
= ;
2
532
1
uuu
x
−+
= ;
2
431
1
uuu
x
−+
= . (1)
Из соотношений (1) легко получаем
513
532321 2
22
uuu
uuuuuu
+=⇒
−+
=
−+
, (2)
5142
431532
22
uuuu
uuuuuu
+=+⇒
−+
=
−+
, (3)
423
431321 2
22
uuu
uuuuuu
+=⇒
−+
=
−+
. (4)
Из равенств (2), (3) и (4) получаем свойство 5.
Свойства 2, 3 и 4 гарантируют достаточное количество треугольных циклов
графа. Условие 1 – не ограничивает общность и добавлено для удобства.
Согласно свойствам 2 и 3 в графе имеет место треугольная грань с верши-
нами (1). Рассмотрим вершину 134 xuu −= , которая будет связана с вершиной 1x
по определению, с вершиной 2x – благодаря образующей 4u , а с вершиной 3x –
образующей 5u . Таким образом, имеем полный подграф.
Заметим, что условия в лемме 2 налагаются, в основном, на образующие.
Таким образом, можно расширить критерий существования полного подграфа
для произвольного связного NA-графа с количеством образующих превышаю-
щих 4 и произвольным числом вершин.
Следствие. Произвольный NA-граф с количеством образующих, превы-
шающим 4, имеет подграф, изоморфный 4K , если среди его образующих най-
дутся пять, отвечающих свойствам леммы 2.
Любой подграф NA-графа можно представить в виде арифметического гра-
фа. Поскольку условия леммы 2 касаются в основном множества образующих,
то указанный в условии подграф останется натуральным. Значит, к нему приме-
нима лемма 2.
Г.А. ШУЛИНОК
64 Теорія оптимальних рішень. 2009, № 8
В отличие от леммы 2 следствие дает только достаточные условия сущест-
вования полного подграфа порядка 4. Это учитывая то, что полный подграф
можно получить и с помощью шести различных образующих.
Рассмотрим полный подграф порядка 5. На рис. 2 показан его пример. Бу-
дем считать вершины и образующие упорядоченными по индексам.
Как видно на рис. 2, первые 4 вершины составляют полный подграф поряд-
ка 4. Очевидно, что первые 4 вершины можно с помощью пяти образующих со-
единить в полный подграф. Данные вершины соединяются с вершиной 5x до-
полнительными ребрами. Определим минимальное количество образующих,
требуемых дополнительных ребер.
В полном подграфе 5K можно выделить пять подграфов порядка 4. Опреде-
лим их. Имеем:
1) подграф из вершин 4321 ,,, xxxx ; достаточно пять образующих вида
43542432413312211 ,,,, xxuxxuxxxxuxxuxxu +=+=+=+=+=+= .
Легко показать, что и выполняются другие условия
леммы 2;
2) подграф из вершин ; достаточно шесть образующих вида
;
3) подграф из вершин ; достаточно пять образующих вида
;
4) подграф из вершин ; достаточно шесть образующих вида
;
5) подграф из вершин ; достаточно пять образующих вида:
.
Таким образом 4 ребра – порождаются
образующими , , и обра-
зующей . Обозначая образующую как , а как , полу-
чим следующий результат.
Лемма 3. Минимальное количество образующих, необходимое для сущест-
вования полного подграфа порядка 5 составляет 7.
Определим критерий существования полного подграфа порядка 5. Пусть за-
дан NA-граф и образующие упорядочены в соответ-
ствии с индексами. Из рис. 2 видно, что два из полных подграфов графа порядка
4 составляются с помощью шести образующих. Один из этих подграфов –
О МИНИМАЛЬНОМ ЧИСЛЕ ОБРАЗУЮЩИХ ДЛЯ ПОЛНОГО ПОДГРАФА NA-ГРАФА
Теорія оптимальних рішень. 2009, № 8 65
, второй – . Остальные подграфы составляются с помо-
щью трех различных пятиэлементных подмножеств образующих графа. Рас-
смотрим данные подмножества: ,
и . Они должны соответствовать условиям леммы 2. Та-
ким образом, , и . Отсюда несложно
сформулировать свойство, подобное лемме 2 для подграфов порядка 5.
Лемма 4. В NA-графе с семью образующими, содержащем полный подграф,
изоморфный 5K , образующие соответствуют следующим условиям:
1) ;
2) подграф на пяти первых образующих соответствует условиям леммы 2;
3) ;
4) ;
5)
2
321
4
uuu
un
−+
−≥ .
Доказательство. Условие 1 добавлено для удобства. Условие 5 гарантирует
достаточное количество ребер. Условия с 2 по 4 вытекают из леммы 2 и под-
множеств образующих исходного графа, обеспечивающие подграфы . Итак,
рассмотрим полный подграф, построенный на первых пяти образующих, кото-
рый является, очевидно, 4K , состоящий из вершин . С вершиной
их соединяют образующие и (рис. 2).
Заметим, что как и в случае с полным подграфом порядка 4, достаточно
проверить наличие полного подграфа на первых пяти образующих и соответст-
вия свойству симметричности множества образующих.
Обобщим результаты, распространив их на произвольный полный подграф.
Минимальное количество образующих, необходимых для полного подграфа по-
рядка 3 составляет 3, для подграфа порядка 4 – 5, а для подграфа порядка
5 – 7. Легко предположить, что для получения полного подграфа 6K необходи-
мо 9, а для получения 7K – 11 образующих. Отсюда получается соотношение
минимального количества образующих для получения полного подграфа поряд-
ка : . Докажем следующее утверждение.
Теорема 1. Минимальное необходимое число образующих в NA-графе, со-
держащем полный подграф sK , составляет 32 −s .
Г.А. ШУЛИНОК
66 Теорія оптимальних рішень. 2009, № 8
Доказательство. Для случая с доказано в [2]. Леммы 2 и 3 свидетель-
ствуют о справедливости утверждения для и . Докажем это утвер-
ждение для произвольного .
Находим критерий существования полного подграфа в заданном натураль-
ном арифметическом графе.
Теорема 2. Граф с образующими содержит полный подграф sK ,
3>s , тогда и только тогда, когда выполняются следующие условия:
1) ;
2) ;
3) образующие составляют полный подграф порядка ;
4)
2
321 uuu
s
−+
≥ .
Доказательство. Рассмотрим граф из условия теоремы, в котором есть пол-
ный подграф порядка , составленный из первых образующих исход-
ного графа. Проведем индукцию по порядку полного подграфа.
Для графа порядка 4 это соответствует условиям леммы 2. Для графа поряд-
ка 5 – леммы 4.
Пусть имеем полный подграф порядка , соответствующий условиям дан-
ной теоремы. Докажем, что теорема выполняется для графа порядка . Реб-
ра, соединяющие вершины графа sK с вершиной сообщаются различными
образующими, поскольку имеет место последовательность неравенств
. Последние
две суммы превышают все образующие подграфа sK . Очевидно, что
, . Относительно остальных образующих
графа имеем , т. е. .
Отсюда получается, что образующая сообщает ребро . Подобно,
ребро сообщается образующей и так далее, до образующей .
Таким образом, все вершины графа sK соединяются с вершиной , образуя
полный подграф требуемого порядка, что и требовалось доказать.
О МИНИМАЛЬНОМ ЧИСЛЕ ОБРАЗУЮЩИХ ДЛЯ ПОЛНОГО ПОДГРАФА NA-ГРАФА
Теорія оптимальних рішень. 2009, № 8 67
x
1
x
2
x3
x
4
x
5
u1
u2
u3
u3
u4
u5
u5
u
4
u6
u7
РИС. 2. Полный граф порядка 5 и его образующие
Заключение. Данное исследование является полезным для последующих
работ по оценке хроматического числа произвольных натуральных арифметиче-
ских графов.
Г.О. Шулінок
ПРО МІНІМАЛЬНУ КІЛЬКІСТЬ ТВІРНИХ ПОВНОГО ПІДГРАФА NA-ГРАФА
Досліджуються натуральні арифметичні графи. З’ясовується мінімальна кількість твірних для
існування повного підграфа заданого порядку. Доведено ряд тверджень, що дозволяють ви-
значати наявність повного підграфа у заданому довільному натуральному арифметичному
графі.
Г.А. ШУЛИНОК
68 Теорія оптимальних рішень. 2009, № 8
G.A. Shulinok
ABOUT MINIMAL GENERATRIXES SET FOR COMPLETE SUBGRAPH
OF THE NA-GRAPH
Natural arithmetic graphs are considered. Minimal generatrixes set for existence of complete graph
of appropriate level is investigated. A number of proposition was proved to determine existence of
complete subgraph in the target natural arithmetic graph.
1. Берж К. Теория графов и ее применение. – М: Изд-во иностр. лит., 1962. – 319 с.
2. Донец Г.А., Шулинок И.Э. О хроматическом числе натуральных арифметических графов
с тремя образующими // Теория оптимальных решений. – Киев. Ин-т кибернетики
им. В.М. Глушкова НАН Украины, 2008. – С. 50 – 60.
Получено 20.03.2009
|