Научное общество учащихся

«Поиск»

40 Открытая областная научная конференция учащихся.

Секция математики .

Научная работа по теме:

«Графы» в моей родословной

Выполнила: Лобурец Виктория

ученица 7 класса

МОУ «Куломзинская СОШ»

Руководитель:

Лысенко Ольга Григорьевна

учитель математики

МОУ «Куломзинская СОШ»

Омск - 2008г.

1. 
   Актуальность и новизна
2. 
   Цель и задачи

II. ОСНОВНАЯ ЧАСТЬ
1.Понятие о графах

2.Свойства графов

3.Применение графов
III.Практическая часть
IV.Заключение
V.Литература

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

С О Д Е Р Ж А Н И Е

Введение………………………………………………………………..…….3

П.1.1. Актуальность и новизна……………………………………………..4

П.1.2.Цели и задачи…………………………………………………………4

Глава I.Теоретическаячасть …...………………………………….……….5

П.2.1.Понятие о графах……………………………………………………..5

Глава II. Практическая часть……………………………………………..11

П.2.1. «Графы» в моей родословной……………………………………..11

П.2.2.Решение логических задач методом графа………………………..11

Заключение…..……………………………………………………………...17

Литература……..……………………………………………………………..18

Приложения…………………………………………………………………..19

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

Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топографии и комбинаторики, с которыми ее связывают самые тесные узы родства. Наиболее раннее упоминание о графах встречается в работе Л. Эйлера (1736г). В середине XIX века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. Окончательно как математическая дисциплина теория графов оформилась в 1936г. после выхода монографии Д. Кёнига «Теория конечных и бесконечных графов».

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

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

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

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

Объектом исследования является процесс обучения учащихся методу «графа».

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

Исходя из гипотезы выдвинуты следующие цели и задачи исследования.

2. Цель и задачи.
Цель : использовать метод графа для решения логических задач, тем самым способствовать развитию логического мышления, рассмотреть решение задач с использованием понятия «Граф», проверить выполнение «Графов» на родословных.

Задачи:

1)Изучить научно- популярную литературу по данному вопросу.

2)Исследовать выполнение «Графов» для выяснения родственных отношений.

3)Проанализировать результаты проведенных экспериментов.

4)Изучение метода «графа», как метода решения логических задач.

Гл.I. Теоретическая часть

П.2.1. Понятие о графах

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.

Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

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

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

Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 4). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом. Они жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. На рисунке 6 изображена очередная попытка проложить такие тропы.

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

Л.С.Понтрягин независимо друг от друга доказали, что если граф не является плоским, то в нем «сидит» хотя бы один из графов, изображенных на рисунках 4 и 5, то есть «полный пятивершинник» или граф «домики – колодцы».

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

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

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

рис.7.

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 7 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф (внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: в А, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 ×3× 2× 1 = 24 способа.

Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях. Заметим, что граф на рис. 8 тоже можно сделать направленным, указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю. Решение: Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б - в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0), если наполним водой большую кастрюлю, или (5, 0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Подобным образом можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов», где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки. Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3×3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин. В терминах графов легко формулируется и решается задача о назначении на должности. А именно: если имеется несколько вакантных должностей и группа лиц, желающих их занять, причем каждый из претендентов имеет квалификацию для нескольких должностей, то при каких условиях каждый из претендентов сможет получить работу по одной из своих специальностей?

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

Гл.II. Практическая часть.
П.2.1. «Графы» в моей родословной.
Методы работы:

Сравнение и анализ результатов эксперимента.

Методика работы:

Для проведения исследований были выбраны:

А) Родословная моей семьи, архивы данных, свидетельства о рождении.

Б) Родословная князей Голицыных, архивы данных.

Я провела исследование, результаты исследования поместила в схемы и проанализировала их.

Методика 1.
Цель: проверить выполнение ’’Графов” на своей родословной.

Результаты: схема 1(см. приложение 1).

Методика 2.
Цель: проверить выполнение ’’Графов’’ на родословной князей Голицыных.

Результат: схема 2 (см. приложение 2).

Вывод: я заметила, что родословная – типичный граф.
П. 2.2. Решение логических задач методом графа
В течение всех лет обучения в школе мы много решаем разнообразных задач, в том числе и логических: задачи занимательного характера, головоломки, анаграммы, ребусы и т.п. Чтобы успешно решать задачи такого вида, надо уметь выделять их общие признаки, подмечать закономерности, выдвигать гипотезы, проверять их, строить цепочки рассуждений, делать выводы. Логические задачи от обычных отличаются тем, что не требуют вычислений, а решаются с помощью рассуждений. Можно сказать, что логическая задача – это особая информация, которую не только нужно обработать в соответствии с заданным условием, но и хочется это сделать. Логика помогает усваивать знания осознанно, с пониманием, т.е. не формально; создаёт возможность лучшего взаимопонимания. Логика – это искусство рассуждать, умение делать правильные выводы. Это не всегда легко, потому, что очень часто необходимая информация «замаскирована», представлена неявно, и надо уметь её извлечь. Как известно, видение рождает мышление. Возникает проблема: как установить логические связи между разрозненными фактами и как оформить в виде единой целой. Видеть ход доказательства и решения задач позволяет метод граф - схем, который делает доказательство более наглядным и позволяет кратко и точно изложить доказательства теорем и решения задач.

