Oб экстремальной теории графов и символьных вычислениях
Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой инди...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85391 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-85391 |
|---|---|
| record_format |
dspace |
| spelling |
Устименко, В.А. 2015-08-01T15:25:38Z 2015-08-01T15:25:38Z 2013 Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/85391 519.176,519.157.2 Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой индикатор отличается от обхвата. В работе приводится полное решение оптимизационной задачи вычисления максимального размера e = e(v) для графов заданного порядка v с цикловым индикатором, превышающим выбранный параметр d, d > 2. Рассматривается задача нахождения наименьшего порядка для k-регулярного графа с цикловим индикатором d. Приводится алгебраическая конструкция беcконечной семьи регулярных графов заданной степени с возрастающим иррегулярным цикловим индикатором асимптотически максимального размера. Построенная бесконечная последовательность графов заданной степени p^s, где p — произвольное нечетное простое, а s — произвольное натуральное число, образует семью графов малого мира. Обсуждаются криптографические применения этой конструкции. Мiнiмальну довжину цикла, що проходить крiзь обрану вершину простого графу, назвемо цикловим показником вершини. Цикловий показник графу визначимо як найбiльший цикловий показник його вершини. Регулярний граф називається графом з iрегулярним цикловим показником, якщо його цикловий показник вiдрiзняється вiд обхвату. В роботi наводиться повний розв’язок оптимiзацiйної задачi обчислення максимального розмiру e = e(v) графiв заданого порядку v з цикловим показником, що перевищує обраний параметр d, d > 2. Розглядається також задача знаходження найменшого порядку для k-регулярного графу з цикловим показником d. Наводиться алгебраїчна конструкцiя нескiнченної сiм’ї регулярних графiв заданого степеня зi зростаючим iрегулярним цикловим показником асимптотично максимального розмiру. Побудована нескiнченна послiдовнiсть графiв заданого степеня p^s, де p — довiльне непарне просте, а s — довiльне натуральне число, утворює сiм’ю графiв малого свiту. Обговорюється криптографiчне застосування цiєї конструкцiї. Let us refer to the minimal length of a cycle passing through the given vertex of a simple graph as the cycle indicator of this vertex. The cycle indicator of a graph will be defined as the maximal cycle indicator of its vertices. A regular graph will be called the graph with irregular cycle indicator if this indicator differs from the girth. The solution of the optimization problem of computation of the maximal size e = e(v) of a graph of order v with the size greater than d, d >2, is given. We consider also the algebraic construction of an infinite family of regular graphs of the given degree with growing irregular cycle indicator of the asymptotically largest size. The constructed sequence of graphs with the given degree p^s, where p is an arbitrary odd prime and s is any positive integer, forms the family of small-world graphs. We discuss the cryptographical applications of this construction. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Oб экстремальной теории графов и символьных вычислениях Про екстремальну теорiю графiв i символьнi перетворення On the extremal graph theory and symbolic computations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Oб экстремальной теории графов и символьных вычислениях |
| spellingShingle |
Oб экстремальной теории графов и символьных вычислениях Устименко, В.А. Інформатика та кібернетика |
| title_short |
Oб экстремальной теории графов и символьных вычислениях |
| title_full |
Oб экстремальной теории графов и символьных вычислениях |
| title_fullStr |
Oб экстремальной теории графов и символьных вычислениях |
| title_full_unstemmed |
Oб экстремальной теории графов и символьных вычислениях |
| title_sort |
oб экстремальной теории графов и символьных вычислениях |
| author |
Устименко, В.А. |
| author_facet |
Устименко, В.А. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Про екстремальну теорiю графiв i символьнi перетворення On the extremal graph theory and symbolic computations |
| description |
Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой индикатор отличается
от обхвата. В работе приводится полное решение оптимизационной задачи вычисления максимального размера e = e(v) для графов заданного порядка v с цикловым индикатором, превышающим выбранный параметр d, d > 2. Рассматривается задача нахождения наименьшего порядка для k-регулярного графа с цикловим индикатором d.
Приводится алгебраическая конструкция беcконечной семьи регулярных графов заданной степени с возрастающим иррегулярным цикловим индикатором асимптотически
максимального размера. Построенная бесконечная последовательность графов заданной
степени p^s, где p — произвольное нечетное простое, а s — произвольное натуральное
число, образует семью графов малого мира. Обсуждаются криптографические применения этой конструкции.
Мiнiмальну довжину цикла, що проходить крiзь обрану вершину простого графу, назвемо
цикловим показником вершини. Цикловий показник графу визначимо як найбiльший цикловий показник його вершини. Регулярний граф називається графом з iрегулярним цикловим
показником, якщо його цикловий показник вiдрiзняється вiд обхвату. В роботi наводиться
повний розв’язок оптимiзацiйної задачi обчислення максимального розмiру e = e(v) графiв заданого порядку v з цикловим показником, що перевищує обраний параметр d, d > 2. Розглядається також задача знаходження найменшого порядку для k-регулярного графу
з цикловим показником d. Наводиться алгебраїчна конструкцiя нескiнченної сiм’ї регулярних графiв заданого степеня зi зростаючим iрегулярним цикловим показником асимптотично максимального розмiру. Побудована нескiнченна послiдовнiсть графiв заданого степеня p^s, де p — довiльне непарне просте, а s — довiльне натуральне число, утворює сiм’ю
графiв малого свiту. Обговорюється криптографiчне застосування цiєї конструкцiї.
Let us refer to the minimal length of a cycle passing through the given vertex of a simple graph
as the cycle indicator of this vertex. The cycle indicator of a graph will be defined as the maximal
cycle indicator of its vertices. A regular graph will be called the graph with irregular cycle indicator
if this indicator differs from the girth. The solution of the optimization problem of computation
of the maximal size e = e(v) of a graph of order v with the size greater than d, d >2, is given.
We consider also the algebraic construction of an infinite family of regular graphs of the given
degree with growing irregular cycle indicator of the asymptotically largest size. The constructed
sequence of graphs with the given degree p^s, where p is an arbitrary odd prime and s is any positive
integer, forms the family of small-world graphs. We discuss the cryptographical applications of this
construction.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/85391 |
| citation_txt |
Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. |
| work_keys_str_mv |
AT ustimenkova obékstremalʹnoiteoriigrafovisimvolʹnyhvyčisleniâh AT ustimenkova proekstremalʹnuteoriûgrafivisimvolʹniperetvorennâ AT ustimenkova ontheextremalgraphtheoryandsymboliccomputations |
| first_indexed |
2025-12-07T20:58:10Z |
| last_indexed |
2025-12-07T20:58:10Z |
| _version_ |
1850884584380563456 |