XI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Графы
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Эйлер вычислял без всякого видимого усилия,
как человек дышит или как орел парит над землей.
Доминик Араго
ВВЕДЕНИЕ
Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ.
В математике даже есть специальный раздел, который так и называется: «Теория графов».
Актуальность проекта: теория графов позволяет решать наиболее легким способом, наглядно многие логические задачи, которые способствуют развитию мышления, наблюдательности, интеллекта.
Практическая значимость: заключается в том, что данный материал можно использовать на уроках математики при решении комбинаторных задач, на внеурочных занятиях. Он (материал) учит нас анализировать ситуацию, рассуждать, перебирать различные варианты построения графов, учит мыслить нестандартно, развивает воображение
Цель исследования: познакомиться с новым понятием «граф» и научиться применять теорию графов при решении математических и логических задач.
Задачи:
Найти различные источники с информацией о графах;
Познакомиться с историей появления графов;
Изучить правила составления графов;
Научиться самостоятельно составлять графы.
Объект исследования: примеры графов
Предмет исследования: методы и способы применения графов при решении математических и логических задач.
Гипотеза:Если метод графов так важен, то обязательно найдется его широкое применение в различных областях науки и жизнедеятельности человека.
Методология исследования:
Изучить определение и свойства графа.
Изучить историю возникновения графов.
Исследовать роль графов в нашей жизни.
Научиться применять теорию графов при решении математических и логических задач.
ОСНОВНАЯ ЧАСТЬ
История возникновения теории графов
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад.
Родоначальником теории графов считаетсяЛеонард Эйлер (1707-1783) – математик, механик, физик и астроном. Ученый необычайной широты интересов. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и других, оказавших значительное влияние на развитие науки. Леонард Эйлер по происхождению швейцарец. В 1726г. был приглашен работать в Петербург, в 1727г. переехал жить в Россию. Являлся академиком, а затем почетным членом Петербургской академии наук.
Первая работа по теории графов принадлежит именно ему (1736), в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.
Бывший Кёнигсберг (Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать, только один раз. До Эйлера никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось.
Эта задача связана с другими головоломками, суть которых в том, чтобы обвести контур некоторой фигуры, не отрывая карандаша от бумаги и не обводя ни одной линии контура дважды, т.е. нарисовать «одним росчерком». Такие контуры образуют так называемые уникурсальные графы.
Задаче о семи кёнигсбергских мостах Леонард Эйлерпосвятил целое исследование, которое в 1936г. было представлено в Петербургскую академию наук.
Издавна среди жителей Кенигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие Кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кенигсберга это невозможно).
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда четно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Что такое граф?
Слово «граф»в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. ГРАФ – это фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек. Точки называются вершинами, а отрезки – ребрами графа. В процессе решения задач по математике заметили, что удобно изображать объекты точками, а отношение между ними отрезками или дугами. С графами связано большое число комбинаторных задач.
Граф — абстрактный математический объект, представляющий собой множество вершинграфа и набор рёбер, то есть соединений между парами вершин. Например, за множество вершин можно взять множество аэропортов, обслуживаемых некоторой авиакомпанией, а за множество рёбер взять регулярные рейсы этой авиакомпании между городами.
Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки.
В математической теории графов — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.
Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах
Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло и электросети. Помогают графы в решении математических и экономических задач.
Состав графа
Граф состоит из вершин, связанных линиями. Направленная линия (со стрелкой) называется дугой. Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторых вершин и входящая в нее же, называется петлей.
Задача о Кёнигсбергских мостах
Ч
ерез город Калининград, раньше он назывался Кенигсберг, протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рис. 1.
Рис. 1 Рис. 2.
Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощенную схему мостов. Получился граф, вершины которого – части города, разделенные рекой, а ребра – мосты (рис. 2).
Попробуйте провести линии по всем ребрам - "мостам", не отрывая карандаша от бумаги. У кого получилось? Таких нет? У Эйлера тоже не получилось. А вы знаете почему? Оказывается, все дело в числе ребер, сходящихся в вершине. Давайте посчитаем, сколько ребер сходится в каждой вершине графа. Напишите рядом с каждой вершиной число, отражающее количество ребер, в ней сходящихся, и назовем вершину четной или нечетной в зависимости от того, какое число, четное или нечетное, стоитрядом. Итак, в вершине А сходится 5 ребер, в вершине В - 3, в вершине С - 3, в вершине Д - 3. Какими являются все эти вершины? (Нечетными.)
Леонард Эйлер сформулировал правило:
Обход возможен:
ЕСЛИ все вершины – четные, и его можно начать с любого участка.
ЕСЛИ 2 вершины – нечетные, а остальные четные, но его нужно начать с одной из нечетных вершин.
Обход невозможен:
Если нечетных вершин больше 2.
В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Практическая часть
Решение логических задач методом графов
Граф – множество точек, изображенных на плоскости, некоторые пары из которых соединены отрезками.
Выделяем из условия задачи главное – объекты и отношения между ними, при этом объекты будем изображать точками, а соответствия между ними отрезками.
Сплошными - два объекта, соответствующие друг другу.
Штриховыми – два объекта, не соответствующие друг другу.
Задачи, решаемые с помощью графов.
1. Любители мультфильмов:
Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?
Рассмотрим метод графов на примере решения задачи:
Рассмотрим множество людей: мама, папа, сын и множество мультфильмов «Ну, погоди!», «Покемоны», «Том и Джерри». Обозначим элементы этих двух множеств точками:
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Заметим, что по условию задачи у человека только один любимый мультфильм. Учитывая данные задачи, получаем следующую схему:
Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух множеств.
Правило: если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
Теперь мы установили, что папа любит мультфильм «Ну, погоди!», сын – «Покемоны». В обеих множествах остается только по одной точке, следовательно, мама любит мультфильм «Том и Джерри». Задача решена.
М ама папа сын
«Ну погоди!» «Покемоны» «Том и Джерри»
ОТВЕТ:
Папа любит мультфильм «Ну, погоди!», сын – «Покемоны», мама любит мультфильм «Том и Джерри».
2. Любители музыки:
В клубе «Отдых» познакомились 3 любителя клубной музыки видов техно, хаус, рейв. Один говорит: «Вы какую музыку больше любите? Я техно люблю!». Другой ответил, что любит Хаус, а третий сказал, что не любит ни техно, ни Хаус, но зато обожает рейв. Интересно то, что все они были в банданах и рубашках желтого, белого и черного цветов, но цвет банданы и рубашки совпадал только у любителя техно. А у любителя хаус ни рубашка, ни бандана не были белыми. А любитель рейв был в желтой рубашке. Определите цвет рубашек и бандан каждого из любителей клубной музыки.
Решение:
Рассмотрим множество видов клубной музыки: техно, хаус, рейв и множество рубашек и бандан желтого, белого и черногоцветов. Обозначим элементы этих двух множеств точками:
Т ехно Хаус рейв
Желтая рубашка белая рубашка черная рубашка
Черная бадана белая бандана желтая бандана
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Учитывая данные задачи, получаем следующий граф:
Т ехно хаус рейв
Желтая рубашка белая рубашка черная рубашка
Черная бандана белая бандана желтая бандана
Используя правило: если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
Т ехно хаус рейв
Желтая рубашка белая рубашка черная рубашка
Черная бандана белая бандана желтая бандана
Ответ:
У любителя «техно» рубашка и бандана белого цвета; у любителя «Хаус» черная рубашка и желтая бандана; у любителя «рейв» желтая рубашка и черная бандана.
3. Три поросёнка:
Жили-были на свете три поросёнка, три брата: Ниф - Ниф, Наф - Наф, Нуф - Нуф. Построили они три домика: соломенный, деревянный и кирпичный. Все три брата выращивали возле своих домиков цветы: розы, ромашки и тюльпаны. Известно, что Ниф - Ниф живет не в соломенном домике, а Наф - Наф – не в деревянном; возле соломенного домика растут не розы, а тот, у кого деревянный домик, выращивает ромашки. У Наф - Наф аллергия на тюльпаны, поэтому он не выращивает их. Узнайте, кто в каком домике живет и какие цветы выращивает.
Решение:
Рассмотрим множество поросят: Ниф - Ниф, Наф - Наф, Нуф - Нуф и множество домиков соломенный, деревянный и кирпичный и цветов розы, ромашки и тюльпаны, возле них. Обозначим элементы этих двух множеств точками:
Н иф - Ниф Наф - Наф Нуф - нуф
Соломенный дом деревянный дом кирпичный дом
тюльпаны ромашки розы
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Учитывая данные задачи, получаем следующий граф:
Н иф - Ниф Наф - Наф Нуф - нуф
Соломенный дом деревянный дом кирпичный дом
тюльпаны ромашки розы
Используя правило: если какая-то, точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
Н иф - Ниф Наф - Наф Нуф - нуф
Соломенный дом деревянный дом кирпичный дом
тюльпаны ромашки розы
Ответ:
Наф - Наф живет в кирпичном домике и выращивает розы; Ниф - Ниф живет в деревянном домике и выращивает ромашки; Нуф - Нуф живет в соломенном домике и выращивает тюльпаны.
4. Друзья
Встретились три друга - Белов, Серов и Чернов. Чернов сказал другу, одетому в серый костюм: «Интересно, что на одном из нас белый костюм, на другом - серый и на третьем — черный, но на каждом костюм цвета, не соответствующего фамилии». Какой цвет костюма у каждого из друзей?
5. Подруги:
Когда три подруги — Надя, Валя и Маша — вышли гулять, на них были белое, красное и синее платья. Туфли их были тех же трех цветов, но только у Нади цвета туфель и платья совпадали. При этом у Вали ни платье, ни туфли не были синими, а Маша была в красных туфлях. Определите цвет платьев и туфель каждой из подруг.
6. Лучшие друзья
Встретились трое лучших друзей: Белов, Рыжов и Чернов. Брюнет сказал Белову: "Любопытно, что ни у кого из нас цвет волос не соответствует фамилии, да и ты не брюнет".
Какой цвет волос у каждого из друзей?
7. Ученицы:
Три ученицы – Валя, Галя и Катя – пришли в театр в платьях разного цвета: одна – в белом, другая – в сером, а третья – в черном. Катя была не в черном, Валя не в черном и не в сером. Угадай, в какое платье каждая из них была одета.
8. Возраст детей
В семье четверо детей. Им 5, 8, 13 и 15 лет, а зовут их Аня, Юра, Света и Лена. Сколько лет каждому из них, если одна девочка ходит в детский сад, Аня старше, чем Юра, а сумма лет Ани и Светы делится на три?
9. Олимпиада
Катя, Боря, Витя и Юра заняли первые четыре места на олимпиаде. Катя не заняла ни первое, ни последнее место, Боря занял второе место, Витя оказался в числе первых трех призеров. Какое место на олимпиаде занял Юра?
10. Кто на чём ездит?
Три друга Алеша, Боря и Витя едут после школы домой на различном транспорте: автобусе, троллейбусе, трамвае. Однажды после уроков Алеша пошел проводить своего друга домой до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадку». Кто на чем ездит домой?
Решение:
Рассмотрим множество друзей: Алеша, Боря и Витя и множество транспорта: автобус, троллейбус, трамвай. Обозначим элементы этих двух множеств точками:
А лёша Боря Витя
Автобус Троллейбус Трамвай
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Учитывая данные задачи, получаем следующий граф:
А лёша Боря Витя
Автобус Троллейбус Трамвай
Используя правило: если какая-то, точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
А лёша Боря Витя
Автобус Троллейбус Трамвай
Ответ:
Леша ездит на трамвае, Боря - на автобусе, Витя – на троллейбусе.
11. Клоуны
Клоуны БАМ, Бим, Бом вышли на арену в красной, синей и зеленой рубашках. Их туфли тоже были этих трех цветов. Туфли и рубашка Бима были одного цвета. на Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Какого цвета были туфли и рубашка у Бома и Бима?
12. Мушкетёры:
Атос, Портос, Арамис и Д’Артаньян – четыре талантливых молодых мушкетёра. Один из них лучше всех сражается на шпагах, другой не имеет равных в рукопашном бою, третий лучше всех танцует на балах, четвертый без промаха стреляет с пистолетов. О них известно следующее:
• Атос и Арамис наблюдали на балу за их другом – прекрасным танцором.
• Портос и лучший стрелок вчера с восхищением следили за боем рукопашника.
• Стрелок хочет пригласить в гости Атоса.
• Портос был очень большой комплекции, поэтому танцы были не его стихией.
Кто чем занимается?
Решение:
Рассмотрим множество четырех талантливых молодых мушкетёров: Атос, Портос, Арамис и Д’Артаньян и множество их занятий: стрелок, рукопашник, шпажист и танцор. Обозначим элементы этих двух множеств точками:
А тос Портос Арамис Д’Артаньян
Стрелок Рукопашник Шпажист Танцор
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Учитывая данные задачи, получаем следующий граф:
А тос Портос Арамис Д’Артаньян
Стрелок Рукопашник Шпажист Танцор
Используя правило: если какая-то точка оказывается соединенной с двумя (в нашем случае тремя) точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:
А тос Портос Арамис Д’Артаньян
Стрелок Рукопашник Шпажист Танцор
Ответ:
Арамис – стрелок; Д’Артаньян – танцор; Портос – шпажист; Атос – рукопашник.
Ответы:
Папа любит мультфильм «Ну, погоди!», сын – «Покемоны», мама любит мультфильм «Том и Джерри».
У любителя «техно» рубашка и бандана белого цвета; у любителя «Хаус» черная рубашка и желтая бандана; у любителя «рейв» желтая рубашка и черная бандана.
Наф-Наф живет в кирпичном домике и выращивает розы; Ниф-Ниф живет в деревянном домике и выращивает ромашки; Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.
Чернов в белом костюме, Белов - в сером, Серов - в черном.
У Нади туфли и платье синего цвета; у Вали туфли белые, платье красное; у Маши туфли красные, платье белое.
Белов – рыжий, Чернов – блондин, Рыжов – брюнет
Валя – в белом, Галя – в черном, Катя – в сером
Анне – 13 лет, Юре – 8 лет, Свете – 5 лет, лене – 15 лет.
Последнее (четвертое)
Леша ездит на трамвае, Боря - на автобусе, Витя – на троллейбусе.
У Бома - синяя рубашка и зеленые туфли, у Бама- зеленая рубашка и синие туфли.
Арамис – стрелок; Д’Артаньян – танцор; Портос – шпажист; Атос – рукопашник.
Одним росчерком
Задача № 1
Какие буквы русского алфавита можно нарисовать одним росчерком?
Ответ: Б, В, Г, 3, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я.
Задача № 2
К акие фигуры можно нарисовать одним росчерком?
Ответ: пятиконечная звезда
Применение графов в повседневной жизни.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов находит применение в жизни. С их помощью упрощается решение математических задач, головоломок, задач на смекалку.
Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
Типичными графами на географических картах изображения железных дорог.
Графы есть и на картах звездного неба.
Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
ЗАКЛЮЧЕНИЕ
Теория графов в настоящие время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графов описываются многие объекты и ситуации: схемы электрических и электронных приборов, химические молекулы, отношение между людьми и другое.
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ.
В математике даже есть специальный раздел, который так и называется: «Теория графов».
В данной работе мы познакомились с новым понятием «граф», рассмотрели историю возникновения графов и научились применять теорию графов при решении различных математических и логических задач.
В ходе исследования были выявлены особенности изображения некоторых рисунков в виде графов, рассмотрены простейшие правила построения графов и их виды.
Также было показано практическое применение графов на конкретных примерах, используемые в повседневной жизни. Были решены математические и логические задачи с применением графов.
Таким образом, выдвинутая гипотеза нашла в работе свое подтверждение, а все поставленные цели и задачи достигнуты.
Приемы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, сокращающих нагрузку на память.
АНКЕТА
1) Знаете вы что такое графы?
2) Слышали вы про задачи, решаемые с помощью графов?
3) Знаете вы как решать задачи с помощью графов?
4) Хотите узнать, как решать задачи с помощью графов?
5) Хотите научиться решать задачи с помощью графов?
СПИСОК ЛИТЕРАТУРЫ
«Россыпи головоломок». Ст. Бар М., «Мир», 1987 г.
Твое свободное время. Занимательные задачи, опыт, игры. М., «Детская литература»,1975
Графы и их применение, О. Оре, Москва, 1979г.
Интернет
Внеклассная работа по математике, З. Н. Альхова, А.В. Макеева, Саратов, 2003 г.