Обучение учащихся поиску решения задач при изучении элементов теории графов задач на факультативных занятиях в школе. Курсовая работа (т). Педагогика.

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Вы можете узнать стоимость помощи в написании студенческой работы.


Помощь в написании работы, которую точно примут!

Похожие работы на - Обучение учащихся поиску решения задач при изучении элементов теории графов задач на факультативных занятиях в школе
Нужна качественная работа без плагиата?

Не нашел материал для своей работы?


Поможем написать качественную работу Без плагиата!

Объём работы: 56 станицы, из них … основного текста, 2 приложения и
список использованных литературных источников (25 источников). В работе 60
рисунков, 1 таблица, 5 схем. Работа состоит из введения, двух глав, заключения
и списка литературы.


КЛЮЧЕВЫЕ СЛОВА: ГРАФЫ, МАТЕМАТИКА, ОБУЧЕНИЕ, РЕШЕНИЕ ЗАДАЧ,
ФАКУЛЬТАТИВНЫЕ ЗАНЯТИЯ, ШКОЛА.


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


Объектом исследования: процесс обучения решению задач на факультативных
занятиях в школе.


Предмет исследования: графы как средство поиска решения задач.


Для достижения поставленной цели необходимо решить следующие задачи:


)       Изучить психолого-педагогическую и методическую литературу по
проблеме обучения учащихся решению задач.


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


)       Отразить роль факультативных занятий как одной из форм
внеклассной работы по математике.


)       Разработать содержание факультативных занятий по теме “Элементы
теории графов” и методики их проведения.


)       Составить и подобрать задачи, решаемые с использованием теории
графов.


Для решения поставленных задач, использовались следующие методы
исследования:


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


практические: разработка содержания и методика проведения факультативных
занятий по теме “Элементы теории графов”; составление и подбор задач, решаемых
с использованием теории графов.


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


Сфера применения: общеобразовательные учреждения Республики Беларусь.







ГЛАВА 1. ВОПРОСЫ ТЕОРИИ ГРАФОВ ПРИ ОБУЧЕНИИ В СРЕДНЕЙ ШКОЛЕ


.1     Роль и функции задач в обучении математике


.2     Роль задач в развитии мышления учащихся


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


.4 Графы как средство обучения учащихся поиску решения задач


ГЛАВА 2. МЕТОДИКА ОБУЧЕНИЯ УЧАЩИХСЯ РЕШЕНИЮ ЗАДАЧ С
ИСПОЛЬЗОВАНИЕМ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ


.1 Роль факультативных занятий как формы обучения математике


.2 Содержание и программа факультативных занятий по теме
“Элементы теории графов”


.3 Методика проведения занятий по решению задач на
факультативных занятиях по теме “Элементы теории графов”


.3.1 Вводное занятие “Сфера применения теории графов”


.3.5 Задача о нахождении кратчайшего пути в графе


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


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


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


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


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


Объектом исследования: процесс обучения решению задач на факультативных
занятиях в школе.


Предмет исследования: графы как средство поиска решения задач.


Для достижения поставленной цели необходимо решить следующие задачи:


1. Изучить психолого-педагогическую и
методическую литературу по проблеме обучения учащихся решению задач.


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


3. Отразить роль факультативных занятий
как одной из форм внеклассной работы по математике.


4. Разработать содержание факультативных
занятий по теме “Элементы теории графов” и методики их проведения.


5. Составить и подобрать задачи,
решаемые с использованием теории графов.


Для решения поставленных задач, использовались следующие методы
исследования:


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


практические: разработка содержания и методика проведения факультативных
занятий по теме “Элементы теории графов”; составление и подбор задач, решаемых
с использованием теории графов.


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


Сфера применения: общеобразовательные учреждения Республики Беларусь.









1.1   Роль и функции задач в
обучении математике




