Oб экстремальной теории графов и символьных вычислениях
Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой инди...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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 |
irk-123456789-85391 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-853912015-08-02T03:01:55Z Oб экстремальной теории графов и символьных вычислениях Устименко, В.А. Інформатика та кібернетика Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой индикатор отличается от обхвата. В работе приводится полное решение оптимизационной задачи вычисления максимального размера 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. 2013 Article Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/85391 519.176,519.157.2 ru Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Устименко, В.А. Oб экстремальной теории графов и символьных вычислениях Доповіді НАН України |
| description |
Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой индикатор отличается
от обхвата. В работе приводится полное решение оптимизационной задачи вычисления максимального размера e = e(v) для графов заданного порядка v с цикловым индикатором, превышающим выбранный параметр d, d > 2. Рассматривается задача нахождения наименьшего порядка для k-регулярного графа с цикловим индикатором d.
Приводится алгебраическая конструкция беcконечной семьи регулярных графов заданной степени с возрастающим иррегулярным цикловим индикатором асимптотически
максимального размера. Построенная бесконечная последовательность графов заданной
степени p^s, где p — произвольное нечетное простое, а s — произвольное натуральное
число, образует семью графов малого мира. Обсуждаются криптографические применения этой конструкции. |
| format |
Article |
| author |
Устименко, В.А. |
| author_facet |
Устименко, В.А. |
| author_sort |
Устименко, В.А. |
| title |
Oб экстремальной теории графов и символьных вычислениях |
| title_short |
Oб экстремальной теории графов и символьных вычислениях |
| title_full |
Oб экстремальной теории графов и символьных вычислениях |
| title_fullStr |
Oб экстремальной теории графов и символьных вычислениях |
| title_full_unstemmed |
Oб экстремальной теории графов и символьных вычислениях |
| title_sort |
oб экстремальной теории графов и символьных вычислениях |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2013 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85391 |
| citation_txt |
Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT ustimenkova obékstremalʹnojteoriigrafovisimvolʹnyhvyčisleniâh |
| first_indexed |
2023-10-18T19:31:02Z |
| last_indexed |
2023-10-18T19:31:02Z |
| _version_ |
1796147175919452160 |