- •Темы контрольных работ по дискретная математика
- •1. Эйлеровы графы .
- •2. Гамильтоновы графы.
- •1 Уилсон р. Дж. Введение в теорию графов. – м.: 1977.
- •3. Связность графа.
- •4. Циклы в графах.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •5. Плоские графы.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •6. Деревья.
- •1) Изучить такие основополагающие понятия теории графов, как граф, маршрут и цикл (/1/, с. 9-43; /2/, с. 5-22).
- •7. Свойства эйлеровых графов.
- •8. Свойства гамильтоновых графов.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •9. Ориентированные графы.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •10. Паросочетания.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •11. Теория трансверсалей.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •12. Потоки в сетях.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •13. Производящие функции в теории графов.
- •14. Теорема Пойа и перечисление графов.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •14. Графы на двумерных поверхностях.
- •1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- •2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- •15. Конечные группы и их графы.
- •2 Оре о. Теория графов. – м.: Наука, 1968.
- •16. Теорема Рамсея и ее приложения.
- •2 Оре о. Теория графов. – м.: Наука, 1968.
- •17. Полугруппы преобразований.
- •18. Копредставления полугрупп.
- •19. Логика на словах.
- •20. Алгебры отношений и полугруппы преобразований.
- •21. Рациональные языки.
- •Тема 71. Соответствие Эйленберга
- •22. Отношения Грина.
- •23. Декомпозиция конечных моноидов.
- •24. Рациональные и алгебраические языки над полукольцами.
- •25. Элементы теории конечных автоматов.
- •1 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- •26. Минимизация чистых автоматов.
- •27. Конструкции чистых автоматов.
- •28. Цифровое шифрование.
- •29. Последовательности над конечным полем.
- •30. Решетки.
8. Свойства гамильтоновых графов.
Одной из первых задач, приведших к возникновению теории графов, является известная «задача о коммивояжере». Решение этой задачи естественно привело к определению важного класса графов, называемых гамильтоновыми. Цель контрольной работы - изучить основные свойства гамильтоновых графов и рассмотреть практические задачи, сводящиеся к задаче о коммивояжере. Рекомендуется следующий план работы:
1) Изучить такие основополагающие понятия теории графов, как граф, маршрут и цепь, контур и цикл (/1/, с. 9-43; /2/, с. 14-18).
2) Рассмотреть понятие гамильтонова цикла, ввести определение гамильтонова графа и доказать теорему Дирака о таких графах (/1/, с. 48-51; /2/, с. 168-173).
3) Разобрать задачу о коммивояжере и примеры конкретных практических задач, приводящих к этой задаче (/2/, с. 179-182).
4) Изучить метод ветвей и границ, разобрать точный алгоритм решения задачи о коммивояжере на стр. 182-197 в /2/.
Литература, рекомендуемая для изучения темы
1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
1976.
3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
1979.
9. Ориентированные графы.
Понятие ориентированного графа (орграфа) играет важную роль в
теории графов и ее разнообразных приложениях. В контрольной работе необходимо изучить основные свойства орграфов и проанализировать известную классификацию таких графов. Рекомендуется следующий план
работы:
1) Изучить такие основополагающие понятия теории графов, как ориентированный граф, ориентированный маршрут, орцепь, орцикл и сильная связность, доказать теорему Роббинса об ориентируемом связном графе (/1/, с. 127-130).
2) Рассмотреть понятие эйлерова орграфа и доказать основную теорему о таких графах (/1/, с. 131-133).
3) Рассмотреть понятия гамильтонова орграфа и проанализировать взаимосвязь полугамильтоновых оргафов с турнирами (/1/, с. 133-136). 4 Разобрать приложение орграфов к теории цепей Маркова (/1/, с. 138-142).
Литература, рекомендуемая для изучения темы
1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
1976.
3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
1979.
10. Паросочетания.
Многие комбинаторные приложения теории графов естественно приводят к понятиям паросочетания и трансверсали. Цель контрольной работы -
изучить постановки важных комбинаторных задач и основные методы их решения с помощью теории графов. Рекомендуется следующий план работы:
1) Изучить такие основополагающие понятия теории графов, как граф, двудольный граф и паросочетание (/1/, с. 9-43, 144-146; /3/, с. 154-159).
2) Рассмотреть известную задачу о свадьбах и доказать теорему Холла (/1/, с. 144-147; /2/, с. 168-173).
3) Изучить теорию трансверсалей и ее приложение к задачам о паросочетаниях (/1/, с. 148-150). 4 Разобрать приложения теоремы Холла к латинским квадратам, реберным раскраскам графов и (0,1)-матрицам (/1/, с. 151-156).
Литература, рекомендуемая для изучения темы
1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
1976.
3 Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
1979.
11. Теория трансверсалей.
Известная задача о системе различных представителей (называемая
также трансверсалью) имеет многочисленные приложения в теории множеств, комбинаторике, теории графов и других разделах дискретной математики. Цель контрольной работы - изучить разнообразные эквивалентные постановки задачи о системе различных представителей и методы ее решения. Рекомендуется следующий план работы:
1) Изучить такие основополагающие понятия теории графов, как граф и двудольный граф, паросочетание и трансверсаль (/1/, с. 9-43, 144-148; /2/, с.
128-134; /3/, с. 154-155, 163-169).
2) Разобрать доказательство теоремы о системе различных представителей и эквивалентных ей известных теорем (/2/, с. 128-144).
3) Рассмотреть прикладные задачи на паросочетания (/2/, с. 150-166).
Литература, рекомендуемая для изучения темы