В обучении математике задачам всегда отводилась достаточно большая, если
не решающая, роль. Сейчас всё большее распространение получает прогрессивный
метод обучения через задачи как реализация системы проблемного обучения.
Основные идеи этого метода находят в какой-то мере отражение в новых учебниках.
Задачи становятся не только и не столько целью, сколько средством обучения.
Исторически сложилось, что на ранних этапах развития математики решение задач
было целью обучения. Ученик должен был заучить образцы и затем подводить под
эти образцы решения задач. В основном решались типовые, стандартные задачи,
принадлежащие классам алгоритмически разрешимых задач, т.е. таких, для которых
существует общий метод (алгоритм) решения.


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


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


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


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


В книге М. И. Махмутов рассказывает об исследовании, проведённом группой
учёных, математиков и психологов с целью выявления закономерностей активизации
познавательной деятельности учащихся. Там отмечается, что напряжение
интеллектуальных сил ученика вызывается главным образом постановкой проблемных
вопросов, проблемных познавательных задач и учебных заданий исследовательского
характера. Это напряжение рождается в столкновении с трудностью в понимании и
осмыслении нового факта или понятия и характеризуется наличием проблемной
ситуации, высокого интереса учащегося к теме, его эмоционального настроя и
волевого усилия"[9] .


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


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


При обучении математике задачи имеют большое и многостороннее значение.


Образовательная функция математических задач. Решая математическую
задачу, человек познает много нового: знакомится с новой ситуацией, описанной в
задаче, с применением математической теории к ее решению, познает новый метод
решения или новые теоретические разделы математики, необходимые для решения
задачи, и т. д. Иными словами, при решении математических задач человек
приобретает математические знания, повышает свое математическое образование.
При овладении методом решения некоторого класса задач у человека формируется
умение решать такие задачи, а при достаточной тренировке - и навык, что тоже
повышает уровень математического образования.


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


Это означает, что при обучении математике учащимся следует предлагать
задачи, связанные со смежными дисциплинами (физикой, химией, географией и др.),
а также задачи с техническим и практическим, жизненным содержанием.


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


Воспитательная функция математических задач. Прежде всего, задача
воспитывает своей фабулой, текстовым содержанием. Поэтому фабула многих
математических задач существенно изменяется в различные периоды развития
общества. Воспитывает не только фабула задачи, воспитывает весь процесс
обучения решению математических задач. Правильно поставленное обучение решению
математических задач воспитывает у учеников честность и правдивость,
настойчивость в преодолении трудностей, интерес к предмету и заинтересованность
в применении математических знаний. Ознакомление учащихся с элементами теории
графов расширяет возможности раскрытия в процессе обучения сфер применимости
математики и дает возможность показать учащимся ее практическую значимость, в
частности, применения в некоторых областях деятельности [7,10,14,16].




1.2   Роль задач в развитии
мышления учащихся


Решение задач требует применения многочисленных
мыслительных умений: анализировать заданную ситуацию, сопоставлять данные и
искомые, решаемую задачу с решенными ранее, выявляя скрытые свойства заданной
ситуации; конструировать простейшие математические модели, осуществляя
мысленный эксперимент; синтезировать, отбирая полезную для решения задачи
информацию, систематизируя ее; кратко и четко, в виде текста, символически,
графически и т. д. оформлять свои мысли; объективно оценивать полученные при
решении задачи результаты, обобщать или специализировать результаты решения
задачи, исследовать особые проявления заданной ситуации. Сказанное говорит о
необходимости учитывать при обучении решению математических задач современные
достижения психологической навыки.


Исследованиями психологов установлено, что уже
восприятие задачи различно у различных учащихся данного класса. Способный к
математике ученик воспринимает и единичные элементы задачи, и комплексы ее
взаимосвязанных элементов, и роль каждого элемента в комплексе. Средний ученик
воспринимает лишь отдельные элементы задачи. Поэтому при обучении решению задач
необходимо специально анализировать с учащимися связь и отношения элементов
задачи. Так облегчится выбор приемов переработки условия задачи. При решении
задач часто приходится обращаться к памяти. Индивидуальная память способного к
математике ученика сохраняет не всю информацию, а преимущественно «обобщенные и
свернутые структуры». Сохранение такой информации не загружает мозг избыточной
информацией, а запоминаемую информацию позволяет дольше хранить и легче
использовать. Обучение обобщениям при решении задач развивает, таким образом,
не только мышление, но и память, формирует «обобщенные ассоциации». При
непосредственном решении математических задач и обучении их решению необходимо
все это учитывать.


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


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


