Выпускная квалификационная работа теория графов
 Скачать 0.56 Mb.
|
 Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку С. Так как существенны только переходы через мосты, план города можно свести к изображению графа, в котором ребра соответствуют мостам, а вершины - различным разделенным частям города (рис.40). Очевидно, не существует циклических обходов, проходящих по всем ребрам по одному разу. Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть универсальной (рис.41). Рис. 41 Теорема: Если граф обладает эйлеровым циклом, то он связный и всего его вершины четные. Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз Эйлеров путь приведет конец карандаша в вершину, столько и выведет, причем уже по другому ребру. Следовательно, степень каждой вершины графа должно состоять из двух одинаковых слагаемых: одно - результат подсчета входов в вершину, другое - выходов. Верно и обратное утверждение. Задачи на отыскание путей через лабиринты, близкие к задачам на Эйлеровы графы, находят и здесь свое применение. Уже начиная с мифа о том, как Тезей, убив Минотавра, нашел путь по коридорам лабиринта в Кноссе, задача о поиске прохода через лабиринт стала популярной головоломкой. Во многих средневековых храмах на мозаичных полах изображены лабиринты. Возможно, метод нахождения пути был бы полезен для группы, заблудившейся в пещере. Однако. кроме этого, задачи о лабиринте представляют теперь интерес главным образом для развлечения детей, а также для психологов, когда они выпускают своих подопытных крыс в запутанные лабиринты. Говоря коротко, лабиринт состоит из коридоров и их перекрестков. Таким образом, он может быть представлен графом, в котором ребра соответствуют коридорам, а вершины перекресткам. На рис.42 изображен план известного лабиринта в саду в Хемптон Корт, а на рис.43 - соответствующий граф. В терминах графов задача о лабиринте может быть сформулирована следующим образом. Определить метод, позволяющий найти маршрут в графе, который начинается в заданной вершине V0 и наверняка приводит в другую заданную вершину V1 (выход). Очевидно, чтобы не было бесконечного блуждания по циклическим маршрутам, необходимо иметь возможность запоминать уже пройденные вершины и ребра; поэтому нужно предполагать, что заблудившийся располагает средствами помечать каким-то способом проходимые им ребра и вершины. В 1857 году ирландский математик Гамильтон предложил игру, названную «Путешествием по додекаэдру». Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра, при условии, что ни в одну из вершин нельзя заходить более одного раза. (Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников) Гамильтоновым циклом (путем) в графе называется цикл (путь), проходящий через каждую вершину графа в точности по одному разу. Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом. Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все ребра, и притом по одному разу каждое, вторые - все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла на графе достаточно выяснить, все ли его вершины четны. Критерий же существования гамильтонова цикла на произвольном графе еще не найден. Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близки известные задачи. Задача о шахматном коне. Можно ли, начиная с произвольного поля на шахматной доске, ходить конем в такой последовательности, чтобы пройти через все поля и вернуться в исходное? На рис.44 указано одно из возможных решений. 56 41 58 35 50 39 60 33 47 44 55 40 59 34 51 38 42 57 46 49 36 53 32 61 45 48 43 54 31 62 37 52 20 5 30 63 22 11 16 13 29 64 21 4 17 14 25 10 6 19 2 27 8 23 12 15 1 28 7 18 3 26 9 24 Рис. 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-Х классах факультативных занятий «для углубления знаний учащихся, для развития их интересов, способностей». Впервые все работники просвещения осознали, что такие занятия столь же важны, как и уроки по обязательной программе. По существу в то время, в условиях единства средней общеобразовательной школы, единства системы среднего образования, факультативные занятия являлись единственной формой дифференцированного обучения. В настоящее время факультативные занятия проводятся в школе наряду с другими формами дифференцированного обучения (уровневой и профильной дифференциацией). Часы на их проведение входят в варьируемую часть базисного учебного плана, в его школьный компонент. Факультативные занятия организуются на добровольной основе, учащиеся выбирают курсы, которые они будут изучать, исходя из своих интересов и способностей к тому или иному предмету или виду деятельности. Значение факультативных занятий состоит в том, что они позволяют: развивать склонности и способности учащихся, давая им соответствующую интеллектуальную нагрузку; удовлетворять интересы учащихся; повышать качество подготовки учащихся к продолжению образования; развивать творческие способности учащихся, их самостоятельность; знакомить учащихся с современными достижениями науки и техники; формировать у учащихся общеучебные умения: готовить доклады и представлять их, выполнять рефераты, работать в группе, умение работать с информацией; способствовать профессиональной ориентации учащихся. На сегодняшний день разработана система факультативных курсов, в которой условно можно выделить три группы: . Курсы повышенного уровня, тесно связанные с основным курсом математики. Их основная цель - углубить знания, полученные учащимися на уроках. Данные курсы сочетают теоретическую и экспериментальную подготовку учащихся. . Курсы прикладной математики, цель которых - познакомить учащихся с важнейшими путями и методами использования достижений математической науки на практике и развивать их интерес к развитию современной математической науке. . Спецкурсы, на которых более глубоко изучаются некоторые разделы математики, играющие важную роль в формировании у учащихся научного мировоззрения. Цель этих курсов - компенсировать отсутствие некоторых важных тем в программе основного курса. Некоторые факультативные курсы изучаются в течение одного года, другие - в течение двух-трех лет. Однако в последнем случае программы каждого года автономны и ученик может начать заниматься данным курсом в любом году. Минимальная наполняемость группы, с которой могут проводиться факультативные занятия, - 10 человек. В сельских малокомплектных школах разрешено проводить факультативные занятия при меньшем составе группы, в этих школах в группу могут быть собраны учащиеся из разных классов. Факультативные занятия проводятся по специальным программам. Программы ряда факультативных курсов утверждены Министерством образования и содержатся в сборниках программ. Помимо этого, учителю дано право работать по собственной программе, которая должна быть утверждена администрацией школы. На факультативных занятиях используются различные формы организации обучения, среди них могут быть как теоретические занятия: лекции, семинары, конференции, так и практические: решение задач, фронтальные занятия, практикум, экскурсии. Опыт показывает, что факультативные занятия достигают цели при сочетании различных форм организации обучения. При этом лекции целесообразны в IX-XI классах, причем доля лекционных часов в IX классе не должна быть большой. В VII-VIII классах лекционные занятия неприемлемы в силу возрастных особенностей учащихся. Рассмотрим формы обучения учащихся на факультативных занятиях. На лекциях могут рассматриваться практические применения теорем и математических законов, они могут посвящаться обобщению и систематизации знаний. Желательно, чтобы на лекции использовалось проблемное изложение материала, способствующее активизации познавательной деятельности учащихся. В начале чтения лекции учащимся дается ее план, который записывается на доске, создается мотивация, ставится основная познавательная задача. У учащихся следует формировать умения конспектировать лекции. Для этого необходимо продумать заранее, какие записи должны остаться у учащихся в тетради, и учитывать это при чтении лекции, диктуя или повторяя несколько раз соответствующий материал, делая паузы. Лекция сопровождается иллюстрациями, записями на доске, демонстрационным экспериментом. Школьная лекция отличается тем, что в нее вводятся некоторые элементы беседы, элементы практической работы учащихся, что связано с возрастными особенностями учащихся, в силу которых они не могут длительное время слушать объяснение учителя, им необходима смена видов деятельности. Доля таких элементов обычно уменьшается в соответствии с возрастом учащихся. Семинарские занятия посвящаются обсуждению теоретических вопросов, их более глубокой проработке. Возможны такие, например, темы семинарских занятий: «Плоские графы», «Графы с цветными ребрами», «Графы в играх и головоломках», «Графы и их роль в школьных учебниках» и другие. Учащимся заранее дается план семинарского занятия, в который входят вопросы, обязательные для подготовки всеми учащимися, и вопросы, которые учащиеся готовят в виде индивидуальных заданий. По каждому вопросу, обсуждаемому на семинаре, указывается обязательная и дополнительная литература. На семинаре учащиеся выступают с небольшими сообщениями, вокруг которых разворачивается дискуссия. Готовясь к семинару, учащиеся учатся работать с литературой, планировать свое выступление, лаконично выражать свои мысли. Работая на семинарском занятии, учащиеся приобретают умение выступать с сообщением, отвечать на вопросы, участвовать в дискуссии, критично, но доброжелательно относиться к выступлениям своих товарищей и самокритично к собственной деятельности. Целесообразно, чтобы учащиеся сопровождали свои выступления средствами наглядности. Одним из видов факультативных занятий является практикум по решению задач. Он проводится, начиная с IX класса, в виде серии уроков решения задач по крупной теме. В этом случае появляется возможность решать комбинированные задачи. Этим практикум по решению задач отличается от уроков решения задач при изучении основного курса математики. На занятиях практикума по решению задач имеется возможность развивать самостоятельность учащихся, их творческие способности, соответствующим образом организуя их познавательную деятельность и предлагая нетривиальные задачи, в том числе исследовательские, повышенной сложности, с неполными или избыточными данными, задачи-парадоксы. На этих занятиях появляется возможность познакомит учащихся с некоторыми специфическими методами решения задач, например с методом размерностей, с методом графов. На факультативных занятиях нет необходимости ограничивать время на выполнение той или иной работы. Если учащийся проявляет интерес к какому-то определенному разделу математики, то можно предоставить ему возможность заниматься экспериментальной работой в области своих интересов. |