vguitВестник Воронежского государственного университета инженерных технологийProceedings of the Voronezh State University of Engineering Technologies2226-910X2310-1202VSUET10.20914/2310-1202-2018-2-73-76vguit-1716Research ArticleИнформационные технологии, моделирование и управлениеInformation technologies, modeling and managementОценка мощности полного множества альтернатив паретовских подграфов в графеPower estimation of the full set of alternatives to Paret's subgraphs in a graphБугаевЮ. В.BugaevYu. V.

д.ф-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия

Dr. Sci. (Phys.-Math.), professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia

y_bugaev52@mail.ruЧикуновС. В.ChikunovS. V.

к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия

Cand. Sci. (Engin.), associate professor, higher mathematics and information technology department, Revolution Av., 19 Voronezh, 394036, Russia

chiksv@rambler.ruВоронежский государственный университет инженерных технологийРоссияVoronezh state university of engineering technologiesRussian Federation2018290520188027376Copyright © Бугаев Ю.В., Чикунов С.В., 20182018Бугаев Ю.В., Чикунов С.В.Bugaev Y.V., Chikunov S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestnik-vsuet.ru/vguit/article/view/1716

На практике часто встречаются задачи построения оптимального подграфа определённого вида в заданном графе. В качестве возможных приложений используются задачи поиска оптимальной структуры технологических сетей, проектирования архитектуры вычислительных устройств, моделирования искусственного интеллекта и многие другие. Всё более актуальными становятся многокритериальные варианты указанных задач. Существенным сдерживающим фактором совершенствования методов многокритериальной оптимизации на графах является проблема их экспоненциальной вычислительной сложности, вызванной большой размерностью задачи. Ряд данных свидетельствует, что теоретическая оценка сложности, построенная для методов полного перебора, не соответствует действительности, и сделанные выводы не имеют достаточного обоснования. Среди эффективных решений наибольший интерес представляет так называемое полное множество альтернатив, мощность которого может быть на порядки ниже, чем мощность множества Парето. С учётом перечисленных фактов в данной работе изложен результат исследований, состоящий в построении оценки сверху для мощности полного множества альтернатив задачи нахождения парето-оптимальных подграфов для заданного графа.

In practice problems of creation of an optimum subgraph of a certain look in a given graph count often meet. As possible annexes problems of search of optimum structure of technological networks, design of architecture of computers, modeling of artificial intelligence and many others are used. More and more relevant are multicriteria options of the specified tasks. An essential limiting factor of improvement of methods of multicriteria optimization on graphs is the problem of their exponential computing complexity caused by big dimension of a task. A number of data demonstrates that the theoretical assessment of complexity constructed for methods of full search isn't true, and the drawn conclusions have no sufficient justification. Among effective decisions the so-called complete set of alternatives which power can be lower on orders, than the power of the Pareto set is of the greatest interest. Taking into account the listed facts in this work the result of researches consisting in creation of assessment from above for the power of a complete set of alternatives of a problem of stay is stated pareto-optimal subgraphs for a given graph.

графподграфмножество Паретополное множество альтернативgraphsubgraphPareto setcomplete set of alternativesReferencesМелькумов В.Н., Кузнецов И.С., Кобелев В.Н. Задача поиска оптимальной структуры тепловых сетей // Научный вестник Воронежского государственного архитектурно-строительного университета. Строительство и архитектура. 2011. № 2. С. 37–42.Melkumov V.N., Kuznetsov I.S., Kobelev V.N. The problem of finding the optimal structure of heat networks. Nauchnyi vestnik VGASU [Scientific Bulletin of the Voronezh state University of architecture and construction. Construction and architecture] 2011. no. 2. pp. 37-42. (in Russian)Ильясова Н.Ю., Корепанов А.О., Чикулаев П.М. Метод выделения центральных линий кровеносных сосудов на диагностических изображениях // Компьютерная оптика. 2006. № 29. С. 146–150.Ilyasova N. Yu,. Korepanov A.O., Chikulaev P.M. Method of selection of Central lines of blood vessels on diagnostic images. Komp’yuternaya optika [Computer optics] 2006. no. 29. pp. 146-150. (in Russian)Попов А.Ю. О реализации алгоритма Форда-Фалкерсона в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. 2014. № 9. С. 162–180.Popov A. Yu. On the implementation of the algorithm of Ford-Fulkerson in a computing system, with many streams of commands and a single data stream. Nauka I obrazovanie [Science and education] 2014. no. 9. pp. 162-180. (in Russian)Williams J., Massie Ch., George A.D., Richardson J. et al. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration // ACM Transactions onReconfigurable Technology and Systems. 2010. V. 3, №. 4. Art. №. 19.Williams J., Massie Ch., George A.D., Richardson J. et al. Characterization of Fixed and Reconfigurable Multi-Core Devices for Application Acceleration. ACM Transactions onReconfigurable Technology and Systems. 2010. vol. 3, no. 4. art.no. 19.Nguyen Q.H., Ong Y.S., Krasnogor N.A. Study on the Design Issues of Memetic Algorithm // IEEE Congress on Evolutionary Computation (CEC 2007). 2007. P. 2390–2397.Nguyen Q.H., Ong Y.S., Krasnogor N.A. Study on the Design Issues of Memetic Algorithm. IEEE Congress on Evolutionary Computation (CEC 2007). 2007. pp. 2390–2397.Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study // IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics. 2006. V. 36. № 1. P. 141–152.Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics. 2006. vol. 36. no. 1. pp. 141–152.Jie J., Zeng J. Improved Mind Evolutionary Computation for Optimizations // Proceedings of 5 th World Congress on Intelligent Control and Automation. 2004. V. 3. P. 2200–2204.Jie J., Zeng J. Improved Mind Evolutionary Computation for Optimizations. Proceedings of 5 th World Congress on Intelligent Control and Automation. 2004. vol. 3. pp. 2200–2204.Liang J.J., Qu B.Y., Suganthan P.N. Problem Definitions and Evaluation Criteria for the CEC 2014 Special Session and Competition on Single Objective Real-Parameter Numerical Optimization. Technical Report 201311. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China; Technical Report. Singapore: NanyangTechnologicalUniversity, 2013. 32 p.Liang J.J., Qu B.Y., Suganthan P.N. Problem Definitions and Evaluation Criteria for the CEC 2014 Special Session and Competition on Single Objective Real-Parameter Numerical Optimization. Technical Report 201311. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China; Technical Report. Singapore: NanyangTechnologicalUniversity, 2013. 32 p.Бугаев Ю.В., Музалевский Ф.А. Полиномиальная оценка мощности множества паретовских путей в графе // Вестник Нижегородского университета. 2013. № 2–1. С. 168–170.Bugaeev Yu.V., Muzalevsky F.A. Polynomial estimation of power of the set of Paret paths in the graph. Vestnik Nizhegorodskogo universiteta [Proceedings of Nizhny Novgorod University] 2013. no. 2-1. pp. 168-170. (in Russian)Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учеб. пособие. М. БИНОМ: Лаборатория знаний, 2010. 311 с.Kostyukova N.I. Graphs and their application. Kombinatornue algoritmy dlya programistov [Combinatorial algorithms for programmers: Studies. benefit] Moscow, BINOM, 2010. 311 p. (in Russian)

The authors declare that there are no conflicts of interest present.