Нефтегазовая промышленность

Исследовательская работа «Круги Эйлера и теория графов в решении задач школьной математики и информатики. Исследовательская работа Исследовательская работа графы и их применение

31.07.2021

Российская научно-социальная программа для молодежи и школьников

«Шаг в будущее»

ХV Районная научно-практическая конференция «Шаг в будущее»

Графы и их применение

Исследовательская работа

МБОУ «Шелеховский лицей», 10 класс

Руководитель: Копылова Н.П.

МБОУ «Шелеховский лицей»,

учитель математики.

Научный руководитель:

Постников Иван Викторович,

младший научный сотрудник

Института систем энергетики им. Л.А. Мелентьева

Сибирского отделения Российской академии наук

г. Шелехов - 2012

Введение, задачи, цель…………………………………………………………… 3

Основная часть……………………………………………………………………. 4

Заключение……………………………………………………………………..... 10

Список литературы…………………………………………………………….... 11

Введение.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнинга в 30-е годы XX столетия.

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

    Дать определение графов и его составляющих

    Рассмотреть некоторые виды графов и их свойства

    Рассмотреть основные положения теории графов, а также теоремы, лежащие в основе данной теории с доказательством

    Решить ряд прикладных задач с помощью графов

    Определить области применения теории графов в окружающей действительности

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

Основная часть.

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

Точки иначе называют вершинами, отрезки – рёбрами графа.

Виды графов:

В общем смысле граф представляется как множество вершин, соединённых рёбрами. Графы бывают полными и неполными. Полный граф - это простой граф, каждая пара различных вершин которого смежна. Неполный граф – это граф, в котором хотя бы 2 вершины не смежны.

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

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

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

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

С вершинами графов связаны 4 теоремы, докажем их с помощью задач:

№1.Участники пионерского слёта, познакомившись, обменялись конвертами с адресами. Докажите, что:

1) всего было передано четное число конвертов;

2)число участников, обменявшихся конвертами нечетное число раз, четное.

Решение. Обозначим участников слёта А 1 , А 2 , А 3 …., А n – вершины графа, а ребра соединяют на рисунке пары вершин, изображающих ребят, которые обменялись конвертами:

1) Степень каждой вершины А j показывает количество конвертов, переданных участником А j своим знакомым, значит общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ. А 1 + степ. А 2 + … + степ. А n-1 + степ. А n , N = 2р (р – число ребер графа), то есть N – четное число. Из этого следует, что было передано четное число конвертов;

2) Мы доказали, что N – четное, а N = степ. А 1 + степ. А 2 + …. + степ. А n-1 + степ. А n , т.е N – количество участников. Мы знаем, что сумма нечетных слагаемых должна быть четной, а это возможно только в том случае, если число нечетных слагаемых четно. Значит, что число участников, которые обменялись конвертами нечетное число раз, четное.

В ходе решения задачи доказаны две теоремы.

    В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. ∑ степ. А j = степ. А 1 + степ. А 2 + … + степ. А n = 2р, где р – число ребер графа Г, n – число его вершин.

    Число нечётных вершин любого графа чётно.

№2. Девять шахматистов проводят турнир в один круг. Покажите, что в любой момент найдутся двое закончившие одинаковое число партий.

Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим соответствующую ему вершину графа, соединим рёбрами попарно вершины, соответствующие шахматистам, которые уже сыграли между собой партию. Мы получили граф с девятью вершинами. Степень каждой вершины соответствует числу партий, сыгранных соответствующим игроком. Докажем, что в любом графе с девятью вершинами всегда есть хотя бы две вершины с одинаковой степенью.

Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2, …, 7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, …, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А со степенью 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых раны между собой.

Вернемся к задаче. Доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.

Решение этой задачи почти дословно повторяется в ходе доказательства следующей теоремы (только число 9 приходится заменить произвольным натуральным числом n ≥ 2).

    Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

№3. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.

Решение. Условие задачи переведем на язык графов. Пусть вершины графа – игроки, а каждое ребро означает, что соответствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степени. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная, либо только одна вершина степени 8.

В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: 0, 1, …, 7, 8. Но у такого графа степени вершин принимают только восемь разных значений, т.к. ровно две вершины имеют одинаковую степень. Следовательно, обязательно либо 0, либо 8 будет значением степени одной из вершин.

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

Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадают. Но такого графа не существует (теорема 3). Значит это предположение неверное.

Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень 8, а все остальные несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень 0, а остальные попарно различные степени. Этого тоже не может быть (теорема 3), т. е. и второе предположение неверное.

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

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

