VII Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Теория графов и уникурсальные фигуры: их практическое применение

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Фесенко С.А. 1

---

1МАОУ Одинцовский лицей №6 им. А.С.Пушкина

Колчина Л.Д. 1

---

1МАОУ Одинцовский лицей №6 им. А.С.Пушкина

Работа в формате PDF

7.1 MB

Автор работы награжден дипломом победителя I степени

Диплом школьникаСвидетельство руководителя

«В математике следует помнить не

формулы, а процесс мышления»

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

ВВЕДЕНИЕ

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

Задачи:

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

Ознакомиться с понятием “граф”, с его основными элементами.

Узнать, что такое уникурсальная фигура.

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

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

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

Объектом исследования являются графы и уникурсальные фигуры.

Предмет исследования: Теория графов и уникурсальные фигуры.

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

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

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

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

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

1. Изучение информационных источников: историческая и научная литература, энциклопедические словари, интернет-источники.

2. Анкетирование одноклассников, друзей и их родителей.

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

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

Разве не пытался кто-то из вас построить генеалогическое дерево своей семьи? Руководителю транспортного предприятия наверняка приходится решать проблему более выгодного использования транспорта при перевозке грузов с места назначения в несколько населенных пунктов. Каждый школьник сталкивался с логическими задачами. А как это сделать грамотно?

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

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

АНКЕТИРОВАНИЕ

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

Знаете ли Вы, что такое ГРАФ?

Знаете ли Вы, что такое УНИКУРСАЛЬНАЯ ФИГУРА?

Где в жизни применяются графы и уникурсальные фигуры?

Кто автор знаменитой задачи о Кёнигсбергских мостах?

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

Результат анкетирования:

В анкетировании принимали участие:

- сверстники (возраст до 15 лет) – 8 чел.,

- респонденты от 15 до 30 лет – 5 чел.,

- участники старше 30 лет – 11 чел.

На 1-й вопрос 69% анкетируемых ответили, что знают, что такое Граф

На 2-й вопрос только 22% ответило утвердительно.

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

На 4-й вопрос 32% ответили, что знают автора задачи о Кёнигсбергских мостах.

И 81% участников опроса смогли решить задачу.

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

ОСНОВНАЯ ЧАСТЬ

Из истории …

В

Л.Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук)

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

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого с итальянским математиком и инженером Маринони (Приложение №1 – письмо, отправленное из Петербурга 13 марта 1736 года).

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

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

Понятие «Граф»

Основные определения теории графов

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

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

Принято вершины графа обозначать латинскими буквами A, B, C, D.

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

Определение 3. Граф, состоящий только из изолированных вершин, называется нуль-графом. Обозначение: O' – граф с вершинами, не имеющий ребер.

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

Определение 5. Степеньювершиныназыва-ется число ребер, которым принадлежит вершина.

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

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

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

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

Свойства таких графов:

- в уникурсальной кривой может быть любое число четных узлов, но не более двух нечетных;

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

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

С амые известные графы имеют собственное имя.

Г раф «Раскрытый конверт» [см. рис.]

С уществующий граф с шестью вершинами и девятью рёбрами [см. рис.], носит название «Домики-колодцы». Оно произошло от старинной задачи-головоломки.

Задача о Кёнигсбергских мостах

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

Задача про рукопожатия

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

Лабиринт

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

В дальнейшем используются следующие понятия и определения:

Лабиринт – это какая-либо структура, которая располагается в пространстве и состоит из запутанных путей к выходу. Данные пути представляют собой некоторую последовательность помещений;

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

ПРАКТИЧЕСКАЯ ЧАСТЬ

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

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

Что же я узнал нового?

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

- количеством вершин (B);

- количеством рёбер (Р);

- количеством частей (Г), на которые разделяется плоскость:

В – P + Г = 2

Если полный граф имеет n вершин, то количество ребер будет равно

n(n-1)/2

ЗАДАЧИ

Знаменитые задачи

№1. Задача коммивояжера

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

Постановка задачи следующая: Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Решение:

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

Р ассмотрим для примера сеть на рисунке [см. рис.], представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

№2. Задача о Кенигсбергских мостах.

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

Решение:

Р ассмотрим граф, соответствующий схеме мостов [см рис.].

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

Интересные задачи

Р аздел «Маршруты»

Задача №1

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

Р ешение:

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D- Коробочке, С - Ноздреву, А - Собакевичу, В - Плюшкину, М - Тентетникову, F - Бетрищеву, Н - Петуху, К - Констанжолго, О - Кошкареву[см.рис.].

З адача №2

На рисунке изображена схема местности [см. рис.].

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий, и какой маршрут - самый длинный.

Р ешение:

Последовательно "расслаиваем" схему в дерево, начиная с вершины 1 [см. рис.]. Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