Правильно организованное обучение решению задач приучает к полноценной
аргументации со ссылкой в соответствующих случаях на аксиомы, введенные
определения и ранее доказанные теоремы. С целью приучения к достаточно полной и
точной аргументации полезно время от времени предлагать учащимся записывать
решение задач в два столбца: слева - утверждения, выкладки, вычисления, справа
- аргументы, т.е. предложения, подтверждающие правильность вызванных
утверждений, выполняемых выкладкой и вычислений. Разумеется, нет необходимости
так записывать решение каждой задачи, допустима и устная аргументация.


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


Умение рассуждать включает в себя
и умение оценивать истинность или ложность высказываний, правильно составлять
сложные высказывания и суждения, т. е. логически правильно употреблять союзы
«и», «или», отрицание «не». Обучение верному применению этих связок помогает
воспитанию у учащихся математически грамотной речи, а мышление, как известно,
связано с языком, речью человека. Полезно научить школьников, верно, формулировать отрицания
тех или иных предложений. Такое умение особенно важно при решении задач
сведением к противоречию. Существенно
для развития математического мышления учащихся формирование умений правильно
выделять посылки и заключения. Такие умения формируются обычно при решении
задач на доказательство. На первых же порах необходимы упражнения в выделении в
некоторых предложений посылок и заключений.


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


Эффективность учебной деятельности по развитию мышления во многом зависит
от степени творческой активности учащихся при решении математических задач. Следовательно,
необходимы математические задачи и упражнения, которые бы активизировали
мыслительную деятельность школьников. Так, например, А. Ф. Эсаулов [21]
подразделяет задачи на следующие виды: задачи, рассчитанные на воспроизведение
(при их решении опираются на память и внимание); задачи, решение которых
приводит к новой, неизвестной до этого мысли, идее; творческие задачи.
Активизирует и развивает мышление учащихся решение задач двух последних видов.


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




1.3   История и основные понятия теории графов




Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в
то время «задачу о кенигсбергских мостах», ставшей впоследствии одной из
классических задач теории графов.


Леонард Эйлер (1707-1783) - математик, механик, физик и астроном. Он
автор более 850 трудов по механике, теории движения Луны и планет, по
географии, по теории кораблестроения, теории музыки и другим наукам.


Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.
Историю возникновения этой теории можно проследить по переписке великого
ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому
математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года
[17]:


"Некогда мне была предложена задача об острове, расположенном в
городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов.
Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды
через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог
это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и
банальный, показался мне, однако, достойным внимания тем, что для его решения
недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих
размышлений было найдено правило, основанное на вполне убедительном
доказательстве, с помощью которого можно во всех задачах такого рода тотчас же
определить, может ли быть совершен такой обход через какое угодно число и как
угодно расположенных мостов или не может. Кенигсбергские же мосты расположены
так, что их можно представить на следующем рисунке, на котором A обозначает
остров, а B, C и D - части континента, отделенные друг от друга рукавами реки.
Семь мостов обозначены буквами a, b, c, d, e, f, g ":


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


Так можно ли обойти Кенигсбергские мосты, проходя только один раз через
каждый из этих мостов (рис.1.3.1)? Чтобы найти ответ, продолжим письмо Эйлера к
Маринони:


"Вопрос состоит в том, чтобы определить, можно ли обойти все эти
семь мостов, проходя через каждый только однажды, или нельзя. Мое правило
приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть,
сколько есть участков, разделенных водой, - таких, у которых нет другого
перехода с одного на другой, кроме как через мост. В данном примере таких
участков четыре - A,B,C,D.