Пример 1.1 . Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?

Решение. Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G1 (рис. 1).

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

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

Решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому, вначале должен возникнуть граф, изображенный на рисунке 2.

Рис.2

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

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

Рис.3
Далее остается соединить сплошной линией точку Ч и точку б , так как точка Ч соединена с точкой бр штриховой линией, а точка р уже «занята» (рис. 4).

Рис. 4

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров - рыжий, Чернов - белокурый, Рыжов – брюнет.

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

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

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Решение. Условию задачи соответствует граф, изображенный на рисунке 5.

Рис. 5

Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.6).

Рис. 6

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечивают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

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

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

Для примера рассмотрим такую задачу:

Имеются два сосуда вместимостью 3л и 5л. Как с помощью этих сосудов налить из водопроводного крана 4л воды?

Начнем с конца. Как в результате может получиться 4л? – Из 5-литрового сосуда отлить 1л. Как это сделать? – Надо в 3-литровом сосуде иметь ровно 2л. Как их получить? – Из 5-литрового сосуда отлить 3 литра. Теперь запишем решение задачи сначала в виде таблицы.

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

Из чисел 3 и 5 можно составить выражения, имеющие значение 4:

5-3+5-3=4 и 3+3-5+3=4

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

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

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

Например, требуется решить задачу: «Однажды встретились пятеро друзей. Каждый здороваясь, пожал каждому руку. Сколько рукопожатий было сделано».

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

Следующая задача :

«Сколько двухзначных чисел можно составить, используя цифры 1,2,3,4?».

Решение. Число 12: надо показать, что начинает с цифры 1, а оканчивается цифрой 2. петля появляется при обозначении, например, числа 11: стрелка должна начинаться и заканчиваться на одной и той же цифре. Открыв для себя первых задачах эти условные обозначения (точки, лини, стрелки, петли), я стала применять их при решении различных задач, составляя графы того или иного вида (рис 2).

ответ:16 чисел.

Приведу некоторые примеры:

1.В финал турнира по шашкам вышли два российских игрока, два немецких и два американских. Сколько партий будет в финале, если каждый играет с каждым по одному разу и представители одной страны между собой не играют? (рис.3.).

н

Н



В финале будет сыграно 4×6 = 24партии.
2.В вазе лежали конфеты четырех сортов. Каждый ребенок взял две конфеты. И у всех оказались отличающие наборы конфет. Сколько могло быть детей? (граф на рис.4).

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

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

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

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

ЗАКЛЮЧЕНИЕ
Выполняя эту работу, я изучила один из интереснейших вопросов теории графов, я рассмотрела математические графы, области их применения, решила несколько задач с помощью графов. Научилась использовать «графы» для выяснения родственных отношений. Изучила метод «графов», как один из методов решения логических задач.

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

В дальнейшем я собираюсь продолжить изучение теории графов, потому что этот раздел математики показался мне интересным и полезным. Кроме того, работая над исследовательской работой, я освоила работу на компьютере в текстовом редакторе Word и Рower Point. Я считаю, что задачи исследовательской работы выполнила.

Литература.

1. 
   Березина Л.Ю. Графы и их применение. – М., 1979.
2. 
   Виленкин Н.Я. Математика. – М.: Русское слово, 1997.
3. 
   Гарднер М. «Математические досуги» М.: Мир,1972
4. 
   Гнеденко Б.В. Курс теории вероятностей. - М.: УРСС, 2005.
5. 
   Коннова Л.П. Знакомтесь, графы. – Самара, 2001.
6. 
   Лыкова И.А. Логические задачки –М.: Карапуз, 2000.
7. 
   Савин А.В. Энциклопедический словарь юного математика. 2-е изд., - М.: Педагогика, 1989
8. 
   Шадринова В.Д. Познавательные процессы и способности в обучении – М.: Просвещение, 1980
9. 
   Чистяков В. П. Курс теории вероятностей. М., Просвещение, 1982.

Приложения.
Приложение 1.
Лобурец Виктория Владимировна 1994 гр.

Лобурец В. Н

1962
.

Орловская Л. В.

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

ВВЕДЕНИЕ

«В математике следует помнить не формулы, а процесс мышления…»

Е. И. Игнатьев

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

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

Цель определила следующие задачи:

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

изучить основные понятия теории графов и основные характеристики графов;

показать практическое применение теории графов в различных областях знаний;

рассмотреть способы решения задач с помощью графов и составить собственные задачи.

Объект исследования: сфера деятельности человека на предмет применения метода графов.

Предмет исследования: раздел математики «Теория графов».

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

Методы исследовательской работы:

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

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

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

ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ

1. Теория графов. Основные понятия

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

В математике определение графа дается так:

Термин «граф» в математике определяется следующим образом:

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

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

Рис. 1 Примеры графов