При решении этой задачи число 9 можно было заменить любым другим натуральным числом n › 2.

Из этой задачи можно вывести следующую теорему:

    Если в графе с n вершинами (n 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени n-1.

Эйлеров путь в графе - это путь, проходящий по всем рёбрам графа и притом только по одному разу.

№4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD; перечеркнем DК. Перечеркнем МО и МН; отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, HK и КО. Найдем единственно возможный при данном условии маршрут.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D – Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, H – Петуху, K – Констанжогло, O - Кошкареву.

№5. У Ирины 5 подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Какова вероятность, что Ирина пойдёт в кино с Верой и Полиной?

Переведем условие задачи на язык графов. Пусть вершинами графов будут подруги. А соответствие подруг одного варианта ребрами. Каждую вершину обозначаем первой буквой имени подруг. Вера – В, Зоя – З, Марина – М, Полина – П, Света – С. Получился граф:

Некоторые варианты повторяются, и их можно исключить. Перечеркнем повторяющиеся ребра. Осталось 10 возможных вариантов, значит вероятность того, что Ирина пойдёт в кино с Верой и Полиной равна 0,1.

Представление о плоском графе

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

Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа.

Плоский граф Плоское представление графа

Представителем не плоского графа является полный граф с пятью вершинами. Все попытки изобразить плоское представление этого графа обернется крахом.

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

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

Рисунок

Грани () и () являются соседями, а грани () и () соседями не являются.

Ребро () является мостом, соединяющим циклы - перегородкой.

Простой цикл, ограничивающий грань - граница грани.

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

Всякое представление графа либо не имеет бесконечной грани,

либо имеет только одну.

В плоском представлении дерева или леса бесконечной гранью является вся плоскость рисунка.

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин (в), число ребер (р), и число граней с учетом бесконечной (г) связаны соотношением: в – р + г =2.

Предположим, что граф А –связный плоский граф без перегородок. Для его плоского произвольного представления определим алгебраическое значение суммы в – р + г. Затем, данный граф преобразуем в дерево, которое содержит все его вершины. Для этого удалим некоторые ребра графа, разрывая при этом поочередно все его простые циклы, но так, чтобы граф остался связным и без перегородок. Обратим внимание, что при данном удалении одного ребра уменьшается число граней на 1, т.к. при этом либо 2 цикла преобразуются в 1, либо один простой цикл просто пропадает. Из этого следует, что значение разности р – г при этом удалении остается неизменным. Те ребра, которые мы удаляем, выделены пунктиром.

В получившемся дереве число вершин обозначим – вд, ребер – рд, граней – гд. Отматим равенство р – г = рд – гд. В дереве одна грань, значит р – г = рд – 1. Изначально мы задали условие, что при удалении ребер число вершин не меняется, т.е. в = вд. Для дерева справедливо равенство вд – рд = 1. Отсюда следует рд = в – 1, т.е р – г = в – 2 или в – р + г = 2. Формула Эйлера - доказана.

Кёнигсберг

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

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

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

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

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

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

На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта.

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

Заключение:

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

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

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

Список литературы:

1. «Графы и их применение» Л. Ю. Березина, издательство «Просвещение», Москва, 1979 г.

2. «Алгебра 9 класс» под редакцией С. А. Теляковского, издательство «Просвещение», Москва, 2010 г.

МОУ СОШ №6

Исследовательская работа.

«Графы»

Выполнил: Макаров Дмитрий

ученик 8 класса МОУ СОШ№6

Руководитель:

Кривцова С.А

Учитель математики и информатики

МОУ СОШ № 6

Г. Абдулино, 2007 г.


СОДЕРЖАНИЕ:
I.ВВЕДЕНИЕ


  1. Актуальность и новизна

  2. Цель и задачи

II. ОСНОВНАЯ ЧАСТЬ
1.Понятие о графах

2.Свойства графов

3.Применение графов
III.Практическая часть
IV.Заключение
V.Литература

VI.Приложение

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

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

Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами.

2. Цель и задачи.
Цель: рассмотреть решение задач с использованием «Граф», проверить выполнение
«Графов» на родословных.
Задачи:


  • Изучить научно- популярную литературу по данному вопросу.

  • Исследовать выполнение ”Графов’’ для выяснения родственных отношений

  • Проанализировать результаты проведенных экспериментов

II. Основная часть.

1.ПОНЯТИЕ О ГРАФАХ
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины , - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.

Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

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

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

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

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

Графы, изображенные на рисунках 4 и 5, как оказалось, играют решающую роль при определение для каждого графа – является ли он плоским, то есть может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик Л. С. Понтрягин независимо доказали, что если граф не является плоским, то в нем «сидит» хотя бы один из графов , изображенных на рисунках 4 и 5, то есть «полный пятивершинник» или граф «домики – колодцы».

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

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

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


Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф(внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: в А, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 3 2 1 = 24 способа.

Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях. Заметим, что граф на рис. 8 тоже можно сделать направленным , указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0),если наполним водой большую кастрюлю, или (5, 0, 3), если наполним меньшую кастрюлю.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

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

Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3 * 3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин.

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

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

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

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

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

Методы работы:
Сравнение и анализ результатов эксперимента.
Методика работы:

Для проведения исследований были выбраны:

А) Родословная моей семьи , архивы данных, свидетельства о рождении.

