Тема: «Графы и решение логических задач».

Тема: «Графы и решение логических задач».

Посельский Борис                                                                                                                                                                                                                                                                                                                                                               учеником  8 «в»  класса МБОУ «Нижнесаянтуйская СОШ»

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

                                           Кожемякина Ирина Семеновна

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

МБОУ «Нижнесаянтуйская СОШ»

2018г

Оглавление.

1. Введение

2. Глава 1.Теория графов  

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

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

2.3.Граф и его элементы

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

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

3. Глава 2. Решение задач с помощью графов

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

5. Список литературы

Введение.

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

Предмет моего исследования: графы

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

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

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

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

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

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

Гипотеза:

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

Глава 1.  ТЕОРИЯ ГРАФОВ

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

 Начало теории графов все единодушно относят к 1736 г., когда Леонард Эйлер - один из крупнейших математиков XVIII, члена Петербургской академии наук, не только решил популярную в то время задачу о кёнигсбергских мостах, но и  

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

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

теорию графов, называемых деревьями, для исследования

Рис. 4  Портрет Леонарда Эйлера.       электрических цепей, а математик А. Кэли в связи с    

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

                деревьев.

   Термин «Графы» ввёл в язык немецкий математик Д. Кёниг. Он первым предложил называть такие схемы «графами». Термин «граф» (от латинского слова «графио» - пишу) приобрел права гражданства и вошел в математический язык в 1936 году, после выхода в свет монографии Кёнига, в которой впервые графы рассматриваются как самостоятельные математические объекты независимо от их конкретного содержания.

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

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

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

  Задача о семи мостах заинтересовала Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем кёнигсбергским мостам, не проходя дважды ни по одному из них. Его ответ был - «нельзя».

    Читая письмо Эйлера выясним, какое же правило он нашел:

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

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

Построим граф без посторонних линий. Рис. 2

  Читаем письмо Эйлера дальше: "Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста. То есть нам нужно определить степень каждой вершины, и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

Покажу это на графе - Рис. 3.

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

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

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

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

                                 3.  Граф и  его элементы.

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

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

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

Абсолютно неважно, какой вид имеют эти линии, и как точки расположены в пространстве. Идея графа — это набор каких-то объектов, с описанными связями между ними. В самом простом случае связь может быть, а может не быть. Приведу пример. Допустим, мы имеем группу людей. Это будут точки в графе. Мы можем описать связи между этими людьми. Например, связь - «знакомства». Если два человека знают друг друга, то между ними есть связь. На рисунке такого графа связь между ними будет обозначена линией от одного человека к другому. Вот как выглядит такой рисунок (граф):

По рисунку (графу) видно, что с Мариной никто не знаком, а Саша  знаком с Олегом, Катей и Леной.

  В графе точки называются вершинами графа, а соединяющие их линии (дуги) – рёбрами.  Смотрим Рис. 1.

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

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

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

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

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

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

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

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст. Г= 2, Ст. Д= 0.

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

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

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

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

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

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

Теорема .

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

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

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

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

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

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

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

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

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

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

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

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

Глава 2. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ.

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

Задача 1. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость?

Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад

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

Соединим пунктирными ребрами те вершины, которые не могут быть связаны друг с другом.

Тогда получаем:

В бутылке – квас или лимонад, так как в банке только квас, значит в бутылке – лимонад;

В кувшине – молоко или вода, так как в стакане не молоко, значит – вода, а кувшине тогда молоко.

Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад

Решение задачи в графах.

Задача 2. На международном конгрессе встретились четверо ученых: физик, историк, биолог и математик. Национальности их различны и, хотя каждый из ученых владеет двумя языками их четырех (русский, английский, французский и итальянский), нет такого языка, на котором они могут разговаривать вчетвером. Есть язык, на котором они могут разговаривать сразу трое, – итальянский. Никто из ученых не владеет французским и русским языками одновременно. Хотя физик не говорит по-английски, но может быть переводчиком, если биолог и историк захотят поговорить друг с другом. Историк может говорить с математиком по-французски. Физик, биолог и математик не могут беседовать втроем на одном языке. Какими двумя языками владеет биолог (укажите названия языков в именительном падеже через пробел).

Решение: Соединим пунктирными ребрами те вершины, которые не могут быть связаны друг с другом.

Ответ: русский английский

Задача 3. Однажды мама, в магазине купила разную приправу: красный перец, коричневый имбирь, зелёную петрушку и белую горчицу. Придя домой, она разложила всё это в баночки для специй. Я знаю, что у нас дома каждая специя лежит в своей баночке и цвет банки не соответствует свету специй. Так же известно, что зеленая петрушка лежит в коричневой банке, а красный перец не лежит в белой  баночке. Мне для приготовления плова нужно узнать: «В какой банке лежит каждая специя?»

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

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

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

Задача 4. Запишите все трехзначные числа, для записи которых употребляются только цифры 1 и 2.

Ответ: 111, 112, 121, 122, 211, 212, 221, 222.

Задача 4. Сколько трехзначных чисел можно составить из цифр 2,4,6,8, если цифры в записи числа не повторяются?

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

Всего можно составить 4*3*2= 24 трехзначных числа.

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

Задача 5.

                     Рис.1                                         Рис. 2

На рисунке 1 пять вершин, причем три из них – четные ( 1,2 и 3), а два нечетных (4 и 5). Эту фигуру можно начертить одним росчерком. Основываемся при решении на

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

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

А вот домик с дверью рис.2 – это уже другая фигура, содержит 9 вершин, 5 из которых четные, а 4 – нечетные. Если в фигуре на графе больше двух нечетных вершин, то ее нельзя начертить одним росчерком!

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

Решение:

1. Можно, т. к. только 2 нечетные вершины.
2. Нельзя, т. к. 4 нечетные вершины.

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

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

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

Их 10.   Ответ: 10.

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

Решение:

Построим граф, вершины которого,
А, Б, В, 1, 2, 3
соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Задача 9. Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

Решение:

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

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

Решение:

Если пятиугольник – граф и все вершины его четные – то это выполнить

ЗАКЛЮЧЕНИЕ:

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

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

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

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

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

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

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

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

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

4. Математика (Дополнительные главы). Е. В. Смыкалова  Санкт-Петербург СМИО Пресс 2006

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

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

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

8. Наглядная геометрия И.Ф.Шарыгин, Л.Н. Ерганжиева М, дрофа, 2000г.