Число ребер, которое принадлежит одной вершине, называется степенью вершины графа . Если степень вершины нечетное число, вершина называется - нечетной . Если степень вершины число четное, то и вершина называется четной .

Рис. 2 Вершина графа

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

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

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

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

Если граф связанный, но не содержит циклов, то такой граф называетсядеревом .

1. Характеристики графов

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

Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.

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

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

Раскраска графов и применение.

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

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

«Проблема четырех красок» вызывала все больший интерес, но так и не была решена, даже выдающимися математиками. В 1890 году английским математиком Перси Хивудом было доказано, что для раскрашивания любой карты будет достаточно пяти красок. А только 1968 году смогли доказать, что для раскрашивания карты, на которой изображено меньше сорока стран, будет достаточно 4 цветов.

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Можно представить задачу о четырех красках несколько иначе.

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

Эйлеровы и Гамильтоновы графы

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

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

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

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

При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.

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

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

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

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

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

ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ

2.1. Этапы проведения исследования

Для проверки гипотезы исследование включало три этапа (таблица 1):

Этапы исследования

Таблица 1.

		Используемые методы
Теоретическое исследование проблемы	Изучить и проанализировать познавательную и научную литературу.	 самостоятельное размышление;  изучение информационных источников;  поиск необходимой литературы.
Практическое исследование проблемы	Рассмотреть и проанализировать области практического применения графов;	 наблюдение;  анализ;  сравнение;  анкетирование.
3 этап. Практическое использование результатов	Обобщить изученную информацию;	 систематизация;  отчет (устный, письменный, с демонстрацией материалов)	сентябрь 2017 г.

2.2. Области практического применения графов

Графы и информация

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

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

CnH 2n+2

Все атомы углеводорода 4-хвалентны, все атомы водорода 1-валентны. Структурные формулы простейших углеводородов показаны на рисунке.

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

Графы и биология

Процесс размножения бактерий - это одна из разновидностей ветвящихся процессов, встречающихся в биологической теории. Пусть каждая бактерия по истечению определенного времени или погибает, или делится на две. Следовательно, для одной бактерии мы получим двоичное дерево размножения ее потомства. Вопрос задачи заключается в следующем, какое количество случаев содержит k потомков в n-м поколение одной бактерии? Данное соотношение в биологии носит название процесс Гальтона-Ватсона, которое обозначает необходимое количество нужных случаев.

Графы и физика

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

Итак, все выше сказанное подтверждает практическую ценность графов.

Математика интернета

Интернет - всемирная система объединенных компьютерных сетей для хранения и передачи информации.

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

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

Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин.

Несмотря на разреженность, интернет очень тесен. От одного сайта до другого по ссылкам, можно перейти за 5 - 6 кликов (знаменитая теория «шести рукопожатий»).

Как мы знаем, степень графа - это число ребер, которым принадлежит вершина. Степени вершин веб-графа распределены по определенному закону: доля сайтов (вершин) с большим количеством ссылок (ребер) мала, а сайтов с малым количеством ссылок - велика. Математически это можно записать так:

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

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

Интернет как целое устойчив к случайным атакам на сайты.

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

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

Эта задача пока полностью не решена! Решение этой задачи - построения качественной модели интернета - позволит разработать новые инструменты для улучшения поиска информации, выявления спама, распространения информации.

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

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

г. Мурманск с помощью графа.

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

В качестве примера рассмотрим типичный случай прибытия в Мурманск из аэропорта в первый раз. Планируется посетить следующие достопримечательности:

1. Морской православный храм Спас-на-водах;

2. Свято-Никольский собор;

3. Океанариум;

4. Памятник коту Семену;

5. Атомный ледокол Ленин;

6. Парк Огни Мурманска;

7. Парк Долина Уюта;

8. Кольский мост;

9. Музей истории Мурманского морского пароходства;

10. Площадь Пяти углов;

11. Морской торговый порт

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

Достопримечательности на карте (слева) и полученный граф (справа) показаны на соответствующем рисунке ПРИЛОЖЕНИЯ №1. Таким образом, новоприбывший вначале проедет около Кольского моста(и, при желании может пересечь его туда - обратно); затем отдохнет в Парке Огни Мурманска и Долине Уюта и отправится дальше. В итоге оптимальный маршрут составит:

С помощью графа можно также визуализировать схему проведения соцопросов. Примеры представлены в ПРИЛОЖЕНИИ №2. В зависимости от данных ответов опрашиваемому задают разные вопросы. Например, если в социологическом опросе №1 опрашиваемый считает математику важнейшей из наук, у него спросят, уверенно ли он чувствует себя на уроках физики; если же он считает иначе, второй вопрос будет касаться востребованности гуманитарных наук. Вершинами такого графа являются вопросы, а ребрами - варианты ответов.

2.3. Применение теории графов при решении задач

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

Задача №1.

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

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

Ответ: 10 рукопожатий (каждая линия означает одно рукопожатие).

Задача №2.

У моей бабушке в деревне, возле дома растут 8 деревьев: тополь, дуб, клен, яблоня, лиственница, береза, рябина и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. В какой последовательности расположатся деревья по высоте от самого высокого к самому низкому.

