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

Муниципальное бюджетное общеобразовательное учреждение
"Средняя школа №4"
муниципального образования "город Десногорск" Смоленской области.
Исследовательская работа на тему:
«ГРАФЫ КАК СРЕДСТВО ОБУЧЕНИЯ УЧАЩИХСЯ ПОИСКУ РЕШЕНИЯ ЗАДАЧ».
Выполнил:
Сологубов Николай Геннадьевич
Учитель информатики
МБОУ «СШ» №4 г. Десногорск.
Десногорск, 2017
Содержание.
TOC \o "1-3" \h \z \u Введение. PAGEREF _Toc478857929 \h 3Глава 1. Графы на уроках информатики. PAGEREF _Toc478857930 \h 7Глава 2. Графы в ОГЭ и ЕГЭ по информатике. PAGEREF _Toc478857931 \h 10Заключение. PAGEREF _Toc478857932 \h 25Список литературы. PAGEREF _Toc478857933 \h 26Приложения к исследовательской работе по теме ««ГРАФЫ КАК СРЕДСТВО ОБУЧЕНИЯ УЧАЩИХСЯ ПОИСКУ РЕШЕНИЯ ЗАДАЧ». PAGEREF _Toc478857934 \h 28ПРИЛОЖЕНИЕ №1. PAGEREF _Toc478857935 \h 28ПРИЛОЖЕНИЕ №2. PAGEREF _Toc478857936 \h 29ПРИЛОЖЕНИЕ №3 PAGEREF _Toc478857937 \h 32ПРИЛОЖЕНИЕ №4. PAGEREF _Toc478857938 \h 36ПРИЛОЖЕНИЕ №5. PAGEREF _Toc478857939 \h 38
Введение.Сегодня понятия и утверждения теории графов широко применяется практически во всех научных дисциплинах, экономике, технике. Являясь частью дискретной математики, теория графов используется в программировании для создания эффективных алгоритмов. В целом, анализируя учебные программы университетов, можно с уверенностью говорить, что учащиеся физико-математических, механико-математических и других факультетов связанных с изучением математики, активно изучают теорию графов как отдельный курс. Данные курсы помогают освоить многочисленную теорию, связанную с графами , но самое главное они показывают все разнообразие применения графов при решении конкретных задач из реальной жизни. Не смотря на то, что в школьной программе изучение теории графов явно не предусмотрено, некоторые положения теории графов могут и должны быть отражены при обучении математике и информатике.
Проблема исследования: каким образом можно применить теорию графов при решении конкретных задач школьного курса информатики?
Цель исследования: изучение графов как средства обучения учащихся поиску решения задач.
Объект исследования: процесс обучения в старшем и среднем звене общеобразовательных школ.
Предмет исследования: теория графов как средство при решении конкретных задач.
Гипотеза исследования: использование графов, при решении конкретных задач на уроке способствует:
Формированию математического мировоззрения, расширению и углублению теоретических и практических основ информатики;
Развитию логического мышления учащихся, культуры математической речи;
Побуждению к применению полученных знаний, умений на практике;
Задачи исследования:
Изучить учебную, методическую литературу по данной теме;
Проанализировать образовательные программы 8 —11 классов, задание ОГЭ и ЕГЭ;
Разобрать некоторые практические задачи, сравнить подходы к решению задач без использования и с использованием графов.
Подобрать задачный материал по данной теме.
Методологическую основу данного исследования составляют:
работы российских и зарубежных математиков по теории графов: Эйлера Л. , Березиной Л.Ю. , Носова В. А., Мельникова О.И., Берж К. , Кристофидес Н., Зыкова А.А. , Харари Ф., Татт У..
Методы исследования:
Теоретический анализ учебной, методической литературы по теме исследования;
Эксперимент на уроках информатики;
Изучение и обобщение передового педагогического опыта.
Теоретическая значимость: проанализированы и обобщены некоторые теоретические аспекты теории графов , а также изучены различные приемы поиска решения задач с помощью графов, подобраны задачи для разбора на уроках, подготовлена таблица применения графов в реальной жизни.
Научная новизна и практическая значимость:
Полученные в результате работы данные по использованию графов как средства при поиске решения задач в учебном процессе могут быть использованы в работе учителей 8 —11 классов для повышения эффективности занятий, познавательной активности обучающихся на уроках.
Актуальность:
Стоит помнить, что отдельный пласт предлагаемых в школьных учебниках и сборниках задач, заданий из ОГЭ и ЕГЭ можно красиво и доступно решать с учащимися, используя графы, некоторые из них «требуют» применения графов. Это позволяет расширить спектр средств, используемых при решении задач, упростить поиск решения и в некоторых случаях существенно сократить время на поиск правильного ответа.
Помимо очевидной популярности элементов теории графов, огромного разнообразия применения и присутствия в ОГЭ и ЕГЭ, существует «живой» интерес со стороны учащихся. На уроках информатики в 8-11 классах была предложена одна задача:
Задача о трех домах и трех колодцах.
Имеется 3 дома и 3 колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались.

