Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой




Скачать 338.77 Kb.
НазваниеМетодическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой
страница1/4
Дата публикации21.05.2014
Размер338.77 Kb.
ТипМетодическое пособие
literature-edu.ru > Математика > Методическое пособие
  1   2   3   4
Введение
Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.

Дискретная математика для программистов относится к числу общепрофессиональных предметов, формирующих базовый уровень знаний, необходимых для изучения других дисциплин, таких, как «Программирование», «Архитектура ЭВМ», «Компьютерное моделирование» и других. Теория графов, как один из разделов дискретной математики, и связанные с ней методы исследования, используются на разных уровнях не только во всей современной математике, но и нашли широкое примениние в областях не связанных непосредственно с математикой.

Данная методическая разработка предназначена для студентов, обучающихся на третьем курсе по специальности 050202 «Информатика».

Целью методической разработки является помощь студентам в самостоятельной работе над теоретическим материалом для более успешной подготовки к выполнению практических упражнений, проверка знаний и практических навыков решения задач по указанным разделам данного курса, а также в качестве закрепления теоретического материала и осуществления качественного самоконтроля. Но также может быть использована как задачник для выполнения домней контрольной работы или просто для отработки полученных знаний умений и навыков.

В работе даны необходимые теоретические сведения, рассмотрено подробное решение наиболее показательных задач;

выделен необходимый для полного раскрытия темы круг контрольных вопросов, составленный в соответствии с государственными требованиями к минимуму содержания и уровню подготовки студентов по данной теме.

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой.

Указана учебная литература, рекомендуемая для успешного изучения материала.
История развития теории графов
На самом западе России есть город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рисунке 1.
старинная карта кёнигсберга. буквами обозначены части города: а — альтштадт, б — кнайпхоф, в — ломзе, г — форштадт. цифрами обозначены мосты (в порядке строительства): 1 — лавочный, 2 — зелёный, 3 — рабочий, 4 — кузнечный, 5 — деревянный, 6 — высокий, 7 — медовый




Рис 1. Кенигсберг
Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Причем он не только решил эту конкретную задачу, но и придумал общий метод решения

подобных задач. Поэтому, родоначальником теории графов принято считать Леонарда Эйлера.

По поводу обнаруженного  им  способа  решать задачи подобного рода Эйлер писал "Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы,имеющие совсем мало отношения к математике, скорее разрешаются математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Эйлер поступил следующим образом: он «сжал» берега в точки, а мосты «вытянул» в линию. В результате получилась фигура изображенная на рисунке 2.

граф кёнигсбергских мостов

Рис 2. Схема мостов Кенигсберга

Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, что если из всех точек или вершин выходит четное количество линий, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии), пройти по всем линиям только по одному разу. При этом движение можно начать с любой вершины и окончить в той же вершине.

Если схема содержит только две нечетные вершины, то задача тоже имеет решение, то есть можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.

Схему с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

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

Это была первая работа по теории графов великого русского математика швейцарского происхождения Леонарда Эйлера.

Задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел  математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков К. Берж, О. Оре, А. Зыков.


  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconСергей Николаевич Бердышев Технологии работы с клиентами разной трудности
Пособие содержит большое количество кейсов, с помощью которых легко понять особенности работы с различными заказчиками. Книга рассчитана...

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconНаркотическая угроза: знать, чтобы выжить!
Теперь совершенно очевидно, что она характерна не только для стран Западного мира. Этим злом оказались поражены народы всех континентов...

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconМетодические указания по написанию контрольных работ 26 Ким для аттестации остаточных знаний 28
Учебно-методическое пособие предназначено для студентов направления: 080100, 080200, 100100, 100400, 230400, 072500

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconМеждународные валютные отношения и валютный рынок Методическое пособие
Методическое пособие предназначено для студентов, обучающихся по специальности «Финансы и кредит» заочной формы обучения

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconУчебно-методическое пособие для студентов Нижний Новгород 2009
Темперамент, Характер. Воля: Учебно-методическое пособие для студентов. Н. Новгород: нгпу, 2009. 42с

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconУчебно-методическое пособие для проведения практических занятий для...
Методы научных исследований: учебно-методическое пособие для проведения практических

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconУчебно-методическое пособие Н. Новгород
...

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconУчебно-методическое пособие для студентов специальностей «История»
Шинаков Е. А., Поляков Г. П., Чубур А. А. Основы восточноевропейской археологии (учебно-методическое пособие). – Брянск, рио бгу,...

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconИ самостоятельной работы студентов
Учебное пособие предназначено для студентов Волжского государственного инженерно-педагогического университета, обучающихся по специальности...

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой iconУчебное пособие Текст предоставлен правообладателем Логопатопсихология:...
«Логопатопсихология: учеб пособие для студентов / под ред. Р. И. Лалаевой, С. Н. Шаховской.»: Гуманитарный издательский центр владос;...

Литература


Заказать интернет-магазин под ключ!

При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции