Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
На рис.44 указано одно из возможных решений.
5641583550396033
4744554059345138
4257464936533261
4548435431623752
20 5306322111613
296421 417142510
619 227 8231215
128 718 326 924
Рис. 44
Задача о званом обеде. Обед накрыт на круглом столе. Среди приглашенных некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны каждого из присутствующих сидели его друзья?
Задача о коммивояжере. Коммивояжер должен объездить все n городов. Для того, чтобы сократить свои расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.
Для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату. По своей математической постановке игра Гамильтона близка к задаче о порядке переналадки станков, задаче о подводке электроэнергии к рабочим местам и др.
Рассмотрим решение задачи о коммивояжере на примере графа G (рис.45).
Имеем пять пунктов V = {1, 2, 3, 4, 5}. Стоимость доставки информации из пункта I в пункт j показана числами над ребрами графа. Требуется, используя компьютерную сеть, моделируемую данным графом, обеспечить перекличку пунктов, начиная с пункта 1. Для решения поставленной задачи построим гамильтонов цикл минимальной стоимости передачи информации, либо несколько таких циклов в случае их одинаковой стоимости.
Задачу будем решать в два этапа. Вначале построим все гамильтоновы циклы из пункта 1. Для этого применим алгоритм с возвратами. Затем на множестве полученных циклов выберем циклы минимальной длины.
Построение цепей графа G применением алгоритма с возвратами приведено на рис. справа, где цепи, соответствующие гамильтоновым циклам, выделены жирными линиями.
Всего имеем четыре гамильтоновых цикла:
а) {1, 2, 3, 5, 4, 1},
b) {1, 2, 5, 3, 4, 1},
c) {1, 4, 3, 5, 2, 1}
d) {1, 4, 5, 3, 2, 1}
Стоимости передачи информации каждым из этих циклов вычисляются ниже:
а) 9 + 10 + 2 + 2 + 6 = 29,
b) 9 + 8 + 2 + 5 + 6 = 30,
с) 6 + 5 + 2 + 8 + 9 = 30,
d) 6 + 2 + 2 + 10 + 9 = 29.
Решению поставленной задачи отвечают гамильтоновы циклы а) и d).
При увеличении размерности задачи всего лишь в несколько раз снова возникают проблемы реального времени. Это способствует развитию новых идей построения гамильтоновых циклов.
Глава II. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ
1. Роль факультативных занятий
Для правильного понимания того, как наладить наконец математические факультативы, необходимо вспомнить об их возникновении.
Еще на рубеже XIX и ХХ вв. некоторые педагоги поняли, что преподавание в общеобразовательной школе какого-либо предмета по обязательной единой общегосударственной программе становится существенно более успешным, если его дополнить циклом необязательных для учащихся, предназначенных только для желающих, внепрограммных групповых занятий.
Такие занятия должны были прежде всего учитывать местные условия, а именно: реальные и потенциальные запросы и интересы конкретного количества учащихся данного класса, реальные возможности конкретного учителя вызвать и развить интерес учащихся к важным аспектам данного предмета, не охваченным обязательной программой.
Так возникла идея факультативных занятий в школе. Из толкового словаря Д.И.Ушакова: факультативный - необязательный, предоставленный собственному выбору.
Влиятельность, воспитательность общеобразовательной школы, - писал в 1901 г. видный русский педагог Петр Федорович Каптерев, - ее значение в народной жизни и развитии культуры будут очень много зависеть от того, как будут поставлены факультативные занятия… на единообразной обязательности далеко не уедешь.
Учителя-энтузиасты дореволюционной и советской школы стали создавать для учащихся факультативные предметные семинары, они получили название, заимствованное из общественной жизни: кружки. Школьные кружки были созданы также при университетах и других вузах.
Опыт многих педагогов показал, что именно в предметном кружке возникает особенно благоприятная атмосфера для воспитания у школьников увлеченности предметом, энтузиазма, инициативы.
Важной вехой в истории советской школы был 1966 г., когда постановление ЦК КПСС и Совета Министров СССР О мерах дальнейшего улучшения работы средней общеобразовательной школы рекомендовало всем школам проведение в VII-Х классах факультативных занятий для углубления знаний учащихся, для развития их интересов, способностей. Впервые все работники просвещения осознали, что такие занятия столь же важны, как и уроки по обязательной программе.
По существу в то время, в условиях единства средней общеобразовательной школы, единства системы среднего образования, факультативные занятия являлись единственной формой дифференцированного обучения.
В настоящее время факультативные занятия проводятся в школе наряду с другими формами дифференцированного обучения (уровневой и профильной дифференциацией). Часы на их проведение входят в варьируемую часть базисного учебного плана, в его школьный компонент.
Факультативные занятия организуются на добровольной основе, учащиеся выбирают курсы, которые они будут изучать, исходя из своих интересов и способностей к тому или иному предмету или виду деятельности.
Значение факультативных занятий состоит в том, что они позволяют:
развивать склонности и способности учащихся, давая им соответствующую интеллектуальную нагрузку;
удовлетворять инте?/p>