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 назв. — рос.

Минимальную длину цикла, проходящего через выбранную вершину простого графа, назовем цикловым индикатором вершины. Цикловой индикатор графа определим как наибольшее значение цикловых индикаторов его вершин. Регулярный граф называется графом с иррегулярным цикловим индикатором, если его цикловой индикатор отличается от обхвата. В работе приводится полное решение оптимизационной задачи вычисления максимального размера e = e(v) для графов заданного порядка v с цикловым индикатором, превышающим выбранный параметр d, d > 2. Рассматривается задача нахождения наименьшего порядка для k-регулярного графа с цикловим индикатором d. Приводится алгебраическая конструкция беcконечной семьи регулярных графов заданной степени с возрастающим иррегулярным цикловим индикатором асимптотически максимального размера. Построенная бесконечная последовательность графов заданной степени p^s, где p — произвольное нечетное простое, а s — произвольное натуральное число, образует семью графов малого мира. Обсуждаются криптографические применения этой конструкции.