Исследовательская работа ««Графы» в моей родословной» (6 класс)

Краткая аннотация

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

Введение

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

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

Разработанность проблемы: 1) книга Березина Л.Ю. знакомит читателя с основами теории графов и ее приложениями;

2) Книга Р. Уилсона является вводным курсом в теорию графов; вместе с тем она затрагивает целый ряд интересных и сложных задач;

3) В интернет источниках даны понятия связности графа, дерева и генеалогического дерева;

4) в книга Оре графы в большей степени сохраняют своё наглядное, геометрическое содержание, как системы точек, соединённых линиями;

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

Гипотеза: если удается использовать теорию графов, то представление родословной упрощается.

Цель: представление моей родословной , используя «Графы».

Задачи:

1)Изучить литературу по данному вопросу.

2)Исследовать выполнение «Графов» для выяснения родственных отношений.

Объектом исследования: является теория графов, и ее приложения

Предметом исследования: родословная семьи.

Методы: теоретические: изучение литературы по теории графов; анализ и обобщение изученной информации.

Эмпирические: представление родословной в виде графа.

Практическая значимость: полученная информация по результатам исследовательской работы может быть использована на факультативных занятиях.

Новизна

Представление генеалогического древа семьи в виде графа придает наглядность и простоту.

Понятие графа

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

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

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

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

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

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

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

• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Определения теории графов

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

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

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

Циклом называется путь, в котором совпадают начальная и конечная точка.

Пример: граф с шестью вершинами и семью рёбрами

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

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.K₂: 1

K₃: 3

K₄: 6

K₅: 10

K₆: 15

K₇: 21

K₈: 28

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

Длиной пути, проложенного на цикле, называется число ребер этого пути.

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

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

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

Структура дерева.

Практическая часть

Задача: «В летней научной школе СФУ пять девочек - Лена ,Света ,Маша ,Катя и Настя выбирают себе браслеты пяти цветов :зелёный , синий ,красный ,белый о оранжевый. Лена любит зелёный и синий цвета . Кате нравится синий и белый браслет , Маша взяла белый браслет , Настя отдала предпочтение зелёному , синему и оранжевому браслетам , Кому достался браслет оранжевого цвета , если известно ,что у всех девочек браслеты оказались разных цветов». Решая эту задачу с помощью графов я нашла быстрый ответ. И я поняла, что представление родословной будет более нагляднее в виде графов.

Трофим Власович

Ефим Пётр (погиб на ВОВ) Егор (погиб на ВОВ)

Михаил Иван (1924) Клавдия

(погиб на ВОВ)

Ефим Михаил ЛюбовьГалинаГеоргийЕкатерина Николай Анна Владимир

(1949) (1952) (1954) (1956) (1959) (1961) (1963) (1966) (1968)

Ирина Иван Ольга

Михаил Иванович(1952)

Татьяна(1974) Игорь(1979) Оксана(1985)

Ирина Мария Кристина Владислав Сергей Адрей(1999)

(1992) (1995) (1994) (1998) (2010) Анастасия(2001)

Дарья (2011)

Константин(2015)

Любовь Ивановна(1954)

Иван(1976) Александр(1979) Светлана(1980) Николай(1991)

Кирилл (2004) Константин(2012)

Галина Ивановна(1956)

Анатолий (1976) Наталья (1978) Леонид (1987)

Кристина Дарья Виолетта Алёна Вадим Ксения

(1995) (1999) (2007) (1997) (2005) (2013)

Георгий Иванович(1959)

Надежда(1985) Владимир (1987)

Виктор (2005) Юлия (2007) Дарина(2014)

Екатерина Ивановна(1961)

Любовь (1980) Виталий(1982) Ганна(1991)

Валентина(я) (2003) Рада(2011) Юрий (2012) Андрей(2008)

Николай Иванович(1963)

Николай(1985)

Анна Ивановна (1966)

Людмила (1985) Алексей (1989)

Анна (2005) Потап(1012)

Владимир Иванович(1968)

Анастасия(19 ) Владислав(19 )

Кира(2011)

Заключение

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

Научилась использовать «графы» для выяснения родственных отношений. Получила, что каждая вершина связана только с верхней и не связана больше ни с чем. В дальнейшем я собираюсь продолжить изучение теории графов, потому что этот раздел математики стал мне интересным и полезным. Кроме того, работая над исследовательской работой, я освоила работу на компьютере в текстовом редакторе Word и Рower Point. Я считаю, что задачи исследовательской работы выполнила.

Литература

1.Березина Л.Ю «Графы и их применение»: Пособие для учителей. - М.: Просвещение, 1979. -143с.

2. Гарднер М. «Математические досуги» М.: Мир,1972

3. Коннова Л.П. Знакомтесь, графы. - Самара, 2001.

4. Оре О. «Графы и их применение PDF» М. : Мир, 1965.- 175 с

5.Савин А.В. «Энциклопедический словарь юного математика». 2-е изд., - М.: Педагогика, 1989 - 352 с

6. Уилсон Р. « Введение в теорию графов» М.: "Мир", 1977. - 208 с

7. slovar.cc/enc/bse/1990090.html

8. nashol.com/tag/teoriya-grafov/

9. https://ru.wikipedia.org/wiki</</p>

10. matmetod-popova.narod.ru/theme213.htm