|
Аннотация
В период становления теории графов возникало немало таких задач, решение которых предполагало построение некоторых алгоритмов (достаточно вспомнить, например, задачу о кенигсбергских мостах, или задачу Гамильтона). При этом, как правило, не накладывалось никаких ограничений на сложность алгоритмов, а лишь рассматривался вопрос их существования. Внедрение вычислительной техники поставило и перед математикой, и перед теорией графов проблему нахождения не произвольных алгоритмов, позволяющих решать те или иные классы задач, а таких алгоритмов, которые допускали бы практическую реализацию с использованием современных вычислительных устройств. Так возникла проблема практической разрешимости задач: найти эффективный алгоритм решения задачи.
В данной курсовой работе рассматривается алгоритм построения минимального множества сечений контуров обратной связи связного графа методом структурно-матричного анализа. Результат данной работы является частью системы, разрабатываемой в рамках программы проектирования автономных необитаемых подводных аппаратов (АНПА).
1. Введение
1.1. Глоссарий
Множеством сечений контуров обратной связи направленного графа называется такое множество дуг, удаление которых разрывает все направленные контуры.
Контуром называется однократная замкнутая последовательность ребер (дуг), где все вершины имеют степень два.
Структурное число A представляет собой совокупность столбцов ak, то есть
A = {a1, a2,…, an}, ai ? aj (i ? j).
Столбцы ak в свою очередь представляют собой множества элементов aik:
ak = {a1k, a2k,…, amk}, aik ? ajk (i ? j),
которые изоморфны всем деревьям графа анализируемой схемы.
1.2. Описание предметной области
Активное развитие вычислительной техники в последнее время позволило использовать ее в различных областях науки. В частности – в теории электрических цепей, для анализа сложных схем. Однако применение вычислительной техники подразумевает под собой разработку более эффективных алгоритмов, оптимизированных для её использования.
Одним из наиболее перспективных и широко используемым направлением в анализе схем является представление схемы в виде графа. И тогда анализ исходной схемы сводится к исследованию графа.
Историю графов принято исчислять с 1736 г., когда Эйлер исследовал «задачу о кенигсбергских мостах»: построить в графе циклический путь, проходящий по одному разу через каждое ребро. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков. В середине 19-го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа (интересно, что несмотря на внешнюю похожесть задача Эйлера имеет простое эффективное решение, а задача Гамильтона в общем случае эффективно не решается). К тому же времени относится использование графов для анализа электрических цепей (Кирхгоф) и химических формул (Кэли). Развитие современной теории графов относится к 30-м годам 20-го столетия. Они нашли многочисленные применения в электротехнике, электронике, биологии, экономике, программировании и других областях.
В большинстве практических задач (сетях связи, экономике, электрических цепях и т.д.) большой интерес представляет минимальное множество сечений контуров обратной связи (впервые задача – дать эффективный алгоритм для отыскания минимального множества контуров обратной связи – была предложена доктором Д. П. Ранианом из лаборатории Белла). В 1995-1996 годах Леонидом Анатолиевичем Наумовым был разработан алгоритм решения данной задачи.
1.3. Неформальная
|
На уровень вверх
Купить