Алгоритмы на графах. Нахождение кратчайшего пути
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
Подобные документы
Изучение конкретного раздела дискретной математики. Решение 5-ти задач по изученной теме с методическим описанием. Методика составления и реализация в виде программы алгоритма по изученной теме. Порядок разработки программного интерфейса и руководства.
курсовая работа, добавлен 27.04.2011Система, свойства и модели комплексных чисел. Категоричность и непротиворечивость аксиоматической теории комплексных чисел. Корень четной степени из отрицательного числа. Матрицы второго порядка, действительные числа. Операции сложения и умножения матриц.
курсовая работа, добавлен 15.06.2011Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
курсовая работа, добавлен 27.03.2011История слова "алгоритм", понятие, свойства, виды. Алгоритм Евклида, решето Эратосфена; математические алгоритмы при действии с числами и решении уравнений. Требования к алгоритмам: формализация входных данных, память, дискретность, детерминированность.
реферат, добавлен 14.05.2015Изучение вопросов применения теории множеств, их отношений и свойств и теории графов, а также математических методов конечно-разностных аппроксимаций для описания конструкций РЭА (радиоэлектронной аппаратуры) и моделирования протекающих в них процессов.
реферат, добавлен 26.09.2010Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.
курсовая работа, добавлен 12.07.2012- 57. Графы
Сущность теории графов и ее применение на современном этапе в различных отраслях науки и техники, особенно в экономике и социологии. Понятие дерева, его разновидности, характерные свойства. Операции, совершаемые над графами и возможности их реализации.
контрольная работа, добавлен 08.12.2009 Разработка и анализ топологической модели электронной схемы для полного диапазона частот. Определение передаточной схемной функции методом эквивалентных схем в матричной форме, а также методом сигнальных графов, используя сигнальный граф Мэзона.
контрольная работа, добавлен 11.04.2016- 59. Матрицы графов
Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат, добавлен 23.11.2008 Первое доказательство существования иррациональных чисел. Развитие теории пропорций Евдоксом Книдским. Теоремы, корень из 2 - иррациональное число. Трансцендентное число: сущность понятия, свойства, примеры, история. История уточнения числа пи.
контрольная работа, добавлен 27.11.2011Нахождение корней уравнений (Equation Section 1) методом: Ньютона, Риддера, Брента, Лобачевского и Лагерра. Вычисление корней многочленов по схеме Горнера. Функции произвольного вида (при использовании пакета Mathcad). Нахождение корней полиномов.
контрольная работа, добавлен 14.08.2010Основные свойства функций, для которых существуют пределы. Понятие бесконечно малых величин и их суммы. Предел алгебраической суммы, разности и произведения конечного числа функций. Предел частного двух функций. Нахождение предела сложной функции.
презентация, добавлен 21.09.2013Понятие и внутренняя структура графа, его применение и матричное представление (матрица инциденций, разрезов, цикломатическая, Кирхгофа). Специальные свойства и признаки графов, решение оптимизационных задач. Венгерский алгоритм, матричная интерпретация.
курсовая работа, добавлен 24.12.2013Сущность и предмет теории вероятностей, отражающей закономерности, присущие случайным явлениям массового характера. Изучение ею закономерностей массовых однородных случайных явлений. Описание наиболее популярных в теории вероятностей экспериментов.
презентация, добавлен 17.08.2015Ознакомление с теоремами теории аналитических функций. Определение и основные свойства индекса функции. Постановка и методы решения однородной и неоднородной задач Римана для односвязной и многосвязной областей. Принципы нахождения функции сдвига.
курсовая работа, добавлен 20.12.2011Основные понятия теории обыкновенных дифференциальных уравнений. Признак уравнения в полных дифференциалах, построение общего интеграла. Простейшие случаи нахождения интегрирующего множителя. Случай множителя, зависящего только от Х и только от Y.
курсовая работа, добавлен 24.12.2014Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа, добавлен 15.12.2008Применение интервальных графов. Алгоритмы распознавания интервальных графов: поиск в ширину, поиск в ширину с дополнительной сортировкой, лексикографический поиск в ширину, алгоритм "трех махов". Программа задания единичного интервального графа.
курсовая работа, добавлен 10.02.2017Расширенный алгоритм Евклида, его использование для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления. Математическая проблема календаря. Евклидовы кольца - аналоги чисел Фибоначчи в кольце многочленов, их свойства.
реферат, добавлен 25.09.2009Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа, добавлен 07.06.2011Некоторые математические вопросы теории обслуживания сложных систем. Организация обслуживания при ограниченной информации о надёжности системы. Алгоритмы безотказной работы системы и нахождение времени плановой предупредительной профилактики систем.
реферат, добавлен 19.06.2008Задачи нахождения собственных значений и соответствующих им собственных векторов. Математическое обоснование метода итераций. Алгоритм метода Леверрье-Фаддеева, численное решение оценки собственных значений матриц. Листинг программы на языке "Pascal".
курсовая работа, добавлен 05.11.2014- 73. Теория графов
Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа, добавлен 14.05.2012 Задача о кенигсбергских мостах, четырех красках, выходе из лабиринта. Матрица инцидентности для неориентированного и (ориентированного) графа. Степень вершины графа. Ориентированное дерево. Линейные диаграммы или графики Ганта. Метод критического пути.
презентация, добавлен 23.06.2013Общие сведения о фигурах, вычерчиваемых одним росчерком. Теория графов Эйлера, задача о мостах. Правила построения фигуры без отрыва карандаша от бумаги. Задача об эйлеровом пути, применение графов в жизни, быту, различных отраслях науки и техники.
реферат, добавлен 16.12.2011