Планирование. Элективный курс. "Графы".

Пояснительная записка.

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

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

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

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

            Кроме того, понятие «граф» очень емко и тесно связано со многими основными понятиями, на которых базируется математика, в том числе школьная.

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

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

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

Формы и методы обучения.

Наряду с традиционными , в преподавании курса предусмотрено широкое применение таких форм занятий, как дискуссия, обсуждение, «мозговой штурм», «марафоны задач», деловые игры, круглый стол и пресс-конференция. Предусмотрены лабораторно-графические работы и математические раскраски. В преподавании курса опорными станут метод проектов (как учебных, так и творческих, и научно-исследовательских) и портфолио творческих и практических заданий по курсу.

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

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

Задачи программы:

- развивать интерес школьников к предмету;

- показать проникновение математических методов в науку и технику через теорию графов;

- помочь учащимся отойти от математических штампов; расширить их математический и общенаучный кругозор.

- обеспечить формирование и развитие навыков самообразования через поисковую и исследовательскую работу;

- сформировать восприятие математики как единого языка познания;

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

Учебно-тематический план

№ п/п	Тема занятия	Кол-во часов	Форма проведения занятия	Форма контроля.
1.	Сведения из истории графов.	1	Лекция – беседа.	Лабораторно-графическая работа
2.	Граф и его элементы.	1	Лекция – беседа.	Сообщение по теме.
3.	Некоторые свойства и теоремы.	1	Практическая работа.	Решение задач.
4.	Эйлеров и гамильтонов циклы.	2	Лекция. Практическая работа.	Решение задач. Лабораторно-графическая работа.
5.	Задачи о мостах. Рисование фигур единым росчерком.	2	Лекция. Практическая работа.	Самостоятельная работа. Конкурс красивых задач.
6.	История лабиринтов.	1	Сообщения учащихся. Беседа.	Поисковые задания.
7.	Геометрическая постановка задачи о лабиринте. Способы прохождения лабиринта.	2	Выполнение практических работ.	Практическая работа.
8.	Способы прохождения лабиринта. Лабиринты и графы.	2	Выполнение практических работ.	Практическая работа.
9. 10.	«Задача четырех красок».  Графы и правильная раскраска карты.	1 2	Сообщение по теме. Практическая работа. Выполнение практических работ	Творческие задания. Практическая  работа.
11.	Графы с цветными ребрами и их свойства.	2	Практикум по решению задач.	Сообщение по теме. Исследовательские задания.
12.	Дерево и лес. Понятие дерева в теории графов.	2	Лекция.	Творческие и исследовательские задания.
13.	Применение деревьев в решении  различных задач.	2	Практикум по составлению дерева решений.	Практическая  работа.
14.	Графы и логические задачи.	3	Практическое занятие.	Марафон задач. Зачетная работа. Выступления с рефератами.
15.	Сетевые графы.	2	Лекция учителя.	Деловая игра.
16.	Элементы теории планирования и управления.	2	Комментированный разбор задачи.	Деловая игра.
17.	Приложение теории графов в различных областях науки и техники.	3	Урок-конференция.	Защита исследовательских работ. Отбор работ на НПК.
18.	Зачетное занятие.	2	Выполнение зачетной работы.	Итоговая работа. Выставка работ.

           Требования к уровню подготовки учащихся.

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

            планирования и осуществления алгоритмической деятельности, выполнения заданных и конструирования новых алгоритмов;

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

            исследовательской деятельности, развития идей, проведения экспериментов, обобщения, постановки и формулирования новых задач;

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

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

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

В результате изучения спецкурса обучающиеся должны:

Знать/понимать

-понятие графа и его элементов, теоремы теории графов;

-понятие об эйлеровом и гамильтоновом циклах;

-историю возникновения задач о лабиринтах;

-знать условия «правильной раскраски» карт;

-понятие деревьев при описании различных вариантов игр и сочетаний  и разбиений

  композиций;

Уметь:

- пользоваться языком геометрии для описания предметов окружающего мира;

- чертить графы одним росчерком;

- решать геометрические задачи о лабиринтах;

-создавать и раскрашивать собственные карты;

- применять графы при решении некоторых типов логических задач ;рассматриваются задачи на     переливание, взвешивание, организацию круговых турниров;

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

    повседневной жизни.

                        Содержание программы.

Программа курса состоит из 18 разделов и рассчитана на учащихся 7-9классов.

 На изучение курса целесообразно отвести 34 часа.

Тема 1.