Решение:

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

Ответ: клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача №3.

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

Ответ: 6 способов

Задача №4.

Между населенными пунктами A, B, C, D, E построены дороги. Нужно определить длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, длина которых указана на рисунке.

Задача №5.

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

Решение: Для решения задачи применим графы

Баскетбол Максим

Футбол Кирилл

Хоккей Вова

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

Задача №6.

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

1. Преподаватель ОБЖ согласен дать только последний урок;

2. Преподаватель географии может дать либо второй, либо третий урок;

3. Математик готов дать либо только первый, либо только второй урок;

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

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

Решение: Эту задачу можно решить перебирая все возможные варианты, но проще, если начертить граф.

1. 1) физика 2. 1) математика 3. 1) математика

2) математика 2) физика 2) география

3) география 3) география 3) физика

4) ОБЖ 4) ОБЖ 4) ОБЖ

Заключение

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

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

Гарднер М. «Математические досуги», М. «Мир», 1972

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

Горбачев А. «Сборник олимпиадных задач» - М. МЦНМО, 2005

Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664

Касаткин В. Н. «Необычные задачи математики», Киев, «Радяньска школа», 1987

Математическая составляющая / Редакторы-составители Н.Н. Андреев, С.П. Коновалов, Н.М. Панюшкин. - М.: Фонд «Математические этюды» 2015 г. - 151 с.

Мельников О. И. «Занимательные задачи по теории графов», Мн. «ТетраСистемс»,2001

Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. «Старинные занимательные задачи», М. «Наука», 1988

Оре О. «Графы и их применения», М. «Мир», 1965

Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.

ПРИЛОЖЕНИЕ №1

Составление оптимального маршрута посещения главных достопримечательностей

г. Мурманск с помощью графа.

Оптимальный маршрут составит:

8. Кольский мост6. Парк Огни Мурманска7. Парк Долина Уюта2. Свято-Никольский собор10. Площадь Пяти углов5. Атомный ледокол Ленин9. Музей истории Мурманского морского пароходства11. Морской торговый порт1. Морской православный храм Спас-на-водах4. Памятник коту Семену3. Океанариум.

ПУТЕВОДИТЕЛЬ ПО ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ МУРМАНСКА

ПРИЛОЖЕНИЕ №2

Социологические опросы № 1, 2

Содержание:

I. Введение……………………………………………………………………2

II. Основная часть.

1.История возникновения теории графов…………………………………….4

2.Основные понятия теории графов…………………………………………..5

3.Некоторые задачи теории графов…………………………………………...6

3.1 Задачи о вычерчивании фигур одним росчерком………………………..8

3.2 Задачи с лабиринтами……………………………………………………..10

3.3 Логические задачи…………………………………………………………12

4.Применение теории графов в различных сферах деятельности…………..15

4.1.Графы и история……………………………………………………………17

4.2.Графы и химия……………………………………………………………...18

4.3. Графы и физика…………………………………………………………….19

III . Заключение………………………………………………………………..20

IV . Список литературы………………………………………………………21

Приложение 1………………………………………………………………….22

Приложение 2………………………………………………………………….25

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

I Введение

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

В этом году я был участником дистанционной олимпиады по математике. В ней была предложена такая задача:

«Почтальон Печкин разнёс почту во все дома деревни, после чего зашёл к дяде Фёдору выпить молока. На рисунке показаны все тропинки, которые проходил Печкин, причём как оказалось, ни одной из них он не проходил дважды. Каким маршрутом шёл почтальон Печкин? В каком доме живёт дядя Фёдор?»

Разбирая решение этой задачи, я задался вопросом: «Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?»

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

Цель:

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

Задачи:

Изучить элементы теории графов.

Разобрать решение различных видов задач.

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

Методы исследования:

Поиск и анализ информации в литературе.

Поиск и изучение информации в интернет – ресурсах.

Моделирование.

II Основная часть

1. История возникновения теории графов.

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах (Приложение 1.) .

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

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила в 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.

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

2. Основные понятия теории графов.

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

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

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

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

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

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

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке 5: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

рис.5

3. Некоторые задачи теории графов.

Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.

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

рис.6 (эйлеровы графы)

Закономерность 1 .

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

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

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

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

Алгоритм решения

Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах:

преобразовать рисунок в граф (определить его вершины и рёбра);

определить степень каждой вершины;

сделать выводы:

а) заданный обход возможен, если

Все вершины чётные (его можно начать с любой вершины);

Две вершины нечётные (его нужно начать с одной из нечётных вершин);

б) заданный обход невозможен, если нечётных вершин больше двух;

указать начало и конец пути.

Я, изучив эти выводы, решил проверить их на примерах задач из раздела теории графов.

3.1. Решение задач о вычерчивании фигур одним росчерком

Задача №1 (О кенигсбергских мостах).

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

Решение.

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

Задача №2.

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

Решение:

Можно, т. к. только 2 нечетные вершины.

Нельзя, т. к. 4 нечетные вершины.

Задача №3.

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

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Задача №4. (Муха в банке).

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение.

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

Задача №5. (Путь Печкина)

