Oб экстремальной теории графов и символьных вычислениях
Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой инди...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85391 |
| 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: | Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862749067951472640 |
|---|---|
| author | Устименко, В.А. |
| author_facet | Устименко, В.А. |
| citation_txt | Oб экстремальной теории графов и символьных вычислениях / В.А. Устименко // Доповiдi Нацiональної академiї наук України. — 2013. — № 2. — С. 42–49. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| 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.
|
| first_indexed | 2025-12-07T20:58:10Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-85391 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T20:58:10Z |
| publishDate | 2013 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| 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 |
| spellingShingle | Oб экстремальной теории графов и символьных вычислениях Устименко, В.А. Інформатика та кібернетика |
| title | Oб экстремальной теории графов и символьных вычислениях |
| title_alt | Про екстремальну теорiю графiв i символьнi перетворення On the extremal graph theory and symbolic computations |
| title_full | Oб экстремальной теории графов и символьных вычислениях |
| title_fullStr | Oб экстремальной теории графов и символьных вычислениях |
| title_full_unstemmed | Oб экстремальной теории графов и символьных вычислениях |
| title_short | Oб экстремальной теории графов и символьных вычислениях |
| title_sort | oб экстремальной теории графов и символьных вычислениях |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85391 |
| work_keys_str_mv | AT ustimenkova obékstremalʹnoiteoriigrafovisimvolʹnyhvyčisleniâh AT ustimenkova proekstremalʹnuteoriûgrafivisimvolʹniperetvorennâ AT ustimenkova ontheextremalgraphtheoryandsymboliccomputations |