В этой теме приводится характеристика «Геометрии положений» (топологии), данная Эйлером в связи с решением исторической задачи о кенигсбергских мостах; формулируются основные понятия теории графов.

Исследование задачи о мостах Кенигсберга Эйлер в 1736 г представил в Петербургскую Академию Наук. Работа начинается определением той области математики, к которой относятся подобные вопросы:

«Кроме той области геометрии, которая рассматривает величины и способы измерения… Лейбниц первым упомянул о «геометрии положения», она занимается только расположением частей фигуры друг относительно друга, отвлекаясь от их размеров. Недавно мне пришлось слышать об одной задаче, относящейся к геометрии положения, и я решил изложить здесь в виде примера найденный мной способ решения этой задачи».

Далее Эйлер обосновывает невозможность решения этой задачи.

- Понятие графа и его элементов. Примеры графов. Полный граф. Четность вершины графа. Основные теоремы теории графов.

·         Если все вершины графа четные, граф можно начертить одним росчерком. Порядок движения любой.

·         Граф  с двумя нечетными вершинами можно начертить одним росчерком, начиная движение с одной и заканчивая на другой нечетной вершине.

·         Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.

Тема 2.

Учащимся дается понятие об эйлеровом и гамильтоновом циклах.

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

Граф может быть и эйлеровым, и гамильтоновым, или одним из них, или ни тем ни другим.

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

Учащимся предлагается составление аналогичных задач с учетом свойств графов.

Рассматриваются задачи на «маршруты путешествий» и «осмотр достопримечательностей»

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

Тема 3.

   Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке сказаний.

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

Возможен ли безвыходный лабиринт?

Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство городских коммуникаций, сетей дорог, каналов, рек, телеграфов и т.д. – все это более или менее сложные лабиринты.

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

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

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

Тема 4.

Учащиеся знакомятся с задачей раскраски карты. Задача известна достаточно давно, но в качестве теоремы или задачи впервые была выдвинута Мебиусом в 1840 году. Суть задачи в следующем:

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

Прослеживается аналогия этой задачи с Эйлеровой задачей о мостах, задачей о лабиринтах.

Учащимися формулируются условия возможности раскраски двумя красками, тремя, условия «правильной раскраски».

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

Тема тем более актуальна, что предположение о 4-х красках никто не доказал, но никто и не опроверг.

Тема 5.

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

Например, среди участников чемпионата в какой-то момент есть и уже сыгравшие, и еще не сыгравшие друг с другом. Или: среди множества стран есть установившие и не установившие дипломатические отношения.

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

Тема 6.

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

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

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

Кроме того, обобщается применение деревьев при описании различных вариантов игр и сочетаний или разбиений композиций.

Данная тема предполагает задания поискового и исследовательского характера.

Тема 7.

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

Тема 8.

Данная тема показывает построение сети сложного комплекса работ, определение по сети самого ответственного участка; формирует навык определения времени завершения работ и поиска резервов времени.

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

Наиболее удачной формой занятия по данной теме можно считать деловую игру.

Тема 9.

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

Занятие проводится в виде пресс-конференции или Круглого стола. Организуется стендовая защита поисковых и исследовательских работ.

Тема10.

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

               Учебно-методическое обеспечение

Тема 1                                                                                              Приложение 1

1.     Нарисуйте полный граф с n  вершинами, если: 

                n=2, n=3, n=5.

2.     Скольким ребрам принадлежит вершина в полном графе с n  вершинами,

                n=3, n=5, n=k?

3.     Существует ли полный граф с семью ребрами?

4.     Сколько ребер в полном графе с n вершинами, если

                n =3, n=4, n=5?

5.  Найдется ли граф с пятью вершинами, степени которых все различны, т.е.   равны 0, 1, 2, 3, 4?

6.  Нарисуйте граф с 5 вершинами, две из которых имеют одинаковую степень.

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

8.  Лабораторно-графическая работа .

Тема 2                                                                                                              

1.                      На рисунке схематически изображена речная сеть Москвы: река Москва, реки Яуза и Сходня, Химкинское водохранилище, острова. Через реки переброшены мосты, связывающие различные участки суши. Можно ли обойти за один раз все мосты на рисунке, проходя через каждый не более одного раза?                                                                                                                        

2.                      Контрабандист решил побывать во всех странах Европы, пересекая границу каждой только однажды. Возможно ли такое путешествие?

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

 

Тема 3.                                                                                                                

1.     Нарисуйте граф, соответствующий данному лабиринту.

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

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