Б) Родословная князей Голицыных, архивы данных.
Я провел исследование, результаты исследования поместил в схемы и проанализировал их.
Методика 1.
Цель: проверить выполнение ’’Графов” на своей родословной.
Результаты: схема 1


Методика 2.
Цель: проверить выполнение ’’Графов’’ на родословной князей Голицыных.
Результат: схема 2
Вывод: я заметил, что родословная – типичный граф.

IV.ЗАКЛЮЧЕНИЕ

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

V.Литература.

1.Энциклопедический словарь юного математика / Сост.А.П.Савин.- М.: Педагогика, 1989

2. Квант № 6 1994Г.

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

4.В.А.Гусев, А. И.Орлов, А.А.Розенталь ’’Внеклассная работа по математике’’
5. И.Семакин’’ Информатика’’

Титов Максим

1. Рассмотреть все маршруты Нижнегорского района.

2. По данным маршрутов составить новые маршруты.

3. Показать являются ли новые маршруты Эйлеровыми графами.

4. Построить матрицу смежности для новых маршрутов.

5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.

Скачать:

Предварительный просмотр:

ВВЕДЕНИЕ ……………………………………………………………………………….3

РАЗДЕЛ 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ …………………………………5

  1. Основные понятия теории графов......…………………...……...…………5
  2. Характеристика Эйлеровых графов …………………………...…………...7
  3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)…………..8

РАЗДЕЛ 2. МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА ……………………..……10

  1. Маршруты Нижнегорского района …..…..……………………………….10
  2. Исследование маршрутов Нижнегорского района ……..………………..11

ЗАКЛЮЧЕНИЕ ………………………………………………………………………….17

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ …………………………………….19

ВВЕДЕНИЕ

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

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

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

Цель работы – исследование транспортных путей Нижнегорского района.

Задачи работы:

1 . Рассмотреть все маршруты Нижнегорского района.

2 . По данным маршрутов составить новые маршруты.

3. Показать являются ли новые маршруты Эйлеровыми графами.

4. Построить матрицу смежности для новых маршрутов.

5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.

Объектом исследования является карта транспортных путей Нижнегорского района.

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

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

С общим замыслом работы связана структура разделов. Основная часть состоит из трех глав. В первой рассмотрены основные понятия графов. Во второй главе исследуются маршруты Нижнегорского района.

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

РАЗДЕЛ 1

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ

1.1. Основные понятия теории графов

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

Рис.1.1.

Вершина графа - точка, где могут сходиться/выходить рёбра и/или дуги.

Ребро графа - ребро соединяет две вершины графа.

Степень вершины - количество рёбер, выходящих из вершины графа.

Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если направление связи имеет значение, то линии снабжают стрелками, и в этом случае граф называется ориентированным графом, орграфом. (Рис.1.2.)

Рис.1.2.

Взвешенный граф - граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). (Рис.1.3.)

Рис. 1.3.

Графы, в которых построены все возможные ребра, называются полными графами. (Рис.1.4.)

Рис. 1.4.

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

Матрица смежности – это матрица, элемент M[i] [j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет (Рис.1.5. для графа на рис.1.1).

1.2. Характеристика Эйлеровых графов

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 1.

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.

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

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

Рис.1.6.

1.3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)


Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов (рис.1.7).

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

Алгоритм Дейкстры (E.W. Dijkstra, 1959):

1. Присвоить всем вершинам метку ∞.

2. Среди нерассмотренных вершин найти вершину j с наименьшей меткой.

3. Для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние.

4. Если остались необработанны вершины, перейти к шагу 2.

