1. |
Шулінок І.Е. Розв'язання задач оптимального представлення числових графів та дослідження умов побудови на них ефективних алгоритмів: Автореф. дис... канд. фіз.-мат. наук: 01.05.01 / І.Е. Шулінок ; НАН України. Ін-т кібернетики ім. В.М.Глушкова. — К., 2004. — 20 с.: рис. — укp.Досліджено числові графи, а також питання застосування їх властивостей для побудови на них ефективних алгоритмів. Розглянуто підкласи числових графів - арифметичні та модульні графи. Доведено, що будь-який граф може бути представлений у класі даних графів. Повністю описано однорідні натуральні арифметичні графи та розраховано таблиці, що дають змогу відтворювати такі графи з заданими параметрами. Розв'язано задачу оптимального представлення довільних графів у класі числових графів для дерев першого рангу, або зірок, для двох циклів довільної довжини, а також інших типів графів. Для модульних графів знайдено необхідні та достатні умови зв'язності, виведено формулу для обчислення цикломатичного числа, повністю описано структуру натуральних модульних графів з двома твірними. Розроблено нові методи представлення графів у класі числових графів. Показано, що багато графів, які використовуються у різних практичних галузях, можуть бути представлені як числові графи у розширеному трактуванні. Доведено, що базові алгоритми на графах, такі, як пошук в глибину або в ширину, діють набагато краще, якщо попередньо графи представити як числові. Доведено, що для числових графів можна створити такі алгоритми, дія яких зводиться до видачі готового розв'язку поставленої задачі. Наведено два приклади таких алгоритмів для модульних графів з двома твірними та їх довільним числом. Скачати повний текст
Індекс рубрикатора НБУВ: В126.3,0 + Шифр НБУВ: РА329903
Рубрики:
|