Министерство образования и науки Республики Калмыкия
Отдел образования Юстинского районного муниципального образования
Муниципальное казенное общеобразовательное учреждение
«Харбинская средняя общеобразовательная школа»
Районная научно-практическая конференция школьников
«От исследования – к научному поиску»
секция: естественно-научная.
Графы в нашей жизни.
Автор работы: Наранов Денис Алексеевич.
МКОУ «Харбинская средняя общеобразовательная школа»,класс 8
Руководитель:
Арлдаева Роза Сангаджигаряевна, учитель математики
МКОУ «Харбинская средняя общеобразовательная школа».
Харба, 2018г
В истории черпаем мы мудрость, в поэзии - остроумие, в математике - проницательность.
Ф.Бэкон
Впервые с понятием “граф” я встретился при решении олимпиадных задач по математике. Теория графов заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Трудности в решении этих задач объяснялись отсутствием этой темы в обязательном курсе школьной программы. Возникшая проблема стала главной причиной выбора темы данной исследовательской работы. Я решил подробно изучить всё, что связано с графами. Как широко используется метод графов и насколько важен он в жизни людей. Решая задачи с помощью графов, я решил понять, где ещё встречаются графы в нашей жизни, и на практике применить теорию графов составив генеалогическое древо своей семьи.
Актуальность. Теория графов в настоящее время является интенсивно развивающимся разделом математики. Теория графов находит применение в различных областях современной математики и ее многочисленных приложениях, в особенности это относится к экономике, технике, к управлению. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту.
Гипотеза:
Исходя из гипотезы, выдвинул следующие цели и задачи исследования.
Цель: выяснить особенности применения теории графов при решении задач и в практической деятельности, проверить выполнение «Графов» на родословных.
Для реализации поставленной цели, мною были выдвинуты следующие задачи:
1.познакомиться с историей теории графов;
2.изучить основные понятия теории графов и виды графов;
3.рассмотреть способы решения задач с помощью графов;
4. показать применение теории графов в различных областях жизни человека;
5. создать генеалогическое древо моей семьи.
Объектом исследования являются математические графы.
Методы исследования:
- теоретический (изучение литературы по данной теме, сбор информации с использованием интернет ресурсов);
- практический (решение задач с применением теории графов, составление генеалогического древа семьи)
Практическая значимость. В своей исследовательской работе по математике "Графы в нашей жизни" я постараюсь выяснить особенности применения теории графов при решении задач и в практической деятельности. Результатом моей исследовательской работы по математике о графах станет генеалогическое древо моей семьи.
II. Основная часть.
Глава 1. Знакомство с графами
1.1. История графов.
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых.
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук).Он предложил изящное решение знаменитой задачи о семи Кенигсбергских мостах в 1736 году, а также придумал общий метод решения подобных задач. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков - К. Берж, О. Оре, А. Зыков. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.
Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топографии и комбинаторики. В середине XIX века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. Окончательно как математическая дисциплина теория графов оформилась в 1936г. после выхода монографии Д. Кёнига «Теория конечных и бесконечных графов». Широкое развитие теория графов получила с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники.
1.2. Понятие о графах.
Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др.
Виды графов:
- граф, состоящий из «изолированных» вершин, называется нулевым графом.
- графы, в которых не построены все возможные ребра, называются неполными графами.
- графы, в которых построены все возможные ребра, называются полными графами.
Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.
Стрелка от одной работы к другой на графе, изображенном на рисунке, означает последовательность выполнения работ.
Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д.
Степени вершин и подсчет числа ребер.
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.
Закономерности, присущие определенным графам.
Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым.
Закономерность 3. Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.
Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.
Граф называется несвязным, если это условие не выполняется. При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
Циклом называется путь, в котором совпадают начало с концом.
Деревом называется любой связный граф, не имеющий циклов.
Для каждой пары вершин дерева существует единственный путь, их соединяющий.
Этим свойством пользуются при нахождении всех предков в генеалогическом дереве. В дереве число вершин на одну больше числа ребер.
Глава 2. Применение графов.
2.1. Применение графов при решении задач.
Задачи на вычерчивание фигур одним росчерком.
Задача 1. О Кенигсбергских мостах. Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу.
Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту. Благодаря этой задаче была создана теория графов.
Мосты через реку Прегель расположены как на рисунке.
Рассмотрим граф, соответствующий схеме мостов
Решение: было найдено русско-немецким математиком Леонардом Эйлером(1736 год).
Его рассуждения заключались в следующем:
1) Число нечётных вершин графа должно быть чётно.
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
4) Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Логические задачи.
Задача 3. В соревнованиях по борьбе, проходящих по олимпийской системе, участвуют 20 борцов. За какое минимальное время можно провести соревнование, если в спортивном зале есть только три борцовских ковра, и на каждую схватку, включая разминку и отдых, отводится час?
Изобразим схему соревнований с помощью древа.
Решение: одна из возможных схем приведена на рисунке.
Ответ: На соревнование уйдет 7 часов.
Задача 6. В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение: Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).
Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.
Решение: Ситуацию в каждый момент можно описать тремя числами.
В результате получаем два решения:
одно в 7 ходов, другое в 8 ходов.
2.2. Генеалогическое древо – один из способов применения графов
Представьте, что за одним столом собрались несколько больших семей. Каждый гость хочет рассказать о своей семье побольше.
Через несколько минут, скорее всего, у слушателей голова пойдет кругом от обилия имен, отчеств, фамилий, дат рождения и другой информации, которой захочется поделиться каждому гостю с собравшимися.
И здесь на помощь опять приходят графы.С их помощью можно построить генеалогическое древо, в котором при желании указать всю многочисленную родню до седьмого колена.
Деревья – очень удобный инструмент наглядного представления информации самого разного вида.
2.3. Описание исследования и составление генеалогического древа семьи
Последовательность действий в исследовании была следующей:
1. Создать модели «Древо жизни» и сетевого графа;
2. Провести опрос родственников (родителей, дедушки, бабушки, тети);
3. Изучить модели составления графов;
4. Создать модели графов.
Для результатов исследования я использовал следующие формы записей:
Для интервью: вопросами и ответами на них.
Для моделирования: создание рисунков.
После проведения исследования я приступил к его первичной обработке, анализу и представлению результатов исследования:
1. Построил образец графа «Древо жизни».
2. Создал граф с помощью полученной информации из интервью.
В приложении приведено генеалогическое древо моей семьи. Я ограничился только близкими родственниками, чтобы не перегружать рисунок.
III. Заключение.
Выполняя эту работу, я изучил один из интереснейших вопросов теории графов, я рассмотрел математические графы, области их применения, решил несколько задач с помощью графов. Научился использовать «графы» для выяснения родственных отношений. Изучил метод «графов», как один из методов решения логических задач.
Итак, для того чтобы научиться решать задачи, надо разобраться в том, что собой они представляют, как они устроены, из каких составных частей они состоят, каковы инструменты, с помощью которых производится решение задач.
Решая практические задачи с помощью теории графов мне стало ясно, что в каждом шаге, в каждом этапе их решения необходимо применить творчество.
С самого начала, на первом этапе, оно заключается в том, что нужно суметь проанализировать и закодировать условие задачи.
Второй этап – схематическая запись, которая состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.
Я убедился, что графы достаточно широко применяются в экономике, управлении, технике. Также теория графов применяется в программировании.
В моей исследовательской работе по математике на тему "Графы в нашей жизни" рассмотрены математические графы, области их применения, решено несколько задач с помощью графов.
Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты). Кроме того, работая над работой, я освоил работу на компьютере в текстовом редакторе WORD. Изучая этот материал, я узнал области применения теории графов и сделал вывод, что этот раздел математики является одним из важнейших, который используется в нашей повседневной жизни часто незаметно для нас.
Таким образом, задачи исследовательской работы выполнены.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данной работы. В дальнейшем я собираюсь продолжить изучение теории графов, потому что этот раздел математики показался мне интересным и полезным.
Литература
1. Берж К. "Теория графов и ее применение", М., ИЛ, 1962г.
2. Березина Л.Ю. "Графы и их применения", М. , 1979г.
3. Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 1969г.
4. Ю. Нестеренко, С. Олехник, М. Потапов “Лучшие задачи на смекалку”.
5. Ресурсы сети Интернет.
6.Коннова Л.П. Знакомтесь, графы. – Самара, 2001.
7.Лыкова И.А. Логические задачки – М.: Карапуз, 2000.
8.Математика. №11,2011. Методическая газета
9.Математика. №3, 2013 . Методическая газета
10.А.В.Фарков, Готовимся к олимпиадам по математике.Москва,2006г
11. Харари Ф. «Теория графов».М.,1973.
Приложение 1. Генеалогическое древо семьи Наранова Дениса.
Приложение 2. Применение графов в различных областях жизни людей
Как уже было сказано, графы имеют очень широкое применение: с их помощью выбирают наиболее выгодное расположение зданий, графами представлены схемы метро. Далее представлены некоторые примеры применения графов.
1. Лабиринт.
Исследовать лабиринт - это найти путь в этом графе.
Вершинами здесь обозначены тупики, а отрезками – проходы лабиринта.
2. Генеалогическое древо.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. 
3. Блок-схема программы
Графами являются блок – схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.
4. Схема цепей дежурного освещения
Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.
5. Схемы авиалиний
6. Участок московского Метрополитена.
7. Социограммы
Социограммы (в психологии при исследовании межличностных отношений в группах).
8. Схема железных дорог
Вершины – железнодорожные станции, а рёбра – железнодорожные пути.
9. Химия. Теория графов позволяет точно определить и пояснить некоторые основные понятия химии: структуру, конфигурацию, определять число теоретически возможных изомеров органических соединений. Молекулярный граф — связный неориентированный граф, находящийся во взаимно-однозначном соответствии со структурной формулой химического соединения таким образом, что вершинам графа соответствуют атомы молекулы, а рёбрам графа — химические связи между этими атомам
10.Созвездия
Графы есть и на картах звездного неба.
Это созвездия.
11. Физика. Одной из наиболее сложных и утомительных задач для радиолюбителей считается конструирование печатных схем.
Печатная схема - это пластинка из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
12. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов».
Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.
Аннотация.
Главной целью школьного математического образования является развитие умственных способностей учеников. Нужен переход от информационно- объяснительной технологии к деятельно-развивающей, направленной на развитие личностных качеств каждого школьника. Важными должны стать не только усвоенные знания, но и сами способы усвоения и переработки учебной информации. Человек быстро забывает те знания, которыми постоянно не пользуется, но с ним навсегда остается логическое развитие
Работа состоит из введения, основной части, заключения и списка использованной литературы. Во введении указываются цели и задачи исследования, обосновывается актуальность выбранной темы. В теоретической части исследования ученик изучил литературу по данной теме, узнал, в каких областях науки используется теория графов, составил генеалогическое древо своей семьи. В заключении даны основные выводы на основании исследованного материала. Работа была представлена на школьной научно-практической конференции.