Формулировка и подача задачи, на первый взгляд соответствует уровню начальной школы, что и подкупило всех без исключения учащихся, которые в туже минуту стали рисовать схемы у себя в тетрадях, не подозревая о том, что задача является одной из фундаментальных в теории графов. Спустя некоторое время, после первых неудач, подход к задаче изменился, и теперь все с упорством и легким недоумением смотрели на «детскую» задачку. Таким образом, за истечением урока ответа ни один из 13 классов (8-11 параллели) так и не получил. В тот момент в учащихся проснулись исследователи, каждый из которых принципиально отказался от использования интернета, все хотели получить ответ сами на такую «простую» задачу. Конечно после нескольких неудач, в ученике назревала идея о том что это невозможно, но новые попытки совершались вновь и вновь . Некоторые из вариантов представлены в ПРИЛОЖЕНИЕ №1. Лишь спустя несколько дней, с изрисованными листами, компьютерными моделями, ученики, сами изучив некоторые элементы графов, в частности теорему Эйлера (ПРИЛОЖЕНИЕ №2), смогли дать ответ: нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.
Именно подобный интерес к практическим задачам и стал основой для дальнейшего продвижения графов на уроках информатики.
Глава 1. Графы на уроках информатики.Тема «Теория графов » имеет ярко выраженную, прикладную направленность (ПРИЛОЖЕНИЕ №3). На простых примерах учащимся можно показать, как можно применить язык теории графов к решению различных практических задач. В качестве стандартного примера можно привести задачу на построение генеалогического древа (граф - дерево), задачу о 3 домах и 3 колодцах или более сложную задачу о Кенигсбергских мостах, которая и является началом всей теории графов. Задачу о мостах, не смотря на ее сложность, можно предложить с 5 по 11 класс.
Как и задача о 3 мостах и 3 колодцах данная задача была предложена в 8-11 классах, но учащиеся уже были более аккуратны и рассудительны, зная о том, что это совсем не такая простая задача как может казаться. Подобная задача была разобрана на факультативных занятиях.
Задача о Кенигсбергских мостах. Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту. Благодаря этой задаче была создана теория графов.

Рис 1
Мосты через реку Прегель расположены как на рисунке. (рис.1).
Проблема семи мостов Кёнигсберга.Суть: можно ли пройти по 7 мостам города Кёнигсберга, не ступив на каждый более одного раза.
Решение: было найдено русско-немецким математиком Леонардом Эйлером в 1736 году.(ПРИЛОЖЕНИЕ №4).
Его рассуждения заключались в следующем:
1) Число нечётных вершин графа должно быть чётно.2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.4) Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Конечно ученик, не зная основ теории графов, вряд ли сможет провести аналогичные рассуждения, но это не означает, что его решение будет неверным. Многие учащиеся на интуитивном уровне объясняют решение задачи о 7 мостах, некоторые из рассуждений действительно похожи на «эталонные»,которые были приведены выше.
Задач, которые можно показать на уроке огромное количество, для поиска решения которых целесообразно рисовать графы или пользоваться некоторыми их свойствами. Самое интересное что ученику для их решения порой достаточно базовых знаний из теорий графов. Список некоторых задач с решениями представлен в ПРИЛОЖЕНИИ №5.
Как показывает эксперимент проведенный в 8-11 классах с задачами о колодцах и мостах , решение с помощью графа, вовлекает в процесс не только учащихся заинтересованных в изучении физико-математических дисциплин , но и детей с гуманитарным складом ума. Если для физмата этот инструмент воспринимается как еще один мощный способ при поиске решения, то для гуманитарного профиля это возможность для проявления своих творческих возможностей. Ведь один и тот же граф можно построить абсолютно по-разному.
Глава 2. Графы в ОГЭ и ЕГЭ по информатике.Анализируя некоторые методы решения заданий из ОГЭ и ЕГЭ, можно сказать о «туманности» многих из этих способов. Если рассмотреть задания из ОГЭ по информатики можно выделить два задания, к которым в явном виде можно применить метод решения с помощью графов. В Демоверсии ОГЭ по информатики такие задания встречаются под номерами: 3,11. Ниже приведены формулировки данных заданий и 2 способа решения:
Задание №3 Демоверсия ОГЭ 2017.

