Гамильтоновы графы и сложность отыскания гамильтоновых циклов
Понятие и основные определения гамильтоновых графов, теоремы их достаточности и особенности методов нахождения циклов. Сущность метода перебора Робертса и Флореса и его улучшение. Задачи отыскания гамильтоновых циклов в графах, создание программы.
Подобные документы
Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.
курсовая работа, добавлен 18.02.2013Основные понятия и определения алгоритмов на графах. Связные графы без циклов, свободное дерево или дерево без корня. Ориентированные графы (орграфы), их использование для представления отношений между объектами. Матрицы смежности и инциденций.
презентация, добавлен 13.09.2013Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.
курсовая работа, добавлен 04.02.2011История возникновения, основные понятия и теоремы теории графов. Способы предоставления графов в компьютере. Матрица смежности, инциденций, списки смежности и массив дуг. Программа определения кратчайшего пути в графах. Язык программирования Delphi.
курсовая работа, добавлен 24.11.2010Табличный вывод значений суммы ряда и номера последнего элемента суммы в зависимости от значений величин входных параметров с применением операторов ветвления и циклов. Блок-схема алгоритма решения. Время работы программы для расчета одного значения.
контрольная работа, добавлен 14.05.2013Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C++. Доказательство "правильности" работы алгоритма с помощью математической индукции.
курсовая работа, добавлен 26.07.2013История и задачи разработки языка программирования Pascal. Понятие и характерные особенности типизированного файла, основные операции с файловыми переменными. Блок-схема алгоритма и исходный текст программы для обработки сведений об учениках школы.
контрольная работа, добавлен 31.07.2013Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа, добавлен 27.12.2008Создание приложения и освоение начала технологии графического программирования. Использование CASE-структур в создаваемых приложениях и применение циклов типа For-Do. Создание программы, которая будет подсчитывать время выполнения определенного цикла.
курсовая работа, добавлен 24.06.2013Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа, добавлен 20.07.2012Основные типы циклов программирования. Методы применения специальных функций break, continue и цикла while. Обработка массивов информации. Условия применения циклических алгоритмов на языке программирования С++. Инициализация одномерного массива.
курсовая работа, добавлен 06.01.2014Предназначение цикла for - оформление циклов (набора действий) с заданным количеством повторений. Пример программы, выводящей на экран все целые числа от 0 до 99. Решение задачи с помощью двух алгоритмов, используя известные функции ввода-вывода.
лабораторная работа, добавлен 15.07.2009Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат, добавлен 06.03.2010Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа, добавлен 14.07.2012Понятие и назначение условных операторов, их функциональные особенности и характерные свойства. Разновидности и отличия циклов. Прерывание фрагмента программы с циклом с использованием оператора break. Компоненты для отображения и редактирования текста.
контрольная работа, добавлен 02.05.2012Решение задачи вычисления и вывода значений функций. Разветвляющиеся и циклические вычислительные процессы. Задача табулирования. Блок схема и код программы. Вычисления по рекуррентным формулам. Программирование вложенных циклов. Сумма элементов матрицы.
контрольная работа, добавлен 10.12.2013Исследование систем методами случайного поиска. Изучение сущности метода половинного деления. Сравнительный анализ прямого перебора и половинного деления. Ручной счет. Шаги исследования. Описание окна работающей программы. Блок-схема и код программы.
курсовая работа, добавлен 06.05.2014Решение задач, прямо связанных с применением циклов и массивов. Условия применения различных видов циклической структуры. Операторы цикла с предусловием while, постусловием do-while и for. Особенности работы с одномерными и двумерными массивами.
курсовая работа, добавлен 31.08.2019Написание программы, которая вводит исходные данные, выполняет расчет и выводит на экран. Использование вспомогательных переменных и счетчиков циклов в программе. Расчет сумм заработков по каждому виду одежды за день, количества изготовленных деталей.
курсовая работа, добавлен 17.01.2015Рабочая среда Visual Basic (VB) и ее основные компоненты. Ввод и вывод данных в VB. Объявление переменных и констант в программе. Создание и работа с процедурами и функциями, их виды. Организация ветвления в VB. Использование циклов в программировании.
практическая работа, добавлен 26.10.2013Стандартные схемы программ в линейной и графовой формах. Инварианты и ограничения циклов. Анализ сетей Петри на основе дерева достижимости. Доказательство полной правильности программы. Суммы элементов диагоналей, параллельных главной диагонали матрицы.
курсовая работа, добавлен 30.05.2012Тестирование модуля отыскания корня уравнения методом половинного деления. Схема алгоритма тестирующей программы. Численное интегрирование по методу Симпсона с оценкой погрешности по правилу Рунге. Проверка условий сходимости методов с помощью MathCAD.
курсовая работа, добавлен 04.02.2011Исследование асимптотической временной сложности решения шахматной задачи; разработка наиболее эффективных алгоритмов и структуры данных; аналитическая и экспериментальная оценка методов сокращения перебора в комбинаторных задачах; программная реализация.
курсовая работа, добавлен 25.06.2013Понятие вложенных циклов, одномерных и двумерных массивов в программировании. Матрицы и основные действия с ними. Иерархические записи, понятие дерева. Операции с двоичными деревьями, рекурсия, включение и удаление узла. Алгоритм поиска по дереву.
отчет по практике, добавлен 27.12.2011Особенности вычисления по формулам в Microsoft Visual Basic с использованием функции If. Применение циклов и разветвлений. Визуальные объекты, составление алгоритмов задачи, блок-схемы и программного кода. Введение переменных, определение типа данных.
лабораторная работа, добавлен 23.05.2014