5. Метка = минимальное расстояние.

Рис.1.7.

Рис.1.8. Решение задачи

РАЗДЕЛ 2

МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА

2.1. Маршруты Нижнегорского района

Нижнегорский район находится в степной части на севере АР Крым. В состав Нижнегорского района входят пгт.Нижнегорский и 59 населенных пунктов.

Через Нижнегорский район проходят две трассы: 2Р58 и 2Р64. Существуют 8 маршрутов, следующие от А/С Нижнегорская до других населенных пунктов. В своей работе я буду рассматривать эти маршруты:

1 маршрут «Нижнегорск – Красногвардейск». Следует через: Нижнегорск – Плодовое – Митофановка – Буревестник – Владиславовка.

2 маршрут «Нижнегорск - Изобильное»: Нижнегорск – Семенное – Кирсановка – Лиственное – Охотское – Цветущее – Емельяновка – Изобильное.

3 маршрут «Нижнегорск - Великоселье»: Нижнегорк – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Чкалово – Великоселье.

4 маршрут «Нижнегорск – Белогорск (трасса 2Р64)»: Нижнегорск – Желябовка – Ивановка – Заречье – Серово – Садовое – Пены.

5 маршрут «Нижнегорск - Уваровка»: Нижнегорск – Семенное – Новоивановка – Уварвка.

6 маршрут «Нижнегорск - Любимовка»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Любимовка.

7 маршрут «Нижнегорск - Пшеничное»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Сливянка – Пшеничное.

8 маршрут «Нижнегорск – Зоркино (траса 2Р58)»: Нижнегорск – Разливы – Михайловка – Кунцево – Зоркино.

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

Маршруты «Нижнегорск - Уваровка» «Нижнегорск - Любимовка» «Нижнегорск - Пшеничное» изменить нельзя, так как по пути их следования, автобусы заезжают во все населенные пункты, поэтому эти маршруты я рассматривать не буду.

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

2.2. Исследование маршрутов Нижнегорского района

1 маршрут: Нижнегорск – Красногвардейск.

Нижнегорск – 1

Плодовое – 2

Митрофановка – 3

Червоное – 6

Буревестник – 4

Новогригорьевка – 7

Владиславовка – 5

Не заезжает в пункт 6, 7. Добавим в маршрут эти населенные пункты.

Рис.2.1.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Плодовое – Митрофановка – Буревестник – Новогригорьевка – Владиславовка. Добавилось село Новогригорьевка.

2 маршрут: Нижнегорск – Изобильное.

Нижнегорск – 1

Семенное – 2

Кирсановка – 3

Лиственное – 4

Охотское – 5

Цветущее – 6

Емельяновка – 7

Изобильное – 8

Кулички – 9

Родники - 10

Не заезжает в пункт 9,10. Добавим в маршрут эти населенные пункты.

Рис.2.2.

Граф не является Эйлеровым и связным, поэтому нельзя построить новый маршрут. Маршрут остается тот же.

3 маршрут: Нижнегорск - Великоселье

Нижнегорск – 1

Семенное – 2

Двуречье – 3

Акимовка – 4

Лужки – 5

Заливное – 6

Степановка – 7

Луговое – 8

Чкалово – 9

Великоселье – 10

Широкое - 11

Не заезжает в пункт 11. Добавим в маршрут этот населенный пункт.

Рис.2.3.

Граф не является Эйлеровым. Маршрут остается тот же.

4 маршрут: Нижнегорск - Белогорск (Трасса 2Р64)

Нижнегорск – 1 Косточковка - 12

Желябовка – 2 Фрунзе - 13

Ивановка – 3 Приречное - 14

Заречье – 4 Жемчужина - 15

Серово – 5

Садовое – 6

Пены – 7

Ломоносово – 8

Кукурузное – 9

Тамбовка – 10

Тарасовка - 11

Не заезжает в пункты 8-18. Добавим в маршрут эти населенные пункты.

Рис.2.4.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Желябовка – Ивановка – Заречье – Тамбовка – Тарсовка – Приречное – Жемчужина – Пены.

5 маршрут: Нижнегорск - Зоркино (Трасса 2Р58)

Нижнегорск – 1

Разливы – 2

Михайловка – 3

Кунцево – 4

Зоркино – 5

Уютное – 6

Нижинское – 7

Не заезжает в пункт 6,7. Добавим в маршрут эти населенные пункты.

Рис.2.5.

Граф не является Эйлеровым и связным, поэтому маршрут остается тот же.