1 способ без графа
Решение
В пункт Е можно приехать только из пункта С.
Дорога АСЕ = 5 + 2 = 7 км
Но в С можно приехать не только из А, но и из В и Д.
Дорога АВСЕ = 2 + 1 + 2 = 5 км
Дорога АДСЕ = 1 + 3 + 2 = 6 км
Значит, наиболее короткой является дорога АВСE = 5 км
2 способ используется граф
Решение
Необходимо построить граф по таблице. В нашем случае город это вершина графа, дорога между городами – ребро графа (Если на пересечении в таблице стоит число, значит между городами есть дорога. То есть, по нашей терминологии 2 вершины соединяются ребром ).
Анализ начинаем с города А, далее город B,C,D и E.
Между городом А и В есть дорога, расстояние равно 2
A
B
2

Между городом А и C есть дорога, расстояние равно 5
2
A
B
C
5

Между городом А и D есть дорога, расстояние равно 1
2
A
B
C
5
D
1

Между городом А и E прямой дороги нет
2
A
B
C
5
D
1
E

Между городом B и A есть дорога, расстояние равно 2. (Таблица симметрична относительно главной диагонали, следовательно если между городом А и В есть дорога, то и между городом B и А есть дорога причем расстояние одинаково!) На графе такая дорога уже нарисована!!!
Между городом B и С есть дорога, расстояние равно 1
2
A
B
C
5
D
1
E
1

Между городом В и E,D прямой дороги нет.
Между городом С и А,B есть дорога, расстояние соответственно 5 и 1. Данные дороги уже нарисованы.
Между городом С и D есть дорога, расстояние равно 3.
2
A
B
C
5
D
1
E
1
3

Между городом С и Е есть дорога, расстояние равно 2.
3
2
A
B
C
5
D
1
E
1
2

Проанализировав таблицу, далее очевидно, что все оставшиеся дороги уже построены.
Осталось лишь перебрать всевозможные варианты перемещения из города А в город Е. В данной задаче самый короткий путь оказался АBCE и он равен 5.
Сравнивая 2 подхода к поиску решения можно выделить плюсы и минусы каждого метода.
1 способ без графа 2 способ с графом
+ - + -
Краткая запись решения Отсутствие наглядности. Перебор путей осуществляется в уме. Возникает возможность пропустить один из «неявных путей». Граф позволяет наглядно ориентироваться в задаче. Перебор путей становится более удобным. Шансов пропустить один из путей существенно сокращается Запись решения задачи увеличивается за счет дополнительного действия – построения графа
Задание № 11 в формулировке уже можно увидеть готовый граф.
Задание №11 Демоверсия ОГЭ 2017.

В данном случае речь уже идет о ориентированном графе, то есть графе у которого ребра являются строго направленными. Вновь задача может быть решена 2 способами.
1 способ без графа.
Решение
Вычислим количество путей, ведущих к каждому городу и отобразим его рядом с буквенным обозначением города.
.
Дорог, ведущие к конечному пункту К: Из Е – 1 дорога, из В – 2 дороги, из Г – 4, из Ж – 5
Просуммируем и получим результат: 1+2+4+5 = 12
2 способ с графом.
Идея второго способа заключается в том чтобы построить граф который наглядно демонстрировал всевозможные пути. Перевернем начальный граф и построим на его основе новый граф-дерево
В город К напрямую можно попасть из городов Е,В,Г и Ж.
К
Е
В
Ж
Г