Далее нужно различать, является ли число мостов, ведущих к этим отдельным
участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять
мостов, а к остальным - по три моста, т. е. Число мостов, ведущих к отдельным
участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это
определено, применяем следующее правило: если бы число мостов, ведущих к
каждому отдельному участку, было четным, то тогда обход, о котором идет речь,
был бы возможен, и в то же время можно было бы начать этот обход с любого
участка. Если же из этих чисел два были бы нечетные, ибо только одно быть
нечетным не может, то и тогда мог бы совершиться переход, как это предписано,
но только начало обхода непременно должно быть взято от одного из тех двух
участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше
двух участков, к которым ведет нечетное число мостов, то тогда такое движение
вообще невозможно… если можно было привести здесь другие, более серьезные
задачи, этот метод мог бы принести еще большую пользу и им не следовало бы
пренебрегать".


Слово «граф» в математике означает картинку, где нарисовано несколько
точек, некоторые из которых соединены линиями. Прежде всего, стоит сказать о
том, что графы, о которых пойдет речь, к аристократам былых времен никакого
отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что
значит «пишу». Тот же корень в словах «график», «биография». В математике
определение графа дается так: графом называется конечное множество точек,
некоторые из которых соединены линиями. Точки называются вершинами графа, а
соединяющие линии - рёбрами.


Схема графа, состоящая из «изолированных» вершин, называется нулевым
графом (рис.1.3.2).


Графы, в которых не построены все возможные ребра, называются неполными
графами (рис.1.3.3).


Графы, в которых построены все возможные ребра, называются полными
графами (рис.1.3.4).




Граф, каждая вершина которого соединена с ребром любой другой вершины,
называется полным. Заметим, что если полный граф имеет n вершин, то количество
ребер будет равно n(n-1)/2. Действительно, количество ребер в полном графе с n
вершинами определяется как число неупорядоченных пар, составленных из всех n
точек-ребер графа, т.е. как число сочетаний из n элементов по 2: граф, не
являющийся полным, можно дополнить до полного с теми же вершинами, добавив
недостающие ребра. Так, например, на рисунке 1.3.3 изображен неполный граф с
пятью вершинами. На рисунке 1.3.4 ребра превращающие граф в полный граф
изображены другим цветом, совокупность вершин графа с этими ребрами называется
дополнением графа.


а) Степени вершин и подсчет числа ребер.


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




На рисунке 1.3.5 изображен граф с пятью вершинами. Степень вершины А
обозначим ст.А. На рисунке : ст.А = 1, ст.Б = 2, ст.В = 3, ст.Г = 2, ст.Д = 0.


Сформулируем некоторые закономерности, присущие определенным графам.


Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них
на 1 меньше числа вершин этого графа.


Доказательство: эта закономерность очевидна уже после рассмотрения любого
полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой
себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n-1 ребро, что
и требовалось доказать.


Закономерность 2. Сумма степеней вершин графа число четное, равное
удвоенному числу ребер графа. Эта закономерность справедлива не только для
полного, но и для любого графа.


Доказательство: действительно, каждое ребро графа связывает две вершины.
Значит, если будем складывать число степеней всех вершин графа, то получим
удвоенное число ребер 2R (R - число ребер графа), т. к. каждое ребро было
подсчитано дважды, что и требовалось доказать.


Попробуем граф, изображенный на рис.1.3.6, обвести одним росчерком, то
есть, не отрывая карандаша от листа бумаги и не проходя по одной и той же части
линии более одного раза. Фигура эта, такая простая на вид, оказывается, имеет
интересную особенность. Если мы начнем движение из вершины В, то у нас это
обязательно получится. А что будет, если мы начнем движение из верины А? Легко
убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет
оставаться не пройденные ребра, добраться до которых уже невозможно.




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


Графы, начерченные на рис.1.3.8(а,б) и также можно начертить одним
росчерком пера.