ЗАКЛЮЧЕНИЕ

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

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

В процессе исследования была проделана следующая работа:

1. Проанализирована и проработана литература по теме исследования.

2. Рассмотрены и изучены различные виды фракталов.

3. Представлена классификация фракталов.

4. Собрана коллекция фрактальных образов для первичного ознакомления с миром фракталов.

5. Составлены программы для построения графического образа фракталов.

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

Закончив свой проект, я могу сказать, что всё из того, что было задумано, удалось. В следующем году я продолжу работу над темой «фракталы», так как это тема очень интересна и многогранна. Думаю, что я решил проблему своего проекта, так как мной были достигнуты все поставленные цели. Работа над проектом показала мне то, что математика – это не только точная, но и красивая наука.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.

4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

5. О. Оре. Теория графов, Наука, 1982 г.

Третья городская научная

конференция учащихся

Информатика и математика

Исследовательская работа

Круги Эйлера и теория графов в решении задач

школьной математики и информатики

Валиев Айрат

Муниципальное общеобразовательное учреждение

«Средняя общеобразовательная школа №10 с углубленным изучением

отдельных предметов», 10 Б класс, г. Нижнекамск

Научные руководители:

Халилова Нафисе Зиннятулловна, учитель математики

Учитель информатики

г. Набережные Челны

Введение. 3

Глава 1. Круги Эйлера. 4

1.1. Теоретические основы о кругах Эйлера. 4

1.2. Решение задач, применяя круги Эйлера. 9

Глава 2.О графах 13

2.1.Теория графов. 13

2.2. Решение задач, используя графы. 19

Заключение. 22

Список литературы. 22

Введение

«Всё наше достоинство заключено в мысли.

Не пространство, не время, которых мы не можем заполнить,

возвышает нас, а именно она, наша мысль.

Будем же учиться хорошо мыслить.»

Б. Паскаль,

Актуальность. Основной задачей школы является не подача детям большого объёма знаний, а обучение учащихся самим добывать знания, умению перерабатывать эти знания и применять их в каждодневной жизни. Поставленные задачи может решить ученик, обладающий не только умением хорошо и много работать, но и ученик с развитым логическим мышлением. В связи с этим во многие школьные предметы вложены различного типа задачи, которые и развивают у детей логическое мышление. Решая эти задачи, мы применяем различные приёмы решения. Одни из приёмов решения – это использование кругов Эйлера и граф.

Цель исследования : изучение материала, применяемого на уроках математики и информатики, где используются круги Эйлера и теория графов, как один из приемов решения задач.

Задачи исследования :

1. Изучить теоретические основы понятий: «Круги Эйлера», «Графы».

2. Решить задачи школьного курса вышеназванными методами.

3. Составить подборку материала для использования учениками и учителями на уроках математики и информатики.

Гипотеза исследования: применение кругов Эйлера и графов повышают наглядность при решении задач.

Предмет исследования: понятия: «Круги Эйлера», «Графы», задачи школьного курса математики и информатики.

Глава 1. Круги Эйлера.

1.1. Теоретические основы о кругах Эйлера.

Эйлеровы круги (круги Эйлера) - принятый в логике способ моделирования, наглядного изображения отношений между объемами понятий с помощью кругов, предложенный знаменитым математиком Л. Эйлером (1707–1783).

Обозначение отношений между объемами понятий посредством кругов было применено еще представителем афинской неоплатоновской школы - Филопоном (VI в.), написавшим комментарии на «Первую Аналитику» Аристотеля.

Условно принято, что круг наглядно изображает объем одного какого-нибудь понятия. Объем же понятия отображает совокупность предметов того или иного класса предметов. Поэтому каждый предмет класса предметов можно изобразить посредством точки, помещенной внутри круга, как это показано на рисунке:

Группа предметов, составляющая вид данного класса предметов, изображается в виде меньшего круга, нарисованного внутри большего круга, как это сделано на рисунке.

https://pandia.ru/text/78/128/images/image003_74.gif" alt="пересекающиеся классы" width="200" height="100 id=">

Такое именно отношение существует между объемом понятий «учащийся» и «комсомолец». Некоторые (но не все) учащиеся являются комсомольцами; некоторые (но не все) комсомольцы являются учащимися. Незаштрихованная часть круга А отображает ту часть объема понятия «учащийся», которая не совпадает с объемом понятия «комсомолец»; незаштрихованная часть круга B отображает ту часть объема понятия «комсомолец», которая не совпадает с объемом понятия «учащийся». 3аштрихованиая часть, являющаяся общей для обоих кругов, обозначает учащихся, являющихся комсомольцами, и комсомольцев, являющихся учащимися.