Решение. Нечётных вершин в условии задачи две – почта и дом, поэтому начинаться и заканчиваться маршрут может только в этих узлах. Почтальон Печкин начинает разнос писем с почты, поэтому его маршрут может заканчиваться в доме 5, там и живёт дядя Фёдор. Например, маршрут может быть таким: почта-1-3-2-1-7-почта-3-4-5-7-6-5.

1. 1. Задачи с лабиринтами

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

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

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

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

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

Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

Второй метод – МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

Рассмотрим задачу общего вида:

М
ожно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:

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

3.3 Логические задачи

Задача №1.

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение:

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

Задача №2.

В
деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

Решение.

Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70: 2= 35. Таким образом, между домами проходит 35 тропинок.

Ответ. 35 тропинок

Задача №3.

В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, электрик-младший из друзей.

По вечерам Андрей и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.

Решение.

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

В С Н А

Ш С Т Э

Задача №4.

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

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

Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.

Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром.

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

Решение.

Иванов Петренко Сидорчук Гришин Капустин

маляр мельник плотник почтальон парикмахер

4.Применение теории графов в различных сферах деятельности.

Ч

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

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

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

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

Инженер чертит схемы электрических цепей.

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

Историк прослеживает родословные связи по генеалогическому дереву.

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

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

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

4.1.Графы и история .

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

Генеалогическое дерево А.С. Пушкина.

Моё генеалогическое дерево

4.1.Графы и химия .

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

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

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

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

М
олекулярные графы и деревья: а, б - мультиграфы этилена и формальдегида; в-молекулы изомеров пентана.

4.3.Графы и физика

Е

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

Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок.

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

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

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

III Заключение.

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

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

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

IV . Литература.

1. Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

2. Перельман Я.И. Одним росчерком. – Ленинград, 1940

3. Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

4. Игнатьев Е. И. Математическая смекалка. - М.: «Омега», 1994г.

5. Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.

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

Леонард Эйлер и мосты Кёнигсберга

Леонард Эйлер родился в швейцарском городе Базеле, где в 15 лет окончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли и подружился с его сыновьями Даниилом и Николаем, которые были приглашены для работы в только что созданную Петербургскую академию наук. Через год по их рекомендации туда же был приглашен и двадцатилетний Эйлер. Этот выбор оказался одним из самых удачных для России. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения. Даже историю возникновения теории графов можно проследить по переписке великого ученого.

Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:

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

В своём письме к Маринони Эйлер подробно описал ход своих рассуждений:

"Кенигсбергские же мосты расположены так, что их можно представить на рисунке, где A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

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

Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,

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

Ход решения задачи будем представлять в виде графа , где вершины – острова и берега, а ребра – мосты.

"Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста".

То есть нам нужно определить степень каждой вершины (количество рёбер, сходящихся в вершине) и узнать, какие вершины четные , а какие нечетные . Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

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

Приложение 2

Разные задачи на вычерчивание одним росчерком

Приложение 3

Профессия логист

О
писание профессии:

Это специалист, который координирует движение товаров на пути от производства до точек реализации.

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

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

Цепочка может выглядеть, например, так: закупка товаров у иностранного поставщика - их страхование - перевозка - растаможивание (прохождение таможенного контроля, уплата пошлин) - складирование - упаковка и/или снабжение русскоязычными этикетками и документацией - распределение по оптовым торговым базам - продажа в розничной сети.

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

Например, завезли слишком много какого-то товара - он попусту загромождает складские помещения и может прийти в негодность. А какой-нибудь другой товар, который следует привезти к вполне определенному сроку (например, елки к Новому году или цветы к 8 Марта), из-за неправильно оформленных сопроводительных документов застрянет на таможенном складе и поступит в продажу слишком поздно, когда уже окажется никому не нужен.

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

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

страница 1

Научное общество учащихся

«Поиск»

Секция информатика

Научная работа по теме:

«Его величество Граф»

Выполнила : Сапожникова Светлана,

ученица 7 класса

МОУ «Сергеевская СОШ»

Оконешниковского МР

Руководитель : Гармс Елена Анатольевна,

учитель информатики

МОУ «Сергеевская СОШ»

Омск - 2010
Содержание

Научное общество учащихся 1

«Поиск» 1

Научная работа по теме: 1

Введение 3

ТЕОРИЯ ГРАФОВ 4

1.2.Эйлеровы графы 7

1.3. Задача о мостах, Леонард Эйлер и теория графов 8

2.1. Решение задач с помощью графов «Один день из жизни Графа» 11

Библиографический список 16

Введение

Актуальность исследования . Вот уже второй год я интересуюсь шахматами и занимаюсь в школе в шахматном кружке «Шах и Мат». На одном из занятий в качестве домашнего задания была предложена задача, в которой нужно было просчитать перестановку фигур за меньшее число ходов. Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась только на уроке истории при изучении темы дворянство.

Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми, всевозможные транспортные схемы и многое-многое другое. Очень важное, для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Я решила разобраться, какую роль в обычной жизни играют графы.

Объект исследования : понятие граф
Предмет исследования : степень распространенности применения графов
Цель исследования : Исследовать роль графов в нашей жизни.
Задачи исследования :