Теперь попробуем вычертить одним росчерком граф, изображенный на
рис.1.3.9. Вам это сделать не удалось! Почему? Вы не можете найти нужную
вершину? Нет! Дело не в этом. Этот граф вообще нельзя вычертить одним росчерком
пера.




Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А, из
него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти
по каждому из этих ребер, должны выйти из вершины А по одному из них, в какой -
то момент обязательно вернуться в него по второму и выйти по третьему. А вот
снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то
закончить в нем не сможем.


Допустим теперь, что вершина А не является началом. Тогда в процессе
вычерчивания мы должны войти в него по одному из ребер, выйти из него по -
другому и снова вернуться по третьему. А так как выйти из него мы не сможем, то
вершина А в этом случае должен являться концом. Но про три другие вершины
нашего графа можно сказать то же самое. Но ведь и начальной вершиной
вычерчивания может быть только одна вершина, и конечной вершиной также может
быть только одна вершина! А значит, вычерчивать этот граф одним росчерком
невозможно.


Граф, который можно нарисовать, не отрывая карандаша от бумаги,
называется эйлеровым графом (рис.1.3.8). Такими графы названы в честь учёного
Леонарда Эйлера.


Закономерность 1. (вытекает из рассмотренной нами теоремы). Невозможно
начертить граф с нечетным числом нечетных вершин.


Закономерность 2. Если все вершины графа четные, то можно не отрывая
карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один
раз, начертить этот граф. Движение можно начать с любой вершины и закончить его
в той же вершине.


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


Закономерность 4. Граф, имеющий более двух нечетных вершин, невозможно
начертить «одним росчерком».


Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги,
называется уникурсальной.


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




рис.1.3.10                    рис.1.3.11




На рисунке 1.3.10, очевидно, изображен несвязный граф. Если, например, на
рисунке между вершинами Д и Е провести ребро, то граф станет связным
(рис.1.3.11).Такое ребро в теории графов (после удаления которого граф из
связного превращается в несвязный) называется мостом.


Примерами мостов на рисунке 1.3.10 могли бы служить ребра ДЕ, A3, ВЖ и
др., каждое из которых соединяло бы вершины «изолированных» частей графа
(рис.1.3.11).


Несвязный граф состоит из нескольких «кусков». Эти «куски» называются
компонентами связности графа. Каждая компонента связности является, конечно,
связным графом. Отметим, что связный граф имеет одну компоненту связности.


Теорема. Граф является эйлеровым тогда и только тогда, когда он связан и
имеет не более двух нечетных вершин.


Доказательство: Рисуя граф каждую вершину, за исключением начальной и
конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех

2.3.2 Занимательные задачи Курсовая работа (т). Педагогика.
Контрольная работа по теме Дьявол и демон: образ персонажа в трактате Бартоло да Сассоферрато 'Процесс сатаны против человеческого рода'
Курсовая работа по теме Разработка финансовой стратегии предприятия ОАО 'Надежда'
Дипломная работа: Захоплення на базі екскаватора одноковшового
Доклад: Белые цветы Осириса и слезы Исиды
Статья: Когда прекращать тестирование программ?
Курсовая работа по теме Незаконное производство, сбыт или пересылка наркотических веществ или их аналогов
Реферат по теме Кредитно-модульная система в Одесском национальном политехническом университете и проблемы её функционирования
Дипломная работа: Анализ конкурентной среды Кемеровского молочного комбината. Скачать бесплатно и без регистрации
Курсовая работа: Правовые проблемы наследования по закону
Реферат по теме Мой любимый уголок Москвы - Усадьба Кусково
Сочинение по теме "А был он лишь солдат…"
День Учителя Мини Сочинение
Дипломная работа по теме Управление адаптацией персонала
Курсовая Работа 2022 Образец
Практическая Работа По Молекулярной Биологии
Дипломная Работа На Тему Розробка Політики Розподілу Прибутку На Торговельному Підприємстві
Создание Информационной Системы Курсовая
Реферат: Опера
Сочинение Весна 5 Класс
Реферат: Архитектуры реализации корпоративных информационных систем
Реферат: Научные революции и их разновидности
Статья: Дача и дачники в русском представлении
заканчиваться некоторым зримым результатом, некоторой вехой (milestone).