Тема 4.                                                                                                            

1.     Раскрасьте предложенные карты минимально возможным количеством красок .

2.     Придумайте необычную карту и раскрасьте ее в минимальное количество цветов.

3.     Создайте карту, которую можно раскрасить в две, три, четыре краски.

Тема 5.                                                                                                                 

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

2.     На карте выбраны пять городов. Среди них из любых трех найдутся два, соединенные авиалиниями, и два – несоединенные. Доказать: 1) Каждый город соединен авиалиниями непосредственно только с двумя другими. 2) Вылетев из любого города, можно облететь остальные, побывав  в каждом по разу и вернуться назад.

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

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

5.     Докажите, что среди шести углов (острых) найдутся три угла А, В, С такие, что все их парные суммы А+В, А+С, В+С одновременно либо больше 90 ⁰ , либо одновременно не больше 90 ⁰ .

Тема 6.                                                                                                                 

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

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

3.     Сколько различных способов обедов П.И.Чичиков мог насчитать из блюд, выставленных на столе у П.П.Петуха, если бы на каждый обед выбирать одно холодное блюдо, одно первое, одно второе, одно третье? На столе у П.П.Петуха на этот раз были выставлены студень с хреном, красная икра, свежепосоленная рыба; на первое – уха из стерляди, щи с грибами; на второе – осетрина жареная, теленок жареный на вертеле; на третье – арбузы, груши.

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

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

6.     Составьте генеалогическое древо династии Романовых.

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

8.     Изобразите дерево возможных исходов при троекратном бросании монеты.

9.     Постройте дерево игры, показывающее ходы партнеров, приводящие к победе «крестиков», если игра начата ходами: а) (х1) и (о2), б) (х1) и (о9); в) (х5) и (о8).

10.  Рассади участников «Большой восьмерки» за круглым столом всеми возможными способами.

Тема 7.                                                                                                                 

1.     Беседуют трое друзей – Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас – блондин, другой – брюнет, третий – рыжий, но ни у кого цвет волос не соответствует фамилии».

Какой цвет волос у каждого из друзей?

2.     В Артеке за круглым столом оказалось пятеро ребят из Москвы, Санкт-Петербурга, Новгорода, Перми и Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между Томичем и Витей, санкт-петербуржец – между Юрой и Толей, а напротив него сидел пермяк и Алеша. Коля никогда не был в Санкт-Петербурге, Юра не бывал в Москве и Томске, а Томич с Толей регулярно переписываются.

Определите, кто в каком городе живет.

3. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что:

·        Вода и молоко не в бутылке.

·        Сосуд с лимонадом стоит между кувшином и сосудом с квасом.

·        В банке не лимонад и не вода.

·        Стакан стоит между банкой и сосудом с молоком.

В каком сосуде находится какая из жидкостей?

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

         5. На улице, встав в кружок, беседуют Аня, Валя, Галя и Надя.

·        Девочка в зеленом платье – не Аня и не Валя – стоит между девочкой в голубом платье и Надей.

·        Девочка в белом платье стоит между девочкой в розовом и Валей.

Какого цвета платье у каждой из девочек?

6.     В семье четверо детей. Им 5, 8, 13 и 15 лет. Зовут их Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори, а сумма лет Ани и Веры делится на три?

7.     Какое наименьшее число переливаний необходимо для того, чтобы с помощью 7-и 11-литровых сосудов и крана с водой отмерить 2 литра?

8.     Сколько существует различных трехзначных чисел, в записи которых участвуют лишь цифры 1, 2,3 и 4?

9.     Среди чисел, о которых говорится в задаче 8, сколько существует таких, в записи которых цифры не повторяются?

Тема 8.                                                                                                          

1.     В школе готовится новогодний вечер.

А) Назовите отдельные работы, которые при этом должны быть выполнены.

Б) Назовите несколько событий, которые включены в соответствующий сетевой график.

2. Приведите пример комплекса работ, который можно представить сетевым графиком. Составьте такой график.

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

4. По сетевому графику определите поздний срок наступления каждого события и резерв  времени.

Тема 9.

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

Тема 10.

Примерное содержание  зачетной работы.

1.     Нарисуйте полный граф с 6 вершинами.

2.     Определите степень какой-нибудь вершины полного графа с 20 вершинами.

3.     Определите количество ребер у полного графа с 20 вершинами.

4.     Нарисуйте граф с 6 вершинами, имеющий два цикла, каждый из которых проходит через все вершины.

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