Рассмотри каждую ветку для городов Е,В,Г и Ж
В город Е напрямую можно попасть только из города Б
К
Е
Б

В свою очередь в город Б можно попасть напрямую только из города А
К
Е
Б
А

Таким образом будет найден один из возможных вариантов попадания из города А в город К. В данном случае путь проходит через город Е, такой путь один.
1
К
Е
Б
А

Аналогичные рассуждения проведем и для направление через город В.
К
В

В город В напрямую можно попасть только из города Б и А.
В город Б напрямую можно попасть только из города А.
К
Б
В
А
А

Таким образом будут найдены возможные варианты попадания из города А в город К. В данном направлении путь проходит через город В, таких путей два.
К
Б
В
А
А
2

Для следующей ветки граф будет выглядеть следующим образом:К
Г
В
А
Д

К
Г
В
А
Д
2
А
ВАЖНО заметить что для ветки В, на предыдущем шаге было найдено количество путей!!! Их ровно 2!
Таким образом будут найдены возможны варианты попадания из города А в город К. В данном направлении путь проходит через город Г, таких путей четыре.
А
К
Г
В
Д
2
А
4

Осталось проанализировать последнее направление через город ЖК
Ж

В город Ж напрямую можно попасть только из города Г и Д, для которых количество путей уже подсчитано, получаем:
К
Ж
Г
4
Д
1

Таким образом будут найдены возможны варианты попадания из города А в город К. В данном направлении путь проходит через город Ж, таких путей пять.
К
Ж
Г
4
Д
1
5

Исходя из полученных данных, общее количество путей из города А в город К будут найдены путем сложения , т.е. 1+2+4+5 = 12
ОТВЕТ: 12.
Сравнивая 2 подхода к поиску решения можно выделить плюсы и минусы каждого метода
1 способ без графа 2 способ с графом
+ - + -
Краткая запись решения Подсчет путей осуществляется в уме. Возникает возможность пропустить один из путей. Граф позволяет наглядно ориентироваться в задаче. Перебор путей становится более удобным. Шансов пропустить один из путей существенно сокращается Запись решения задачи увеличивается за счет дополнительного действия – построения графа
Как видно плюсы и минусы при решении этой задачи схожи с предыдущей задачей.
Аналогичные задачи встречаются в ЕГЭ по информатике (Задание 3,15), количество городов-вершин увеличивается , связи-ребра становятся более витиеваты. Поэтому в 11 классе решение 1 способом отходит на второй план, и единственным доступным инструментом для поиска решения задачи становится граф.
Задача 3. Сборник задач для подготовке к ЕГЭ по информатике 2017 г.
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
 