Когда же ни один предмет, отображенный в объеме понятия A, не может одновременно отображаться в объеме понятия B, то в таком случае отношение между объемами понятий изображается посредством двух кругов, нарисованных один вне другого. Ни одна точка, лежащая на поверхности одного круга, не может оказаться на поверхности другого круга.

https://pandia.ru/text/78/128/images/image005_53.gif" alt="понятия с одинаковыми объемами - совпадающие круги" width="200" height="100 id=">

Такое отношение существует, например, между понятиями «родоначальник английского материализма» и «автор „Нового Органона“». Объемы этих понятий одинаковы, в них отобразилось одно и то же историческое лицо - английский философ Ф. Бэкон.

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

https://pandia.ru/text/78/128/images/image007_46.gif" alt="противоположные понятия" width="200" height="100 id=">

При этом видно, что между противоположными понятиями возможно третье, среднее, так как они не исчерпывают полностью объема родового понятия. Такое именно отношение существует между понятиями «легкий» и «тяжелый». Они исключают друг друга. Нельзя об одном и том же предмете, взятом в одно и то же время и в одном и том же отношении, сказать, что он и легкий, и тяжелый. Но между данными понятиями есть среднее, третье: предметы бывают не только легкого и тяжелого веса, но также и среднего веса.

Когда же между понятиями существует противоречащее отношение, тогда отношение между объемами понятий изображается иначе: круг делится на две части так: А - родовое понятие, B и не-B (обозначается как B) - противоречащие понятия. Противоречащие понятия, исключают друг друга и входят в один и тот же род, что можно выразить такой схемой:

https://pandia.ru/text/78/128/images/image009_38.gif" alt="субъект и предикат определения" width="200" height="100 id=">

Иначе выглядит схема отношения между объемами субъекта и предиката в общеутвердительном суждении, не являющемся определением понятия. В таком суждении объем предиката больше объема субъекта, объем субъекта целиком входит в объем предиката. Поэтому отношение между ними изображается посредством большого и малого кругов, как показано на рисунке:

Школьные библиотеки" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">школьной библиотеке , 20 - в районной. Сколько из пятиклассников:

а) не являются читателями школьной библиотеки;

б) не являются читателями районной библиотеки;

в) являются читателями только школьной библиотеки;

г) являются читателями только районной библиотеки;

д) являются читателями обеих библиотек?

3. Каждый ученик в классе изучает либо английский, либо французский язык , либо оба этих языка. Английский язык изучают 25 человек, французский - 27 человек, а тот и другой -18 человек. Сколько всего учеников в классе?

4. На листе бумаги начертили круг площадью 78 см2 и квад­рат площадью 55 см2. Площадь пересечения круга и квад­рата равна 30 см2. Не занятая кругом и квадратом часть листа имеет площадь 150 см2. Найдите площадь листа.

5. В детском саду 52 ребенка. Каждый из них любит либо пирожное, либо мороженое, либо и то, и другое. Половина детей любит пирожное, а 20 человек - пирожное и мороженое. Сколько детей любит мороженое?

6. В ученической производственной бригаде 86 старшеклас­сников. 8 из них не умеют работать ни на тракторе, ни на комбайне. 54 ученика хорошо овладели трактором, 62 - комбайном. Сколько человек из этой бригады мо­гут работать и на тракторе, и на комбайне?

7. В классе 36 учеников. Многие из них посещают круж­ки: физический (14 человек), математический (18 чело­век), химический (10 человек). Кроме того, известно, что 2 человека посещают все три кружка; из тех, кто по­сещает два кружка, 8 человек занимаются в математи­ческом и физическом кружках, 5 - в математическом и химическом, 3 - в физическом и химическом. Сколь­ко человек не посещают никаких кружков?

8. 100 шестиклассников нашей школы участвовали в опро­се, в ходе которого выяснялось, какие компьютерные игры им нравятся больше: симуляторы, квесты или стратегии. В результате 20 опрошенных назвали симуляторы, 28 - квесты, 12 - стратегии. Выяснилось, что 13 школьников отдают одинаковое предпочтение симуляторам и квестам, 6 учеников - симуляторам и стратегиям, 4 ученика - квестам и стратегиям, а 9 ребят совершенно равнодушны к названным компьютерным играм. Некоторые из школьников ответили, что одинаково увлекаются и симуляторами, и квестами, и стратегиями. Сколько таких ребят?

