Тема: Решение практических задач. Учебная работа № 430280

Учебная работа № 430280. Тема: Решение практических задач

Выдержка из похожей работы

…….

Графы. решение практических задач с использованием графов (С++)

…..ие

2.
История возникновения
теории графов

3.
Основные понятия теории
графов

4.
Основные теоремы теории
графов

5.
Способы представления
графов в компьютере

6.
Обзор задач теории графов

7.
Заключение

8.
Список литературы

9.
Приложение А

10. Приложение Б

Введение

В последнее время исследования в областях,
традиционно относящихся к дискретной математике, занимают все более заметное
место. Наряду с такими классическими разделами математики, как математический
анализ, дифференциальные уравнения, в учебных планах специальности
“Прикладная математика” и многих других специальностей появились
разделы по математической логике, алгебре, комбинаторике и теории графов.
Причины этого нетрудно понять, просто обозначив круг задач, решаемых на базе
этого математического аппарата.

История возникновения теории графов.

Родоначальником теории графов принято считать
математика Леонарда Эйлера (1707-1783). Однако теория графов многократно
переоткрывалась разными авторами при решении различных прикладных задач.

1.  
Задача о Кенигсбергских
мостах. На рис. 1 представлен
схематический план центральной части города Кенигсберг (ныне Калининград),
включающий два берега реки Перголя, два острова в ней и семь соединяющих
мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по
каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена
(показано, что решение не существует) Эйлером в 1736 году.

рис. 1

2.  
Задача о трех домах и
трех колодцах. Имеется три
дома и три колодца, каким-то образом расположенные на плоскости. Провести от
каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались
(рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским
в 1930 году.

рис. 2

3.  
Задача о четырех
красках. Разбиение на
плоскости на непересекающиеся области называется картой. Области на карте
называются соседними, если они имеют общую границу. Задача состоит в
раскрашивании карты таким образом, чтобы никакие две соседние области не были
закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза,
что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен
опубликовали решение задачи о четырех красках, которое базировалось на переборе
вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось
прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть
опубликованного решения состоит в том, чтобы перебрать большое, но конечное
число (около 2000) типов потенциальных контрпримеров к теореме о четырех
красках и показать, что ни один случай контрпримером не является. Этот перебор
был выполнен программой примерно за тысячу часов работы суперкомпьютера.
Проверить «вручную» полученное решение невозможно – объем перебора выходит
далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно
ли считать такое «программное доказательство» действительным доказательством?
Ведь в программе могут быть ошибки… Методы формального доказательства
правильности программ не применимы к программам такой сложности, как
обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном
случае вообще невозможно. Таким обра…