Научно-практическая конференция молодых исследователей «Шаг в будущее» Секция «Алгебра» Графы и их применение. Выполнила: Натоко Ирина, ученица 10 класса ГСОШ Руководитель: Сороковикова И.Г учитель математики

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

Что называется графом? Граф- это набор точек, некоторые из которых соединены линиями. Точки - вершины графа, отрезки – ребра. отрезки – ребра. Основание теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Основание теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кенигсбергских мостах.

Виды графов. Полные графы. Простой граф, в котором любые две вершины смежных, называется полным графом Регулярные графы. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Платоновы графы. графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Двудольные графы. Полный двудольный граф называется звездным графом. Вполне несвязные графы.Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Связные графы. Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Циклические графы и колеса. Связный регулярный граф степени 2 называется циклическим графом (или циклом) Деревья. Деревом называется любой связный граф, не имеющий циклов.

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

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

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

Старинные задачи. 1. «Сабли Магомета»: Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов Луны знак. 2.«Некто, очень богатый человек, давал миллион рублей каждому, кто начертит следующую фигуру. Но при вычерчивании ставилось одно условие. Требовалось, чтобы эта фигура была вычерчена одним непрерывным росчерком. По проведенной линии нельзя уже было пройти второй раз.

Задача на нахождение кратчайшего пути. Задача о волке, козе и капусте. Коза, капуста и волк находятся на берегу реки; перевозчику надо переправить их через реку, но его лодка так мала, что он может взять с собой не более одного из этих трех «пассажиров». По очевидным причинам нельзя оставлять без надзора волка с козой, а козу с капустой. Как должен поступить перевозчик?

Примеры приложений теории графов. Связи (информационные, управляющие, технологические и др.) между ними. Элементы организационной системы Модели организационных структур Отношение между ними Группы людей Модели коллективов и групп Последовательности выполнения операций и распределения ресурсов Управление проектами Потоки материальных и финансовых ресурсов Участники обменной схемы Обменные схемы Потоки сырья, материалов и продукции Заводы, цеха, станки и т.д. «Технологические задачи» Дороги Пункты«Транспортные» задачи Дуги или ребра ВершиныВиды

Бабушка Александра Григорьевна Пескова (Соколова) Дедушка Павел Александрович Песков Бабушка Людмила Алексеевна Натоко (Капустина) Дедушка Николай Анатольевич Натоко Папа Анатолий Николаевич Натоко Я, Ирина Анатольевна и мой брат Николай Анатольевич Натоко. Мама Галина Павловна Натоко (Пескова) Прабабушка Анастасия и прадедушка Григорий Соколовы Прабабушка Татьяна и прадедушка Александр Песковы Прабабушка Антонина и прадедушка Михаил Капустины Прабабушка Евдокия и прадедушка Анатолий Натоко Генеалогическое древо семьи Натоко.

План – схема микрорайона. 250 м 205 м 40 м 30 м 300 м 200 м 50 м 180 м 210 м 50 м 80 м 100 м

3 км 285 м Итого 210 м Производственная– ул.Лесная Мира- Производственная мХ-Намсараева - Мира м Ул.Саянская- Х- Намсараева ампер.Саянский– ул.Саянская м Дзержинского– пер.Саянский м Пушкина - Дзержинского м Ленина - Пушкина м 40 лет Победы - Ленина м Лесная – 40 лет Победы м Пушкина - Лесная м Саянская – Пушкина м Лесная - Саянская 1-2 Расстояни е Улица Маршрут Вывод: Вычерченный граф представляет собой схему с минимальным прохождением дважды по одной улице. Данный маршрут – самый оптимальный, позволяющий обойти весь участок, преодолевая наименьшее расстояние. Таким образом, суммарная длина маршрута составила 3 км 285 м.

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