Работа выполнена ученицей 6 а класса Угримовой Нелли Руководитель Богдановская В.М. - презентация

1 Работа выполнена ученицей 6 а класса Угримовой Нелли Руководитель Богдановская В.М.

2 Цели и задачи Изучить научно- популярную литературу по данному вопросу. Учиться решать задачи с использованием графов Исследовать выполнение Графов для выяснения родственных отношений Проанализировать результаты проведенных экспериментов

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

4 Задача Льюиса Кэрролла Поросята жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5. Однажды эти поросята перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. На рисунке 6 изображена очередная попытка проложить такие тропы.

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

6 Задачи 1 Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, К-В, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М? З К П В УМ СЮ Ответ: с З до М добраться нельзя.

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

8 Задачи 4 Пять мальчиков: Андрей, Борис, Василий, Григорий и Дмитрий - разъехались на каникулы. Стали переписываться: Андрей и Дмитрий, Василий и Григорий, Григорий и Борис. Может ли сообщение о жизни Бориса дойти до Василия? До Андрея? А Д ВГ Б Ответ: от Бориса до Василия может; до Андрея не может.

9 Иерархия это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами ( системами с иерархической структурой). Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор заместитель учителя ученики

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

11 Задачи 5 Женя пытался представить родственные отношения в своей семье в виде графа. Вершинами он отмечал некоторых членов семьи, а ребрами соединял тех.кто являлся отцом и сыном. Результаты его изысканий представлены на рисунке. Не допустил ли женя ошибки? Ответ: Женя допустил ошибку.

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

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

14 Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.

15

16 Вывод: В настоящей исследовательской работе рассмотрены математические графы, области их применения, решено несколько задач с помощью графов. Я узнала, что графы достаточно широко применяются в математике, технике, экономике, управлении. Графы предназначены для активизации знаний по школьным предметам. Кроме того, работая над исследовательской работой, я освоила работу на компьютере.Научилась пользоваться программой составления генеалогического древа Таким образом, задачи исследовательской работы выполнены.