Связные графы и головоломки

Ставропольский краевой открытый научно-инженерный исследовательский конкурс

Номинация: фундаментальная и прикладная математика

Название работы: «Связные графы и головоломки»

Автор работы:

Звягинцев Иван Сергеевич

Место выполнения работы:  

с. Тугулук, МКОУ СОШ №8,  7 класс

Научный руководитель:

Шеховцова Елена Сергеевна,

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

МКОУ СОШ №8 с. Тугулук

Ставрополь, 2024

Оглавление

1. Введение…………………………………………………………...2
2. Связные графы………….………………………………………….4

1. История возникновения теории графов………………......4
2. Эйлеровы графы…………………………………………….7
3. Гамильтоновы линии……………………………………....8
4. Головоломки и графы

2.4.1. «Ханойская башня» и «Икосаэдрическая игра»…..10

2.4.2. Коллекция головоломок ……………………………12

3. Заключение…………………………………………………….…..14
4. Библиографический список………………………………………15
5. Приложения……………………………………………………16-22

I. Введение

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

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

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

Цели исследования:

1. изучение истории возникновения теории графов, основных понятий и свойств;
2. исследование связных графов;
3. решение различных головоломок, создание  набора головоломок на графах.

Задачи исследования:

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

Объект исследования:  связные графы.

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

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

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

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

Граф, который можно начертить таким образом, чтобы его ребра пересекались только в вершинах, называется плоским графом. Так, граф G (Приложение1) является плоским, потому что существует изоморфный ему граф (Приложение2), все ребра которого пересекаются только в вершинах.

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

Граф называется связным, если для любых вершин А и В есть путь из А в В.

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

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Леонарду Эйлеру, появилась в 1736г.

Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.(Приложение3)

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

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

Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого  выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

   В 20 веке задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. Наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”.

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

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

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

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

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

Эйлер доказал, что эти условия являются также и достаточными.

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

Теорема 2. Для того чтобы на связном графе имелась цепь Z(А, В), содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.

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

2.3. Гамильтоновы линии.

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

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

Гамильтон придумал много игр и головоломок, связанных с додекаэдром, но самой интересной из них была следующая. Начав с любой вершины додекаэдра(Приложение 6)  (каждой его вершине Гамильтон дал название какого-нибудь крупного города), нужно было совершить «кругосветное путешествие» — обойти ровно один раз все ребра правильного многогранника и вернуться в исходную вершину. Иначе говоря, путь должен иметь вид замкнутой ломаной, составленной из всех ребер додекаэдра. Каждое ребро разрешается проходить только один раз.

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

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

2.4. Головоломки и графы.

2.4.1. «Ханойская башня» и «Икосаэдрическая игра».

Вряд ли что-нибудь может произвести большее впечатление на математика, чем открытие связи между двумя на первый взгляд никак не связанными между собой математическими структурами. Именно такое открытие сделал Д. У. Кроув. Он обнаружил связь между двумя популярными головоломками прошлого века — «Икосаэдрической игрой» и «Ханойской башней». Сначала мы расскажем о каждой головоломке в отдельности, а затем покажем ту неожиданную связь, которая существует между ними.

Известную игру «Ханойская башня» придумал французский математик Эдуард Люка. В 1883 году ее продавали как забавную игрушку. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причем нельзя класть большее кольцо на меньшее. (Приложение 8)

Решение существует независимо от того, сколько колец в пирамиде, и что минимальное число необходимых перекладываний выражается формулой 2n — 1 (где n — число колец). Таким образом, три диска можно перенести с помощью семи перекладываний; для четырех дисков понадобится пятнадцать перекладываний, для пяти — 31 и т. д. Для восьми колец потребуется 255 перекладываний. В первоначальном описании игрушка называется упрощенным вариантом мифической «Пирамиды браминов» в храме индийского города Бенареса. Как гласит предание, эта пирамида состоит из 64 золотых колец, которые и по сей день перекладывают жрецы храма. Как только им удастся справиться со своей задачей, храм рассыплется в пыль, грянет гром и мир исчезнет. О конце мира еще, пожалуй, можно спорить, но то, что храм за это время обратится в пыль, несомненно. Формула 264 - 1 дает двадцатизначное число 18446744073703551615. Даже если бы жрецы работали не покладая рук, днем и ночью, перенося каждую секунду по одному кольцу, чтобы закончить работу, им понадобились бы многие миллионы тысячелетий.

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

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

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

2.4.2. Коллекция головоломок.

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

1. Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Наконец она устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно). Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача? (Приложение 9)

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

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

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

5. На рисунке (Приложение 12) изображён план деревни. Тракторист заметил, что, если по каждой улице деревни он проедет только по одному разу, то закончит свою поездку на том перекрёстке, где находится гараж. С какого перекрёстка начал своё движение тракторист и где находится гараж? Сколько имеется вариантов решения?

6.  Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз? (Приложение 13)

7. Река разделяет город на четыре части, соединённые шестью мостами. Один турист решил обойти все мосты, побывав на каждом из них только один раз. Как это можно сделать, если не требовать обязательного возвращения в тот же район города, из которого начался обход? Добавьте на рисунок ещё один мост так, чтобы: а) можно было совершить переход через все мосты из любой части города; б) совсем нельзя было совершить переход через все мосты, побывав на каждом по одному разу. (Приложение 14)

8. На рисунке дан план квартиры. Разрывы в линиях обозначают двери. Маленькому мальчику захотелось за один обход пройти через все двери свое квартиры по одному разу. Его папа помог ему в этом. С какой комнаты мальчик мог начать свой путь? (Приложение15)

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

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

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

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

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

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

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

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

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

1. Интернет-Университет Информационных Технологий http://www.intuit.ru/department/algorithms/graphsuse/5/graphsuse_5.html

2. МobWiki.  http://mobwiki.ru/Гамильтонов_цикл

3. Мартин Гарднер Гексафлексагоны и Другие Математические Развлечения. http://stepanov.lk.net/gardner/hex/hex06.html

4. Гамильтонов граф. Тематические статьи Lmatrix. http://lmatrix.ru/news/theory/gamiltonov-graf_49.html

5. Энциклопедический словарь юного математика\Сост.А.П.Савин.-  М.: Педагогика, 1989

6. Журнал «Квант» №6 1994г.

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

8. Кордемскин Б. А. Математическая смекалка, М., Физматгиз, 1984.

9.Оре О. "Графы и их применения", М. "Мир", 1975.

        10. Лойд С. Математическая мозаика. Сост. и ред. М. Гарднер/ Пер. с англ. – М.: «РИПОЛ», 1995.

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Приложение 5

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

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

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

Приложение 9

Приложение 10

Приложение 11

Приложение 12

Приложение 13

Приложение 14

Приложение 15