Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа с. Чапланово

муниципального образования «Холмский городской округ»

Сахалинской области

ЕСТЕСТВЕННО-НАУЧНОЕ НАПРАВЛЕНИЕ

ТЕМА НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЫ

«Графы в математике»

Автор: Ткаченко Маргарита Алексеевна

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

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

Алексеева Светлана Валерьевна, учитель математики и информатики МАОУ СОШ с.Чапланово

г. Холмск, 2021

Оглавление

Введение        3

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

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

1.2.        Основные виды графов.        6

1.3.         Свойства графов        9

1.4.        Типы задач, решаемых с помощью графов        10

1.4.1.        Задачи на вычерчивание фигур одним росчерком.        10

1.4.2.        Задачи о мостах.        10

1.4.3.        Задачи о колодцах.        11

1.4.4.        Логические задачи.        12

1.4.5.        Задачи на рукопожатиях.        12

1.4.6.        Примеры олимпиадных задач с помощью графов.        13

Заключение        14

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Анализ и сравнение задач.

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

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

Теория графов – наука сравнительно молодая. Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

В дальнейшем над графами работали Юлиус Кениг (1774-1833), Уи́льям Ро́уэн Гамильтон (1805-1865), из современных математиков – Клод Берж (1926-2002), Ойстин Оре (1899-1968), Александр Александрович Зыков (1922-2013).

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг (1884-1944), назвав графами схемы, состоящие из множества точек и связывающих эти точки отрезков прямых и кривых.

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

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

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

структура алмаза схема                 городской телефонной сети

     генеалогическое дерево                 схема метро                         схемы авиалиний

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

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

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

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

2. Основные виды графов.

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

Рис. 4

3. Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами (рис. 5).
4. Граф без кратных ребер и петель называется обыкновенным (рис. 6).

Рис. 5                                                 Рис. 6

5. Полный граф – это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа (рис. 7).
6. Если в графе каждые две вершины связаны ребром, то это связанный граф. Граф называется несвязанным, если в нем есть хотя бы одна пара несвязанных вершин (рис. 8).
7. Плоский граф (Плана́рный граф)  граф, который может быть изображён на плоскости без пересечения рёбер (рис. 9)

8. Смешанный граф-это граф, в котором некоторые рёбра ориентированные, другие неориентированные (рис. 10)
9. Граф Эйлера – это граф, который является замкнутым, т. е через каждое ребро графа можно пройти ровно по одному разу (рис. 11).

Рис. 11

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

Рис. 12

11. Взвешенный граф-это граф с вершинами или рёбрами, несущими добавочную информацию, другими словами вес (рис. 13).

Рис. 13

12. Если в графе выбрать такой путь, когда начальная и конечная точка совпадают, то такой путь называется циклом графа (рис. 14).
13. Если прохождение через каждую вершину графа происходит не более одного раза, то цикл называется простым.        
14. Если граф связанный, но не содержит циклов, то такой граф называется деревом. Между любыми двумя его вершинами есть ОДИН путь. Дерево не содержит циклов и петель (рис. 15).

Два ребра называются смежными, если они выходят из одной вершины (рис. 16).

Два ребра называются кратными, если они соединяют одну и ту же пару вершин (рис. 17).

Ребро называется петлей, если его концы совпадают (рис. 18). 

Степени вершин

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

Рис. 19

Вершина называется изолированной, если она не является концом ни для одного ребра. Вершина называется висячей, если из неё выходит ровно одно ребро (рис. 20).

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

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

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

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

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

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

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

4. Типы задач, решаемых с помощью графов

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

1. Задачи на вычерчивание фигур одним росчерком.
2. Задачи о мостах.
3. Задачи о колодцах.
4. Задачи о "правильном" раскрашивании карт.
5. Логические задачи.
6. Задачи на рукопожатия.
7. Задачи про города и дороги.

Рассмотрим эти задачи и способы их решения.

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

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

Рассмотрим рисунок 21:

• у фигур 1 и 5 все вершины четные, поэтому данные фигуры можно начертить одним росчерком (свойство 1);
• у фигур 2, 3, 6 имеется две нечетных вершины, но по свойству 2 и их можно начертить одним росчерком;
• а вот фигуры 4 и 7 нельзя начертить одним росчерком, так как у них более двух нечетных вершин (свойство 3).        

1. Задачи о мостах.

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

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

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

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

2. Задачи о колодцах.

3. Логические задачи.

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

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

4. Задачи на рукопожатиях.

Задача

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

Решение:

Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. В задаче необходимо подсчитать число ребер графа, изображенного на рисунке 24. Это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

Лемма о рукопожатиях

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

Из леммы о рукопожатиях вытекает следующий факт:

В любом графе число вершин нечетной степени четно.

5. Примеры олимпиадных задач с помощью графов.

Задача 1.

Задача 2.

Заключение

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

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

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

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

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

1. Барболин М. Головоломки и графы // научно-популярный физико-математический журнал «Квант» - 1994. - № 6 – 33 с.
2. Горбачев В. Г. Сборник олимпиадных задач по математике / В. Г. Горбачев. – М., 2004 – 56 с.
3. Мельников О. И. Теория графов в занимательных задачах. Изд. 3-е. / О. И. Мельников – М.:КомКнига, 2009. – 232 с.
4. Оре О. Графы и их применение: Пер. с англ. / О. Оре.  – М.:Наука, 1980. – 176 с.
5. Фосс В. Элементы теории графов // научно-популярный физико-математический журнал «Квант» - 1973. - № 8 – 17 с.
6. Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
7. https://ru.wikipedia.org/wiki/Теория_графов