1.познакомиться с историей возникновения графов;

2.познакомиться с основными понятиями графа, видами, элементами;

3.научиться решать задачи с помощью графов;

4.составить своё родословное дерево.
Методы исследования : частично - поисковый, аналитический.

Глава 1

ТЕОРИЯ ГРАФОВ

1. 
   Понятие графа

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

В математике определение графа дается так: «графом называется конечное множество точек, некоторые из которых соединены линиями».

В информатике под графом понимают средство для наглядного представления состава и структуры системы.

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

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

Граф, в котором все линии направленные, называется ориентированным графом.

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

хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг .

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

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

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

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

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

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

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

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

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

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

Доказательство :

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

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

ТЕОРЕМА.

Число нечетных вершин любого графа четно.

Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как

K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

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

1.2.Эйлеровы графы

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

Такими графы названы в честь учёного Леонарда Эйлера.

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

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

Закономерность 5.

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

Закономерность 6.

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

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

рис.6 (эйлеровы графы)

Связные графы.

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

Граф называется несвязным, если это условие не выполняется.

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

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

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

1.3. Задача о мостах, Леонард Эйлер и теория графов

Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

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

Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты « вытянул» в линии, как показано на рисунке 9 а, б.

Рисунок 9

На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.

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

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

Давайте четко сформулируем поставленную задачу. При каком условии можно обойти все ребра графа, пройдя каждое ровно один раз? Решение оказалось очень простым. Сосчитаем, сколько ребер выходит из каждой вершины. Одни из этих чисел будут четными, а другие - нечетными. Будем и сами вершины называть четными, если из них выходит четное число ребер, и нечетными в противном случае. Как мы уже знаем: количество ребер, выходящих из данной вершины, называется степенью вершины. Вершина графа, имеющая нечетную степень, называется нечетной, а четную степень – четной.
Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:

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

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

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Циклом называется путь, в котором совпадают начало с концом.

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.10а). В графе на рис.10б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.12)

рис.10 а;б
Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2.

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

рис.12 (кружком обведены висячие вершины)
Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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

Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.

ЛЕММА (о висячей вершине)

В каждом дереве есть висячая вершина.

Доказательство:

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

Что можно описать с помощью графов? Обозначим области применения данного описания.

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

Например:

Схему линий метрополитена можно рассматривать как граф;

В химии граф можно рассматривать как способ отображения структуры молекулы;

В медицине – вопрос о группе крови;

В виде графа можно представить генеалогическое дерево;

Системы классификаций в науке.

Иерархическую структуру административного управления предприятия, ВУЗа и т.д.

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

Глава 2

2.1. Решение задач с помощью графов «Один день из жизни Графа»

Рассмотрим решение задач с помощью графов из школьной жизни.

Задача 1. Утром учащихся нашей школы привезли с окрестных деревень Волчино, Ольховка, Кочковатое, Павловка на занятия. На рисунке изображен граф, представляющий информацию о дорогах между четырьмя деревнями: Волчино, Ольховка, Кочковатое, Павловка. Веса вершин – названия деревень, веса линий – длина дорог в километрах.

Маршрут движения автобуса – это граф.

Задача 2. При встрече каждый из моих одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо; 3)пятеро?

Решение.

Задача решается с помощью полных графов.

1)Встретились трое:

Количество рукопожатий равно количеству рёбер, т.е.3.

2)Встретились четверо:

Количество рёбер 6; возможно 6 рукопожатий.

3)Встретились пятеро:

В графе 10 рёбер; возможно 10 рукопожатий.

Ответ: 1)3; 2)6; 3)10.
По расписанию у нас шесть уроков: геометрия, история, информатика, география, русский язык и физика.
Задача 3. На уроке геометрии было предложено построить граф классификации геометрических объектов. Это оказалось легко сделать с помощью понятия граф.


Задача 4 . А на уроке истории нужно было составить родословное дерево. Родословное дерево. Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.

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

Задача 5 . На уроке информатике мы познакомились с новой темой «Алгоритмы». И к моему удивлению, оказалось, что блок схема – ориентированный граф Блок – схема алгоритма представляет собой граф процесса управления некоторым исполнителем. Блоки – вершины этого графа- обозначают отдельные команды, а дуги указывают на последовательность переходов от одной команды к другой. В алгоритме любой путь начинается от вершины начала и заканчивается выходом на вершину конца. Внутри же путь может быть разным в зависимости от исходных данных.

Задача 6. На уроке географии мы рассматривали параграф. И чтоб быстрее его найти я открыла в конце учебника содержание. И к своему удивлению заметила, что структура разделов учебника отражена в виде дерева.

Задача 7 . На уроке русского языка тема «Числительные» и учитель предложила нам составить опорный конспект.

Числительные в русском языке классифицируются по составу и по значению. По составу они делятся на простые, сложные и составные. Пример простых числительных: четыре, пять. Пример сложных числительных: шестьдесят, пятьсот. Пример составных числительных: 35, 154. По значению числительные делятся на порядковые и количественные. Пример порядковых числительных: второй, девятый. Пример количественных числительных: шесть, два.

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

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

