Сборник тем курсовых работ по математике (алгебра, математическая логика, дискретная математика). Молчанов В.А - 33 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

привело к определению важного класса графов, называемых гамильтоновыми.
Цель курсовой работы - изучить основные свойства гамильтоновых графов и
рассмотреть практические задачи, сводящиеся к задаче о коммивояжере.
Рекомендуется следующий план работы.
1 Изучить такие основополагающие понятия теории графов, как граф,
маршрут и цепь, контур и цикл (/1/, с. 9-43; /2/, с. 14-18).
2 Рассмотреть понятие гамильтонова цикла, ввести определение
гамильтонова графа и доказать теорему Дирака о таких графах (/1/, с. 48-51; /2/,
с. 168-173).
3 Разобрать задачу о коммивояжере и примеры конкретных
практических задач, приводящих к этой задаче (/2/, с. 179-182).
4 Изучить метод ветвей и границ, разобрать точный алгоритм решения
задачи о коммивояжере на стр. 182-197 в /2/.
Решить задачи 7a, 7b, 7d, 7e, 7i из /1/.
Литература, рекомендуемая для изучения темы
1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
3 Березина Л.Ю. Графы и их применения: Пособие для учителей. – М.,
1979.
Тема 55. Раскраски графов
Одной из первых задач, приведших к возникновению теории графов,
является известная «гипотеза четырех красках». Исследование этой проблемы
послужило толчком к многочисленным и чрезвычайно разнообразным
исследованиям, в результате которых возник важный раздел теории графов.
Цель курсовой работы - изучить основные понятия теории раскрашивания
плоских графов и проанализировать известные результаты о гипотезе четырех
красок. Рекомендуется следующий план работы.
1 Изучить такие основополагающие понятия теории графов, как граф,
маршрут и контур, раскраска и плоский граф (/1/, с. 9-43; /2/, с. 14-18).
2 Рассмотреть понятия хроматического числа и хроматического
многочлена графа, графа, доказать теоремы о свойствах этих понятий (/1/, с.
101-103, 120-124; /2/, с. 168-173).
3 Проанализировать известные результаты о гипотезе четырех красок
(/1/, с. 110-119; /2/, с. 95-99; /3/, с. 32-40).
Решить задачи 17a, 17b, 17d, 21a, 21b, 21c из /1/.
Литература, рекомендуемая для изучения темы
1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. 
привело к определению важного класса графов, называемых гамильтоновыми.
Цель курсовой работы - изучить основные свойства гамильтоновых графов и
рассмотреть практические задачи, сводящиеся к задаче о коммивояжере.
Рекомендуется следующий план работы.
        1 Изучить такие основополагающие понятия теории графов, как граф,
маршрут и цепь, контур и цикл (/1/, с. 9-43; /2/, с. 14-18).
        2 Рассмотреть понятие гамильтонова цикла, ввести определение
гамильтонова графа и доказать теорему Дирака о таких графах (/1/, с. 48-51; /2/,
с. 168-173).
        3 Разобрать задачу о коммивояжере и примеры конкретных
практических задач, приводящих к этой задаче (/2/, с. 179-182).
        4 Изучить метод ветвей и границ, разобрать точный алгоритм решения
задачи о коммивояжере на стр. 182-197 в /2/.

        Решить задачи 7a, 7b, 7d, 7e, 7i из /1/.

        Литература, рекомендуемая для изучения темы
        1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
        2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
        3 Березина Л.Ю. Графы и их применения: Пособие для учителей. – М.,
1979.

        Тема 55. Раскраски графов

         Одной из первых задач, приведших к возникновению теории графов,
является известная «гипотеза четырех красках». Исследование этой проблемы
послужило толчком к многочисленным и чрезвычайно разнообразным
исследованиям, в результате которых возник важный раздел теории графов.
Цель курсовой работы - изучить основные понятия теории раскрашивания
плоских графов и проанализировать известные результаты о гипотезе четырех
красок. Рекомендуется следующий план работы.
         1 Изучить такие основополагающие понятия теории графов, как граф,
маршрут и контур, раскраска и плоский граф (/1/, с. 9-43; /2/, с. 14-18).
         2 Рассмотреть понятия хроматического числа и хроматического
многочлена графа, графа, доказать теоремы о свойствах этих понятий (/1/, с.
101-103, 120-124; /2/, с. 168-173).
         3 Проанализировать известные результаты о гипотезе четырех красок
(/1/, с. 110-119; /2/, с. 95-99; /3/, с. 32-40).

        Решить задачи 17a, 17b, 17d, 21a, 21b, 21c из /1/.

        Литература, рекомендуемая для изучения темы
        1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

Страницы