A B C D E F G
A 2 6 B 2 5 3 C 5 1 8
D 6 3 1 9 7 E 9 5
F 7 7
G 8 5 7  
Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.
Решение.
Найдём все варианты маршрутов из A в G и выберем самый короткий.
Из пункта A можно попасть в пункты B и D.
Из пункта B можно попасть в пункты C и D.
Из пункта C можно попасть в пункты D и G.
Из пункта D можно попасть в пункты E и F.
Из пункта E можно попасть в пункт G.
Из пункта F можно попасть в пункт G.
A−B−C−D−E−G. Длина маршрута 22.
A−B−C−D−F−G. Длина маршрута 22.
A−B−C−G. Длина маршрута 15.
A−B−D−E−G. Длина маршрута 19. 
A−B−D−F−G. Длина маршрута 19. 
A−D−F−G. Длина маршрута 20. 
A−D−E−G. Длина маршрута 20. 
A−B−D−С−G. Длина маршрута 14. 
Кратчайший путь равен 14.
Ответ: 14.
Более рационально решение задачи можно получить рисуя граф, для этого нужно повторить рассуждения Задания №3 Демоверсии ОГЭ 2017.
Задача 15. Сборник задач для подготовке к ЕГЭ по информатике 2017 г.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.
Начнем считать количество путей с конца маршрута – с города К. NX — количество различных путей из города А в город X, N — общее число путей.
В "К" можно приехать из И, Ж, или Е, поэтому N = NК = NИ + NЖ + N Е (1)
Аналогично:
NИ = NД;
NЖ = NД + NВ + NЕ;
NЕ = NГ. 
Добавим еще вершины:
NД = NБ + NВ = 1 + NВ = 1 + 3 = 4;
NВ = NБ + NА + NГ = 1 + 1 + 1 = 3;
NГ = NА = 1; 
NБ = NА = 1.
Преобразуем первые вершины с учетом значений вторых: 
NИ = NД = 4;
NЖ = NД + NВ + NЕ = 4 + 3 + 1 = 8;
NЕ = NГ = 1. 
Подставим в формулу (1):
N = NК = 4 + 8 + 1 = 13.
Ответ :13.
Более рационально решение задачи можно получить рисуя граф, для этого нужно повторить рассуждения Задания №11 Демоверсии ОГЭ 2017.
Также в ЕГЭ с помощью графов можно решить следующие задачи:
Задача №4. Табличная модель, поиск родственников.
Задача №5. Задача на условие Фано.
Задача №6. Записать порядок команд в программе преобразования одного числа в другое.
Задача №22. Определить количество программ, которые преобразуют одно число в другое.
Задача №23. Высчитать количество различных наборов логических переменных.
Задача №26. Определить количество камней в начале игры двух игроков.
Заключение.В процессе выполнения работы было рассмотрено применение графов как средства обучения учащихся поиску решения задач , изучена учебная и методическая литература по данной теме, решены некоторые задачи, которые предполагают использование графов, проанализированы некоторые образовательные программы 8 —11 классов. На основании данных, которые были получены можно сделать следующие выводы:
Метод применения графов как средства обучения учащихся поиску решения конкретных задач отличается не только своей математической красотой но и является достаточно эффективным , а иногда и вовсе единственным вариантом решения некоторых задач.
К сожалению, основной школьный курс почти ничего не говорит о существовании истинного математического богатства, именуемого теорией графов.
Кроме того графы применим не только в математике, информатике, но и в физике, экономике и других науках.
Список литературы.Берж К. "Теория графов и ее применение", М., ИЛ, 1962г.
Гарднер М., Оре О. "Графы и их применения", М. "Мир", 1965г.
Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 1969г.
Асельдеров З.М., Донец Г.А. Представление и восстановление графов - К.:Наукова Думка, 1991, 96 стр.
Березина Л. Ю. Графы и их применение: Пособие для учителей. — М.: Просвещение, 1979. — 143 с. с ил. 
Донец Г.А., Шор Н.3. Алгебраический подход к проблеме раскраски плоских графов - К.: Наукова думка, 1982. — 144 с.
Зыков А.А. Основы теории графов. - М.:Наука, 1987, 384 с.
Калмыков Г. И. Древесная классификация помеченных графов. - М.: ФИЗМАТЛИТ, 2003. - 192 с.
Камерон П., ван Линт Дж. Теория графов, теория кодирования и блок-схемы - М.:Наука, 1980, 140 стр.
Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с анг. - М.:Мир, 1978, 432 с.
Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств - М.:Наука, 1974, 304 с.
Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.
Мельников О.И. Занимательные задачи по теории графов. - Минск: ТетраСистемс, 2001. - 144 с. 
Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с. 
Татт У. Теория графов. Пер. с англ. - М.:Мир, 1988, 424 с.
Уилсон Р. Введение в теорию графов. Пер. с анг. 1977. 208 с.
Фляйшнер Г. Эйлеровы графы и смежные вопросы. Пер. с англ. - М.:Мир, 2002, 176 с.
Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
http://www.problems.ru.
Приложения к исследовательской работе по теме ««ГРАФЫ КАК СРЕДСТВО ОБУЧЕНИЯ УЧАЩИХСЯ ПОИСКУ РЕШЕНИЯ ЗАДАЧ». ПРИЛОЖЕНИЕ №1.