6.     Приведите примеры связных и несвязных графов с 6 вершинами.

7.     Нарисуйте два связных графа с 5 вершинам так, чтобы один из них являлся деревом.

8.     В мастерской имеется 10 различных станков. Известно, что каждый из 10 рабочих этой мастерской умеет работать только на двух станках и на каждом станке умеют работать только двое рабочих. Можно ли расставить рабочих у станков так, чтобы каждый стоял у станка, на котором умеет работать?

9.     Придумайте жизненную ситуацию, описываемую ориентированным графом с 5 вершинами.

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

Самостоятельная работа №1

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

1) На рисунке 1 закрасьте те кружки, которые обозначают входы в парк, в красный цвет. Нарисуйте один из вариантов маршрута папы.

2) На рисунке 2 добавьте одну дорожку так, чтобы также можно было пройти по всем дорожкам парка только один раз, начав с одного входа и кончив в другом (в этом случае входы в парк могут быть другими). Закрасьте в красный цвет те кружки, которые будут обозначать входы в парк.

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

4) На рисунке 4 добавьте одну дорожку так, чтобы нельзя было за один обход пройти по всем дорожкам парка один раз. Новые дорожки должны начинаться от белых кружков и кончаться на белых кружках. Дорожки в парке должны пересекаться только в белых кружках.

 

                                                                                                        Приложение 2

Примерные задания для проведения марафона задач или олимпиады.

1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. Можно ли добраться с Земли до Марса?

2. В Солнечном городе есть 9 домов с номерами 1, 2, 3, 4, 5, 6, 7, 8, 9. Незнайка обнаружил, что два дома соединены дорогой в том и только том случае, если двузначное число, составленное из номеров этих домов, делится на 3, и никакие 2 дороги не пересекаются. Можно ли добраться из дома № 1 в дом № 9?

3. Доска имеет форму креста, который получается, если из квадратной доски 4 × 4 выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по одному разу?

4. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?

6. В городе Маленьком все еще 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?

7. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

8. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

9. Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов выходит на берег озера?

10. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.

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

                                                                                              Приложение 3.

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

1. Графы в головоломках.

2. Графы и игры на шахматной доске.

3. Геометрическая задача о лабиринтах.

4. Использование графов в школьных учебниках.

5. Графы в решении логических задач.

6. Графы и подсчет числа изомеров.

7. Графы в генетике.

8. Расчет сетевых графиков.

9. Графы и транспортные сети.

10. Графы в электротехнике.

11. Графы в психологии.

12. Проблема раскраски карты.

13. Графы и поиски анаграмм.

14. Графы в физике.

15. Графы с цветными ребрами.

Литература для учащихся.

1.      Барр с. Россыпи головоломок.- М. «Мир». 1987.

2.      Болл У, Коксетер Г. Математические эссе и развлечения. – М. «Мир», 1986.

3.      Гарднер М. Математические головоломки и развлечения. – М. «Мир», 1971.

4.      Гарднер М. Крестики-нолики. М., «Мир», 1988.

5.      Графы // Квант. 1994. - №6.

6.      Игнатьев Е.И. В царстве смекалки. Ростов-на-Дону, Ростовское книжное издательство, 1995.

7.      Лихтарников Л.М. Занимательные логические задачи. – СПБ.: Лань, МИК, 1996.

8.      Перельман Я.И. Занимательные задачи и опыты. – М, «Детская литература», 1972.

9.      Топология графов // Квант. – 2005. - №3.

10.   Энциклопедия для детей. Том 11. Математика. Тема «Графы». – М.: Аванта, 1998.

Литература для учителя

1.      Абрамов А.М, Березина Л.Ю. и др. Методика факультативных занятий в 7-8 классах. – М. «Просвещение», 1981.

2.      Асарина Е.Ю., Фрид М.Е. Математика выводит из лабиринта. – М. «Контекст», 1995.

3.      Березина Л.Ю. Графы и их применение. – М. «Просвещение», 1979.

4.      Гусев В.А, Орлов А.И. Розенталь А.Л. Внеклассная работа по математике в 6-8 классах. – М., «Просвещение», 1984.

5.      Графы и кратчайшие расстояния в них. – Математика. Приложение к газете «1 сентября». – 2001 - №15, 16.

6.      Литвинова С.А, Куликова Л.В, и др. За страницами учебника математики. Волгоград: Панорама, 2006.

7.      Нестеренко Ю.В., Олехник С.Н., Потапов М.К. Задачи на смекалку. М, «Дрофа», 2005.