ЭЛЕКТРИЧЕСКАЯ МОДЕЛЬ С ИДЕАЛЬНЫМИ ЭЛЕМЕНТАМИ ДЛЯ ПОИСКА КРАТЧАЙШЕГО ПУТИ НА ВЗВЕШЕННОМ ОРИЕНТИРОВАННОМ ГРАФЕ
Journal: Automation of technological and business processes (Vol.10, No. 2)Publication Date: 2018-06-07
Authors : Гнатенко В.Ю. Ступень П.В. Дікусар К.В. Шутєєв Е.І;
Page : 38-43
Keywords : электрическая модель; взвешенный ориентированный граф; кратчайший путь; метод узловых потенциалов; метод установления;
Abstract
Рассмотрена проблема определения кратчайшего пути во взвешенном ориентированном графе с применением электрической модели с идеальными диодами, источниками напряжения и тока. Проведены теоретические исследования в области математического моделирования электрических схем с идеальными элементами. Рассмотрен пример определения кратчайшего пути в заданном взвешенном ориентированном графе. В задачах небольшой размерности можно использовать аналоговые электрические модели. Однако для больших графов аналоговые модели становятся весьма громоздкими из-за необходимости включения в каждую цепь изолированного источника электрической энергии, а точность решения низкой из-за не идеальности характеристик элементов. В данной статье рассматривается развитие модели представления взвешенного ориентированного графа без использования структурной матрицы или каких-либо других топологических матриц. Вместо этого предлагается формировать и обрабатывать в процессе анализа список ветвей с присущими им характеристиками и параметрами. Целью работы является обоснование электрической модели для поиска кратчайшего пути во взвешенном ориентированном графе, представление алгоритма для реализации и иллюстрации эффективности метода. Так как исходная электрическая цепь не содержит накопителей энергии и в ней в принципе невозможен переходный процесс, предлагается преобразовать исходную электрическую цепь в динамическую путем присоединения к каждому узлу схемы по емкости, другой конец которой соединить с базисным узлом, не принадлежащим данной схеме и общим для всех емкостей. В результате становится возможным протекание переходного процесса, по окончании которого токи емкостей станут равными нулю и не будут оказывать влияния на распределение токов и напряжений в схеме.
Other Latest Articles
- ВИКОРИСТАННЯ СУЧАСНИХ ТЕХНОЛОГІЙ У ВИКЛАДАННІ ТЕХНІЧНИХ ДИСЦИПЛІН
- РОЗРОБКА АЛГОРИТМУ РОБОТИ МІКРОКОНТРОЛЕРНОГО ПРИСТРОЮ ДЛЯ ВИЗНАЧЕННЯ СТИГЛОСТІ ВИНОГРАДУ
- IMPLEMENTATION OF A STANDARDIZED INFORMATION MANAGEMENT SYSTEM INTO ACTIVITY OF SCIENTIFIC AND TECHNICAL LIBRARY
- АРХІТЕКТУРА КЛІЄНТ-СЕРВЕР НА ОСНОВІ ДОДАТКА ВІДДІЛУ АСПІРАНТУРИ ТА ДОКТОРАНТУРИ ОНАХТ
- OVERVIEW OF PROBLEMS IN TEXT-DATA PROCESSING AND CREATING A CLIENT-SERVER APPLICATION DEVOTED TO REFERENCES MANAGERS
Last modified: 2018-12-03 23:01:27