ПРИЛОЖЕНИЕ №2.Теорема.  Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство
В - Р + Г = 1, (*)
где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).
Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).

Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем
В - (Р + 1) + (Г+1) = В – Р + Г.
Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) (рис. 2, б). Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:
а) для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;
б) для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.
В обоих случаях равенство (*) не изменится. Например, в первом случае после  удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:
(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.
Самостоятельно рассмотрите второй случай.
Таким образом, удаление одного треугольника не меняет равенства (*). Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно, B - Р + Г= 1. Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*).
Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.
Приступим теперь к решению задачи о трех домиках и трех колодцах.
Решение. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.
Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1. Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5∙4)/2 = 10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.
ПРИЛОЖЕНИЕ №3Как уже было сказано, графы имеют очень широкое применение: с их помощью выбирают наиболее выгодное расположение зданий, графами представлены схемы метро. Далее представлены некоторые примеры применения графов.
1. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов». Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.
2. Генеалогическое древо.
3. Блок-схема программы
Графами являются блок – схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.
4.  Схема цепей дежурного освещения
5. Схемы авиалиний
6. Участок московского Метрополитена.
7. Социограммы
Социограммы (в психологии при исследовании межличностных отношений в группах).
8. Схема железных дорог
Вершины – железнодорожные станции, а рёбра – железнодорожные пути.
9. Созвездия
10. Химия. Теория графов позволяет точно определить и пояснить некоторые основные понятия химии: структуру, конфигурацию, конформацию, квантовомеханическое и статистико-механическое взаимодействия молекул, определять число теоретически возможных изомеров органических соединений, позволяет анализировать некоторые химические превращения, описывать химические реакции, определять некоторые свойства молекул.
Молекулярный граф — связный неориентированный граф, находящийся во взаимно-однозначном соответствии со структурной формулой химического соединения таким образом, что вершинам графа соответствуют атомы молекулы, а рёбрам графа — химические связи между этими атомам.
11. Математика.  Немало поводов для появления графов и в математике. Наиболее очевидный пример – любой многогранник в трёхмерном пространстве.
Например, вершины и рёбра куба можно рассматривать как вершины и рёбра графа. При этом мы отвлекаемся от того, как расположены элементы куба в пространстве, оставляя лишь информацию о том, какие вершины соединены рёбрами.

12. Физика.  Одной из наиболее сложных и утомительных задач для радиолюбителей считается конструирование печатных схем.
Печатная схема - это пластинка из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов.
ПРИЛОЖЕНИЕ №4.21590-3810Эйлер Леонард (1707—1783), математик, физик, механик, астроном.
Родился 15 апреля 1707 г. в Базеле (Швейцария). Окончил местную гимназию, слушал в Базельском университете лекции И. Бернулли. В 1723 г. получил степень магистра. В 1726 г. по приглашению Петербургской академии наук приехал в Россию и был назначен адъюнктом по математике.
В 1730 г. занял кафедру физики, а в 1733 г. стал академиком. За 15 лет своего пребывания в России Эйлер успел написать первый в мире учебник теоретической механики, а также курс математической навигации и многие другие труды.
В 1741 г. он принял предложение прусского короля Фридриха II и переехал в Берлин. Но и в это время учёный не порвал связи с Петербургом. В 1746 г. вышло три тома статей Эйлера, посвящённых баллистике.
В 1749 г. он выпустил двухтомный труд, впервые излагающий вопросы навигации в математической форме. Многочисленные открытия, сделанные Эйлером в области математического анализа, были позже объединены в книге «Введение в анализ бесконечно малых величин» (1748 г.).
Вслед за «Введением» вышел трактат в четырёх томах. 1-й том, посвящённый дифференциальному исчислению, вышел в Берлине (1755 г.), а остальные, посвящённые интегральному исчислению, — в Петербурге (1768—1770 гг.).
В последнем, 4-м томе рассматривается вариационное исчисление, созданное Эйлером и Ж. Лагранжем. Одновременно Эйлер исследовал вопрос о прохождении света через различные среды и связанный с этим эффект хроматизма.
В 1747 г. он предложил сложный объектив.
В 1766 г. Эйлер вернулся в Россию. Работу «Элементы алгебры», увидевшую свет в 1768 г., учёный вынужден был диктовать, так как к этому времени он ослеп. Тогда же печатались три тома интегрального исчисления, два тома элементов алгебры, мемуары («Вычисление Кометы 1769», «Вычисление затмения Солнца», «Новая теория Луны», «Навигация» и др.).
В 1775 г. Парижская академия наук в обход статута и с согласия французского правительства определила Эйлера своим девятым (должно быть только восемь) «присоединённым членом».
Эйлеру принадлежит более 865 исследований по самым разнообразным и труднейшим вопросам. Он оказал большое и плодотворное влияние на развитие математического просвещения в России в XVIII в. Петербургская математическая школа, в которую входи ли академики С. К. Котельников, С. Я Румовский, Н. И. Фусс, М. Е. Головин и другие учёные, под руководством Эйлера провела огромную просветительную работу, создала обширную и замечательную для своего времени учебную литературу, выполнила ряд интересных исследований.
Скончался Эйлер 18 сентября 1783 г. в Петербурге.
ПРИЛОЖЕНИЕ №5.Решение задач с помощью графов:
Задача 1.