Решение.

Чтобы указать все обеды из двух блюд, будем рассуждать так.

Выберем одно первое блюдо (борщ) и будем добавлять к нему поочерёдно разные вторые

Ответ: 8 разных обедов из двух блюд.

Замечание. В задаче осуществляются два выбора, но каждый выбор - из своего множества вариантов.

Ответ: 6 сочетаний.

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

После школы, на занятиях кружков «Занимательная информатика» и «Шах и МАТ», благодаря теории графов, с легкостью решали логические задачи.

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

Так графы стали мои лучшими друзьями. Одноклассники и учителя заметили, что у меня улучшилась успеваемость по предметам. Но я то знаю, что это благодаря «Его величеству Графу»!

Вывод

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

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

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

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

Библиографический список

1. Генкин, С. А, Итенберг И. В. Ленинградские математические кружки: пособие для

внеклассной работы.-Киров, 1994г.

2.Горбачев, В.Г. Сборник олимпиадных задач по математике.- М., 2004г.

3. Игнатьев Е.И. Математическая смекалка. - Москва, 1994 г.

4.Оре, О. Графы и их применение.- Москва, 1979 г.

5.Перельман, Я.И. Весёлые задачи.- Москва, 2003г

6. Физико-математический журнал «Квант», А. Савин, №6, 1994г.

страница 1

Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации: Исследовательская работаГрафы вокруг нас.Выполнила: Абросимова Елена ученица 8 «А» класса МАОУ Домодедовской СОШ №2Руководитель: Генкина Н.В.

Выяснить особенности применения теории графов при решении математических, логических и практических задач.Цель исследовательской работы:
Изучить теорию графов;Решить задачи с помощью графов;Рассмотреть применение теории графов в различных областях науки;Создать с помощью теории графов маршруты и задачи;Выяснить наличие знаний о графах у учеников 7 классов.Задачи:

Граф-?
Леонард Эйлер Первый кто развил теорию графов, был немецкий и русский математик Леонард Эйлер (1707-1783). Нет науки, которая не была бы связана с математикой

Задача о Кёнигсбергских мостах
Представим задачу в виде графа где острова и берега - точки, а мосты -ребра.
Задачи. №1Мальчики 10«Б» класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
№2 Задача о перестановке четырех коней. Напишите алгоритм перестановки жёлтых коней на место красных коней и красных коней на место жёлтых коней.
Теория графов в различных областях науки. Теория графов в различных областях науки. Собственные разработки Маршрут по домодедовским церквям.
Маршрут автобуса для пенсионеров.
Задача №1.
Ответ:
Задача №2.
Маршрут по Дворцовым Питерским мостам. Исследование:
«Графы и их применение» Л. Ю. Березина.«Знаменитейший ученый муж» изд. Калейдоскоп «Кванта» «Леонард Эйлер» В. Тихомиров«Топология графов» В. Болтянский«Современная школьная энциклопедия. Математика. Геометрия» изд. «Москва Олма Медиа Групп»Граф (математика) - Википедия ru.wikipedia.orgГрафы. Применение графов к решению задач festival.1september.ruГРАФЫ sernam.ruГрафы | Социальная сеть работников образования nsportal.ruГрафы / Математика studzona.comГрафы и их применение в решении задач sch216.narod.ruГрафы 0zd.ruИсточники: Спасибо за внимание.

Муниципальное автономное общеобразовательное учреждение
Домодедовская средняя общеобразовательная школа №2
Исследовательская работа.
«Графы вокруг нас».
Выполнила: Абросимова Е. С. ученица 8 «А» класса.
Руководитель: учитель математики Генкина Н.В.
2014 год.
План:
Вступление.
Гипотеза.
Актуальность темы.
Теория.
Практическое приложение.
Собственные разработки.
Исследование.
Заключение.
Вступление:
Теория графы заинтересовала меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Так как я готовилась к математической олимпиаде, то теория графов была неотъемлемой частью в моей подготовке. Углубившись в эту тему, я решила понять, где ещё встречаются графы в нашей жизни.
Гипотеза:
Изучение теории графов может помочь в решении различных головоломок, математических и логических задач.
Актуальность темы:
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Поэтому тематика данной работы достаточно актуальна.
Теория:
Теория графов - раздел математики, изучающий свойства графов. В математической теории граф - это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами). Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются отрезком или дугой. В случае ориентированного графа дуги заменяют стрелками, или явно указывают направленность ребра. Есть и планарный граф - это граф, который можно изобразить на рисунке без пересечения. В том случае, если граф не содержит циклов (путей однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов - бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной - не имеющей выходящих рёбер. Основные понятия теории графов. Маршрут графа – последовательность чередующихся вершин и ребер. Замкнутый маршрут – маршрут, в котором начальная и конечная вершины совпадают. Простая цепь – маршрут, в котором все ребра и вершины различны. Связный граф – граф, в котором каждая вершина достижима из любой другой.
Терминология теории графов поныне не определена строго.
Первый кто развил теорию графов, был немецкий и русский математик Леонард Эйлер (1707-1783). Который известен своей старинной задачей о кёнигсбергских мостах, которую решил в 1736 году. Эйлер математик и механик, внёсший фундаментальный вклад в развитие этих наук. Вся жизнь Л. Эйлера была связана с научной деятельностью и не только связанной с графами. Он говорил: «Нет науки, которая не была бы связана с математикой». Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805- 1865), из современных математиков - К. Берж, О. Оре, А. Зыков.

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

