Пример готовой курсовой работы по предмету: Высшая математика
Содержание
Содержание
ВВЕДЕНИЕ 3
1. ОСНОВОПОЛАГАЮЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 4
2. ЦИКЛОМАТИЧЕСКОГО ЧИСЛА ГРАФА И ЕГО ОСНОВНЫЕ СВОЙСТВА 7
3. ОПРЕДЕЛЕНИЕ ГРУПП ОДНОМЕРНЫХ И НУЛЬМЕРНЫХ ЦЕПЕЙ ГРАФА 10
РЕШЕНИЕ ЗАДАЧ 15
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 18
Выдержка из текста
Введение
Работа выполнена в соответствии с темой
4. Циклы в графах.
С циклами и цепями связаны наиболее известные задачи из истории графов, одна из них задача о гамильтоновых цепях и циклах. Требуется найти, при каких условиях конечный связный граф содержит цепь или цикл, проходящий через все вершины. Если такая цепь или цикл существует и являются простыми, то они называются соответственно гамильтоновыми цепями или гамильтоновыми циклами.
Если граф обладает гамильтоновым циклом S, то, очевидно, он обладает и гамильтоновой цепью. Обратное, вообще говоря, неверно.
Несмотря, на наличие частных результатов, в общем случае задача определения гамильтоновых циклов и цепей недостаточно изучена. Даже нет хороших методов доказательства существования таких цепей и циклов.
Интересной задачей, связанной с поиском кратчайшего гамильтонова пути, является задача коммивояжера. Коммивояжер должен посетить по одному разу каждый из n городов (каждый город связан с другим дорогой) и вернуться в исходный город. При этом он должен выбрать кратчайший маршрут. Очевидно, что определения кратчайшего маршрута с помощью просмотра всех гамильтоновых циклов приводит к перебору гамильтоновых циклов (n-1)!/2 возможных циклов, а это величина астрономическая при больших n.
Список использованной литературы
Список использованных источников
1. Уилсон Р. Введение в теорию графов — М . Мир, I977
2. Белов В.В. Воробьев Е. М . Шаталов В. Е. Теория графов — М ВШ. 1976.
3. Березина Л. Ю. Графы и их применения. Пособие для учителей. — М.. 1979.