Решение:
Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 2.
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Решение:
Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Решение:

Задача 4.

Задача 5.

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

Теперь видно, что долететь от Земли до Марса нельзя.
Задача 7.
Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.   а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).   б) Укажите все случаи, когда связность нарушается при отмене n рейсов.
Решение
  а) Предположим, что после отмены некоторых рейсов "связность" нарушилась. Рассмотрим некоторый город A, множество M всех городов, в которые можно проехать из A (возможно, с пересадками) и его дополнение N. Ясно, что между городами из M и N авиалиний нет. При этом в одном из этих множеств не более n городов; пусть их k.   Первоначально каждый из этих городов был связан авиалиниями не менее чем с n городами, поэтому по крайней мере n + 1 – k  рейсов соединяли его с городами "чужого множества" и, следовательно, были отменены. Значит, всего было отменено не меньше чем  k(n + 1 – k)  рейсов. Но k(n + 1 – k) > n – 1  при  k = 1, 2, ..., n .  Следовательно, если отменить  n – 1  рейс, то "связность" не нарушается.
  б) Заметим, что  k(n + 1 – k) = n  лишь при  k = 1  и  k = n.  Если  k = 1,  то это значит, что некоторый город был связан рейсами ровно с n городами и все эти рейсы были отменены. Если  k = n,  то это значит, что некоторые n городов A1, A2, ..., An попарно соединены авиалиниями, оставшиеся n городов B1, B2, ..., Bn тоже попарно соединены авиалиниями и есть еще n рейсов, соединяющих города A1 и B1, A2 и B2, ..., An и Bn. На рисунке см. схемы авиалиний для  n = 2  и  n = 3.

Задача 8.
Можно ли нарисовать эту картинку (см. рис.), не отрывая карандаша от бумаги и проходя по каждой линии по одному разу?

Решение
Пронумеруем три квадрата, из которых состоит фигура. Начнём рисовать первый квадрат с любой его точки до тех пор, пока не дойдём до точки пересечения со вторым квадратом. Затем прерываем обход первого квадрата и рисуем второй до тех пор, пока не дойдём до его точки пересечения с третьим. Затем рисуем полностью третий квадрат, окончив дорисовываем второй, затем – первый. Каждый раз мы будем оканчивать рисовать квадрат в той же точке, в которой начинали, то есть в точке пересечения с предыдущим квадратом.
Ответ
Можно.
Задача 9.
Доска имеет форму креста, который получается, если из квадратной доски 4×4 выкинуть угловые клетки. Можно ли обойти её ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?
Решение
Занумеруем поля доски (рис. слева) и нарисуем граф (рис. в центре), где вершины соответствуют полям, а ребро проводится, если соответствующие поля отстоят на ход коня. На графе легко построить требуемый обход (жирная линия). На рис. справа поля занумерованы уже в порядке обхода.

Ответ
Можно.
Замечания
Приведённый маршрут обхода, конечно, не единственный.
Задача 10.
Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.

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

  Оценка. Всего в Старом городе 36 перекрёстков. Всякий раз, когда турист проходит очередную улицу, он попадает на новый перекрёсток. Таким образом, больше 35 улиц турист пройти не сможет (начальный перекрёсток A не считается). Покажем, что посетить 35 перекрёстков (и, следовательно, пройти 35 улиц) турист тоже не сможет. Для этого раскрасим перекрёстки в чёрный и белый цвета в шахматном порядке (рис. справа). Всякий раз, проходя улицу, турист попадает на перекрёсток другого цвета. И отель, и вокзал расположены на белых перекрёстках. Поэтому любой маршрут содержит чётное число улиц, а число 35 нечётно.