Ответы

https://pandia.ru/text/78/128/images/image012_31.gif" alt="Овал: А " width="105" height="105">1.

А – шахматы 25-5=20 – чел. умеют играть

В – шашки 20+18-20=18 – чел играют и в шашки, и в шахматы

2. Ш – множество посетителей школьной библиотеки

Р – множество посетителей районной библиотеки

https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">

5. 46. П – пирожное, М – мороженое

6 – детей любят пирожное

6. 38. Т – трактор, К – комбайн

54+62-(86-8)=38 – умеют работать и на тракторе и на комбайне

графами" и систематически изучать их свойства.

Основные понятия.

Первое из основных понятий теории графов - это понятие вершины. В теории графов оно принимается в качестве первичного и не определяется. Его нетрудно представить себе на собственном интуитивном уровне. Обычно вершины графа наглядно изображаются в виде окружностей, прямоугольников другими фигурами (рис.1). Хотя бы одна вершина должна обязательно присутствовать в каждом графе.

Другое основное понятие теории графов - дуги. Обычно дуги представляют собой отрезки прямых или кривых, соединяющих вершины. Каждый из двух концов дуги должен совпадать с какой-нибудь вершиной. Случай, когда оба конца дуги совпадают с одной и той же вершиной, не исключается. Например, на рис.2 - допустимые изображения дуг, а на рис.3 - недопустимые:

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

Дуги могут быть однонаправленными, при этом каждая дуга имеет только одно направление, или двунаправленными.

В большинстве применений можно без потери смысла заменить ненаправленную дугу на двунаправленную, а двунаправленную - на две однонаправленных дуги. Например, так, как показано на рис. 4.

Как правило, граф либо сразу строится таким образом, чтобы все дуги имели одинаковую характеристику направленности (например, все - однонаправленные), либо приводится к такому виду путем преобразований. Если дуга AB - направленная, то это значит, что из двух ее концов один (A) считается началом, а второй (B) - концом. В этом случае говорят, что начало дуги AB есть вершина A, а конец - вершина B, если дуга направлена от A к B, или что - дуга AB исходит из вершины A и входит B (рис. 5).

Две вершины графа, соединенные какой-либо дугой (иногда, независимо от ориентации дуги) называют смежными вершинами.

Важным понятием при исследовании графов является понятие пути. Путь A1,A2,...An определяется как конечная последовательность (кортеж) вершин A1,A2,...An и дуг A1, 2,A2 ,3,...,An-1, n последовательно соединяющих эти вершины.

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

Например, если изобразить в виде графа систему кровообращения человека, где вершины соответствуют внутренним органам, а дуги - кровеносным капиллярам, то такой граф, очевидно, является связным. Можно ли утверждать, что система кровообращения двух произвольных людей является несвязным графом? Очевидно, нет, поскольку в природе наблюдаются т. н. “сиамские близнецы”.

Связность может быть не только качественной характеристикой графа (связный/несвязный), но и количественной.

Граф называется K-связным, если каждая его вершина связана с K других вершин. Иногда говорят о слабо - и сильносвязанных графах. Эти понятия субъективны. Исследователь называет граф сильносвязанным, если для каждой его вершины количество смежных вершин, по мнению исследователя, велико.

Иногда связность определяют как характеристику не каждой, а одной (произвольной) вершины. Тогда появляются определения типа: граф называется K-связным, если хотя бы одна его вершина связана с K других вершин.

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

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

Еще одна характеристика графа, исследуемая в ряде задач, часто называется мощностью графа. Эта характеристика определяется как количество дуг, связывающих две вершины. При этом дуги, имеющие встречное направление, часто рассматриваются раздельно.

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

Мощность, как и связность, может определяться как для каждой пары вершин графа, так и для некоторой (произвольной) пары.

Существенная характеристика графа - его размерность. Под этим понятием обычно понимают количество вершин и дуг, существующих в графе. Иногда эта величина определяется как сумма количеств элементов обоих видов, иногда - как произведение, иногда - как количество элементов только одного (того или иного) вида.

Разновидности графов.

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

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

Окраска

Окраска графов - весьма популярный способ модификации графов.

Этот прием позволяет, и повысить наглядность модели и увеличить математическую загруженность. Способы введения окраски могут быть различными. По тем или иным правилам окрашиваются как дуги, так и вершины. Окраска может быть однократно определена или меняться с течением времени (т. е. при приобретении графом каких-либо свойств); цвета можно преобразовывать по тем или иным правилам, и т. д.