Раздел «Группы, знакомства»

Задача №1. О рукопожатиях

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

Решение:

П рименяя формулу Эйлера (n(n-1)/2) сразу получаем ответ: 10 рукопожатий.

Задача №2

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

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Р ешение:

Пусть участники фестиваля А₁, А₂, А₃ . . . , А_n - вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами [см.рис.].

а) степень каждой вершины А_i показывает число конвертов, которое передал участник А_i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А₁ + степ. А₂ + . . . + степ. А_n-1 + степ. А_n , N=2p, где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А₁ + степ. А₂ + + . . . + степ. А_n-1 + степ. А_n сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.

Задача №3

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

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д. Это первые буквы имён. Соединим те точки, которые соответствуют именам созвонившихся ребят [см.рис.].

Из рисунка видно, что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Задачи практического плана

Задача №1. Транспортная

Пусть в городе Краснодаре находится база с сырьём, которое нужно развести по городам Крымск, Темрюк, Славянск-на-Кубани и Тимашевск одним заездом, затратив при этом как можно меньше времени и топлива и вернувшись обратно в Краснодар.

Р ешение:

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

Для удобства решения обозначаем города цифрами: Краснодар – 1, Крымск – 2, Темрюк – 3, Славянск – 4, Тимашевск – 5.

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

Задача №2. Логическая задача на переливание

В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами [см.рис.].

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

ЗАКЛЮЧЕНИЕ

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

Выводы:

Разобрав эти интереснейшие задачи, я выявил следующее:

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

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

Проанализировав свои исследования, можно заключить:

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

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

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

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

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

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

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

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

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

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

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

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

Итак, начало уже положено, а будущее – за нами!

СПИСОК ЛИТЕРАТУРЫ

Энциклопедия для детей. Юному эрудиту обо всем [пер. с англ.]. London, Kingfisher Publications Plc, 1997 г. / Изд. Махаон, 2008 г., с. 93-94

Журнал "Галилео. Наука опытным путем". DeAgostini Russia, № 32, 2012 г.

Мартынюк Ю.М., Ванькова В.С., Угаров А.С. Формализация лабиринта в теории графов // Современные научные исследования и инновации. 2015. № 1

Шейнина О.С., Соловьева Г.М. Математика. Занятия школьного кружка. 5-6 кл. – М.: Изд-во НЦ ЭНАС, 2004. – 208 с.

Интернет- ресурс:

http://pm.far-for.net

http://www.strana.ru/news/232242.html

http://web.snauka.ru/issues/2015/12/61428

Берж К. Теория графов и ее применения. – M.: ИИЛ, 1962.

Зыков А.А. Теория конечных графов. – Новосибирск: Наука, 1969.

Березина Л.Ю. Графы и их применение. – M.: Просвещение, 1979. – 144 c.

Гарднер М. Математические досуги, М. Мир, 1972 (глава 35)

Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные занимательные задачи. – М. Наука, 1988 (часть 2, раздел 8; прил. 4)

Оре Ойстин. Графы и их применение. – М, 1965.

Крейдлин Г.Е. Математика помогает лингвистике, 1994.

Уилсон Р. Введение в теорию графов, 1977.

Мир математики. №11. Карты метро и нейронные сети. Теория графов. DeAgostini, 2014.

ПРИЛОЖЕНИЯ

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

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

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

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:

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

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

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

Применение графов в различных областях жизнедеятельности людей

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

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

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

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

Пример генеалогического дерева моей семьи [см. рис.].

Еще один пример. На рисунке показано библейское генеалогическое дерево [см. рис.].

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

Графы используют даже филологи - Графы и стилистика переводов иностранных текстов:

1. В. Шекспир.

That time of year thou mayst in me be hold

When yellow leaves, or none, or few do hang

Upon those boughs which shake against the cold

In me thou seest the twilight of such day

As after sunset fadeth in the west

Which by and by black night doth take away,

Death’s second self that seals up all the rest.

In my thou seest the glowing of such fire,

That on the ashes of his youth doth lie,

As the death-bed, whereon it must expire,

Consumed with that which it was nourished by.

This thou perciev’st, which makes thy love more strong,

To love that well, which thou must leave ere long.

2. Б. Пастернак.

То время года видишь ты во мне,

Когда из листьев редко, где какой,

Дрожа, желтеет в веток голизне,

А птичий свист везде сменил покой.

Во мне ты видишь бледный край небес,

Где от заката памятка одна

И, постепенно взявши перевес,

Их отпечатывает темнота.

Во мне ты видишь то сгоранье дна,

Когда зола, что пламенем была,

Становится могилою огня,

А то, что грело, изошло дотла

И, это видя, помни: нет цены

Свиданьям, дни которых сочтены.

Теперь начертим графы нескольких строк эти стихотворений.

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