Свойства графа (Эйлер): Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине. Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
Практическое приложение:
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
В спортивном зале собрались Витя, Коля, Петя, Сережа и Максим. Каждый из мальчиков знаком только с двумя другими. Кто с кем знаком.
Решение: Построим граф.
Ответ: Витя знаком с Колей и Сережей, Сережа с Витей и Петей, Петя с Сережей и Максимом, Максим с Петей и Колей, Коля с Петей и Максимом.
Мальчики 10 «б» класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку другому по одному разу). Сколько всего рукопожатий было сделано? Решение:Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию - отрезок или часть кривой, соединяющая конкретные точки - имена.
Если подсчитать число ребер графа, изображенного на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Задача о перестановке четырех коней. Напишите алгоритм перестановки жёлтых коней на место красных коней и красных коней на место жёлтых коней. Конь перемещается за один ход буквой «Г» в горизонтальном, либо в вертикальном положении. Конь может перепрыгивать через стоящие на его пути другие фигуры, но может ходить только на свободные поля.
Решение. Каждой клетке доски сопоставим точку на плоскости, и если из одной клетки можно попасть в другую ходом коня, то соединим соответствующие точки линией, получим граф.
Написание алгоритма перестановки коней становится очевидным.

Усадьба Хакенбуш.
Эту замечательную игру придумал математик Джон Конвей. Для игры используется картинка с "усадьбой Хакенбуш" (смотрите ниже). За один ход игрок стирает один любой отрезок картинки, ограниченный точками или одной точкой, если отрезок это петля. Если после удаление этой линии, часть линий оказывается не связанной с рамкой, то она удалятся тоже. На рисунке пример, где удалятся линия, выделенная зеленым цветом, и вместе с ней удаляются линии дыма, выделенные красным. Игрок, который удаляет последний элемент картинки выигрывает.

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

Задача:
Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:
1) Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин:

2)Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.
3) Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи:

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

В химии и биологии,

В природоведении,

В проектировании интегральных схем и схем управления,

В истории.

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

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

Также меня вдохновило решение интересных задач, и поэтому я создала свои собственные.
Задача:
Шел урок. Во время урока Маша передала записку Кате. Как составить граф, чтобы записка дошла до Полины. При условиях, что нельзя передавать записку по диагонали, и чтобы граф не пересекался с маршрутом (графом) учительницы.

Задача:
На луг пастух вывел 8 овец. Через некоторое время появился волк, который прикинулся овцой. Как пастуху выявить волка, если каждая овца знакома лишь с двумя другими.
Ответ:

Задача:
Как обойти Дворцовые мосты ни проходя ни по одному мосту дважды. Одной из задач создания такого маршрута было условие, что по одной дороге нельзя проезжать дважды. Это условие можно выполнить, опираясь на теорему Эйлера.

После составления карт и задач, я решила провести исследование и понять, как другие люди пользуются наукой графы.
Исследование о наличии знаний у учеников 7 классов по теории графов:
ВОПРОСЫ:
Играли ли вы в игру нарисовать фигуру по цифрам?
lefttop00
Играли ли вы в игру нарисовать одним росчерком конверт?

Вы делали это, основываясь на каких-то научных знаниях или методом проб и ошибок?
А знаете ли вы, что существует целая наука «графы», которая помогает решить вышеперечисленные задачи?
Хотели бы вы поближе познакомиться с теорией графов?

Заключение:
После того, как я провела эту исследовательскую работу, я изучила более подробно теорию графов, доказала свою гипотезу: «Изучение теории графов может помочь в решении различных головоломок, математических и логических задач», рассмотрела теорию графов в разных областях науки и составила свой собственный маршрут и свои три задачи. Но делая эту работу, я заметила, что многие люди фактически пользуются этой наукой, хотя не имеют о ней ни малейшего представления. Я изучила многое, но еще есть над чем работать.
Список литературы
Л. Ю. Березина «Графы и их применение: Популярная книга для школьников и преподавателей». Изд. Стереотип.- М.: Книжный дом «ЛИБРОКОМ», 2013.- 152 с.
«Знаменитейший ученый муж». Изд. Калейдоскоп «Кванта»
В. Тихомиров «Леонард Эйлер» (К 300-летию со дня рождения). Изд. «Квант»
В. Болтянский «Топология графов». Изд. «Квант»
«Современная школьная энциклопедия. Математика. Геометрия». Под ред. А.А.Кузнецова и М.В. Рыжакова. Изд. «М.: Олма Медиа Групп», 2010. – 816 с.
Цифровые ресурсы:
wikipedia.orgfestival.1september.rusernam.runsportal.rustudzona.comsch216.narod.ru0zd.ru