Например, пусть граф представляет собой модель кровообращения человека, где вершины соответствуют внутренним органам, а дуги - кровеносным капиллярам. Окрасим артерии в красный цвет, а вены - в синий. Тогда очевидно справедливость следующего утверждения - в рассматриваемом графе (рис. 8) существуют, и при этом только две, вершины, имеющие исходящие красные дуги (на рисунке красный цвет изображен жирно).

Дольность

Иногда элементы объекта, моделируемые вершинами, имеют существенно различный характер. Или к реально существующим в объекте элементам в процессе формализации оказывается полезным добавить некоторые фиктивные элементы. В этом, и некоторых других случаях, вершины графа естественно разделить на классы (доли). Граф, содержащий вершины двух типов, называют двудольным и т. д. При этом в число ограничений графа вносятся правила, касающиеся взаимоотношений вершин разных типов. Например: “не существует дуги, которая бы соединяла вершины одного типа”. Одна из разновидностей графов такого рода называется “сеть Петри” (рис. 9) и имеет достаточно широкое распространение. Более подробно сети Петри будут рассмотрены в следующей статье этого цикла.

Понятие дольности может быть применено не только к вершинам, но и к дугам.

2.2. Решение задач, используя графы.

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

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году. (рис. 11).

3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 12). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

4.

Задачи Дьюдени.

1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р)

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже .

5. Пассажир – однофамилец кондуктора живет в Чикаго.

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

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста? (рис.13)

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы). Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.

Заключение

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

Список литературы

1. «Занимательные задачи по информатике» , Москва, 2005

2. «Сценарии школьных праздников» Е. Владимирова, Ростов-на-Дону, 2001

3. Задачи для любознательных. , М., Просвещение, 1992г,

4. Внеклассная работа по математике, Саратов, Лицей, 2002г.

5. Удивительный мир чисел. , ., М., Просвещение, 1986г.,

6. Алгебра: учебник для 9 класса . , и др. под ред. ,- М.: Просвешение, 2008

Кучин Анатолий Николаевич

Руководитель проекта:

Куклина Татьяна Ивановна

Учреждение:

МБОУ "Основная общеобразовательная школа" п. Троицко-Печорск Респ. Коми

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

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


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

Введение
Глава 1. Знакомимся с графами
1.1. История графов.
1.2. Виды графов
Глава 2. Возможности применения теории графов в различных областях повседневной жизни
2.1. Применение графов в различных областях жизни людей
2.2. Применение графов при решении задач
2.3. Генеалогическое древо – один из способов применения теории графов
2.4. Описание исследования и составление генеалогического древа моей семьи
Заключение
Использованная литература
Приложения

«В математике следует помнить не формулы,
а процесс мышления».
Е.И. Игнатьева

Введение


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

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

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

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

Выяснить особенности применения теории графов при решении задач и в практической деятельности.

Объектом исследования является математические графы.

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

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

Для реализации поставленной цели, мною были выдвинуты следующие задачи:

1. познакомиться с историей теории графов;
2. изучить основные понятия теории графов и виды графов;
3. рассмотреть способы решения задач с помощью графов;
4. показать применение теории графов в различных областях жизни человека;
5. создать генеалогическое древо моей семьи.

Методы: наблюдение, поиск, отбор, анализ, исследование.


Исследование:
1. были изучены ресурсы сети Интернет и печатные издания;
2. выписаны области науки и жизнедеятельности человека, в которых используется метод графов;
3. рассмотрено решение задач с помощью теории графов;
4. изучена методика составления генеалогического древа моей семьи.

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

Чтобы убедится в этом, мной и руководителем было предложено учащимся 5-9 классов, участникам школьного и муниципального туров Всероссийской олимпиады школьников, 4 задачи, при решении которых можно применить теорию графов (Приложение 1 ).

Результаты решения задач таковы:
Всего 15 учащихся (5 класс – 3 ученика, 6 класс - 2 ученика, 7 класс – 3 ученика, 8 класс - 3 ученика, 9 класс - 4 ученика) применили теорию графов в 1 задаче – 1, во 2 задаче – 0, в 3 задаче – 6, в 4 задаче – 4 учащихся.

Практическая значимость исследования заключается в том, что результаты несомненно вызовут интерес у многих людей. Разве не пытался кто-то из вас построить генеалогическое дерево своей семьи? А как это сделать грамотно?
Оказывается они решаются при помощи графов легко.