Удивительные применения графов

Удивительные применения графов

Оглавление. Введение –Как возникла работа. Сущность проблемы. Глава1. Из теории графов. Интересные моменты из истории. 1.1.  О теории графов. 1.2.  Немного теории Глава 2. Исследование необычных применений графов. 2.1.  Графы в играх и головоломках 2.2.  Графы и подсчеты комбинаций 2.3.  Моделирование задач с помощью графов Глава 3 Авторское практическое применение графов. Принципы создания схемы эвакуации в случае ЧС Заключение Список литературы стр. 2-3 стр.4-7 стр.8-13 стр.14-17 стр.18 стр.19

Введение.

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

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

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

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

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

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

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

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

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

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

Цели исследования:

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

·  формирование правил выработки выигрышной стратегии в игровых ситуациях;

·  создание на основе теории графов схемы эвакуации МОУ лицея в случае чрезвычайной ситуации;

·  апробация этой схемы в ходе тренировки в день гражданской обороны;

Задачи исследовательской работы:

Ø  показать эффективность использования теории графов при решении логических задач, головоломок, применение графов на практике.

Ø  накопить реально-практический опыт применения теории графов.

Глава 1.

1.1. Теория графов.

Перед тем, как начать работу, я ознакомилась с материалом из истории. Откуда взялась данная теория, и в как возникла?

С теорией графов связаны не только математические развлечения и головоломки. Теория графов наука молодая. Первая работа по теории графов принадлежит Леонарду Эйлеру, она появилась в 1736 году в публикациях Петербургской Академии Наук. Он описывал решения головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х годов ХХ века в связи со становлением кибернетики и развитием вычислительной техники.

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

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

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

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

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

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек (вершины графа) и соединяющих эти точки отрезков прямых или кривых (ребра графа) (примеры графов изображены на рисунке 1).

Рис. 1. Примеры графов

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

Задача. Винни-Пух решил навестить своих друзей: Пятачка, Кролика и Иа-Иа. Ему обязательно нужно побывать у каждого из своих друзей и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но вы же знаете Винни-Пуха: он не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга:

Решение. Дано: Иа-Иа (О) Винни-Пух (В) Пятачок (П) Кролик (К) Надо: Найти кратчайший путь Рассуждения.

Алгоритм решения:

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

2.  Определить пары симметричных вариантов (симметричные варианты – это, например, пути В-К-П-И-В и В-И-П-К-В) и вычеркнуть на графе один вариант из каждой пары.

3.  Выписать оставшиеся варианты и подсчитать расстояния:

a.  В-К-П-И-В=60+50+55+30=195;

b.  В-К-И-П-В=60+45+55+40=200;

c.  В-И-К-П-В=30+45+50+40=165.

Ответ: самый короткий путь Винни-Пуха: В-И-К-П-В=165

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

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

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

Рис. 2. Нулевой граф с пятью вершинами Рис. 3. Неполный граф с пятью вершинами

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

Например, все три фигуры на рисунке изображают один и тот же граф.

Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.

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

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

Ø  На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.

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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

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

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

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

На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст. А.
На рисунке : Ст. А = 1, Ст. Б = 2, Ст. В = 3, Ст. Г= 2, Ст. Д= 0.

Вершина называется нечетной - если степень этой вершины нечетная, четной - если степень этой вершины четная.

Сформулируем некоторые закономерности, присущие определенным графам.

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

Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Доказательство.

Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро. ч. т.д.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

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

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

Доказательство.

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

Задача. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

  Решение.

Если в государстве k городов(вершин), то сумма степеней всех вершин равна 3k, и равна удвоенному произведению числа ребер – 2r. Отсюда число ребер (дорог) - 3k/2. Это число не может быть равно 100.

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

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

Доказательство.

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа

(К1 + К3 + К5 +...) + (2K2 + 2К3 +4K4 + 4К5 + ...)=2R
Вторая скобка - четное число как сумма четных чисел. Полученная сумма (2R) - четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

ч. т.д.

Задача. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей?

Решение.Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 - степень 4, 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

Глава 2.

Графы в играх и головоломках.

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

Пример 1. Рассмотрим одну из простейших задач: «Крас­ный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша от­личается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем граф (1).

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

(1) (2)

Пример 2 .

Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение: Решим задачу с помощью полного графа с четырьмя вершинами А, Б, В, Г, обозначенными по первым буквам имен каждого из мальчиков. В полном графе проводятся всевозмож­ные ребра. В данном случае отрезки-ребра обозна­чают сыгранные шахматные партии. Из рисунка видно, что граф имеет 6 ребер, значит, и партий было сыграно 6. Ответ: 6 партий.

Пример 3. Андрей, Борис, Виктор и Григорий после возвращения из спортивного лагеря подари­ли на память друг другу свои фотографии. Причем каждый мальчик подарил каждому из своих друзей
по одной фотографии. Сколько всего фотографий было подарено?

Решение. I способ. С помощью стрелок на ре­брах полного графа с вершинами А, Б, В и Г показан процесс обмена фотографиями. Очевидно, стрелок в 2 раза больше, чем ребер, т. е. 6*2 = 12. Столько же было подарено и фотографий.

II способ. Каждый из четверых мальчиков пода­рил друзьям 3 фотографии, следовательно, всего было роздано 3 • 4 = 12 фотографий.

О т в е т: 12 фотографий.

2.2. Графы и подсчеты комбинаций.

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

Пример 1. «Сколько трехзначных чисел можно составить из цифр 1,3,5,7, используя в записи числа каждую из них не более одного раза?».

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

Далее делается важное замечание, что ответ на поставленный вопрос в задаче можно получить, не выписывая сами числа и не строя дерево воз­можных вариантов. Рассуждать будем так. Первую цифру трехзначного числа можно выбрать четырь­мя способами. Так как после выбора первой циф­ры останутся три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Нако­нец, третью цифру можно выбрать (из оставшихся двух) двумя способами. Следовательно, общее число искомых трехзначных чисел равно произве­дению 4*3*2. т. е. 24.

Пример 2. Сколько различных трехзначных чисел можно записать с помощью цифр 1. 2 и 3 при условии, что: 1) цифры в числе должны быть раз­личны; 2) цифры в числе могут повторяться?

Решение. 1) Способ составления трехзначных чисел из трех различных цифр :

123; 213; 132; 312; 231; 321. Получили 6 чисел.

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

111; 112; 113; 211; 212; 213; 311; 312; 313;

121; 122; 123; 221; 222; 223; 321; 322; 323;

131; 132; 133; 231; 232; 233; 331; 332; 333.

Пример 3. Сколько существуют различных трех­значных чисел, записанных с помощью цифр 0, 1, 2, если цифры в числе могут повторяться?

Решение. Первой цифрой составляемого трех­значного числа может быть либо 1, либо 2. Вто­рой цифрой может быть любая из трех данных цифр, третьей — также любая из этих цифр. Изоб­разим сказанное с помощью дерева. Ответ: 18.

Дерево вариантов дает наглядное представление о том, как применяется правило произведения при подсчете комбинаций из большего, чем 2, числа элементов. Действительно согласно правилу произведения первые две циф­ры числа можно было записать шестью способами (2 • 3 = 6). Третью цифру к уже двум имеющимся можно было, согласно правилу произведения, при­писать (2 • 3) • 3 = 18 способами, т. е. существует 2 • 3 • 3 = 18 всевозможных трехзначных чисел, записанных с помощью цифр 0, 1 и 2.

Пример 4. Антон, Борис и Василий купили 3 би­лета на 1-е, 2-е и 3-е места первого ряда на фут­больный матч. Сколькими способами они могут занять имеющиеся места?

Решение. На 1-е место может сесть любой из трех друзей, на 2-е - любой из двух оставшихся, а на 3-е — последний. Сказанное изобразим с помо­щью дерева, помещая в вершины графа первые буквы имен А, Б и В:

АБВ

АВБ

БАВ

БВА

ВАБ

ВБА Ответ: 6.

Пример 5. В меню столовой предложены на вы­бор 3 первых, 5 вторых и 4 третьих блюда. Сколь­ко различных вариантов обеда, состоящего из од­ного первого, одного второго и одного третьего блюда, можно составить из предложенного меню?

Решение. Согласно правилу произведения та­ких обедов можно составить

3 • 5 • 4 = 60.

О т в е т : 60 вариантов.

Дополнительные примеры.

1. При встрече каждый из друзей пожал другому руку. Сколько рукопожатий было

сделано, если друзей было: 1) трое; 2) четверо; 3) пятеро?

2. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвова­ли: 1) 3 человека; 2) 4 человека; 3) 5 человек?

2.3. Прием моделирования с помощью графов

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

Задача. Три товарища — Иван, Дмитрий и Сте­пан преподают различные предметы (химию, био­логию и физику) в школах Москвы, Тулы и Новго­рода. О них известно следующее:

1) Иван работает не в Москве, а Дмитрий — не в Новгороде;

2) москвич преподает физику;

3) тот, кто работает в Новгороде, преподает хи­мию;

4) Дмитрий и Степан преподают не биологию;

Какой предмет, и в каком городе преподает каж­дый?

Решение. В задаче можно выделить три мно­жества: учебных предметов, городов, учителей. Каждое множество содержит по три элемента. Обо­значим их точками вершинами графа

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

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

Так, используя условие 1). проведем пунктирную линию, соединяющую объекты Иван и Москва, Дмитрий и Новгород.

В соответствии с условием 2) соединим сплош­ной линией вершины Москва и физика, а условие 3) выразим сплошной линией от точки Новгород до точки химия.

Дмитрий и Степан преподают не биологию, со­единим соответствующие вершины пунктирными линиями. Кто же преподает биологию? Если это не Дмитрий и не Степан, то получается, что биоло­гию преподает Иван. Эти объекты соединяет сплошная линия.

Где же живет преподаватель биологии? Извест­но, что химик живет в Новгороде, а физик в Моск­ве, следовательно, биолог живет в Туле. Обратим внимание на треугольник, образованный вершина­ми Иван, Тула, биология: в нем есть две сплошные стороны, значит, третью сторону также можно вы­делить сплошной линией В самом деле, если Иван преподает биологию, а биолог живет в Туле, то Иван живет в Туле.

Что известно про Дмитрия? Дмитрий не живет в Новгороде (по условию) не живет в Туле (там живет Иван), значит, Дмитрий живет в Москве - проведем соответствующую сплошную линию. Но москвич преподает физику - эта линия тоже сплошная. В треугольнике с вершинами в точках Дмитрий, Москва и физика две стороны сплош­ные, следовательно, третью сторону тоже можно выделить сплошной линией.

Что же известно про Степана? Степан не живет в Туле (там живет Иван) и не живет в Москве (там живет Дмитрий), следовательно, Степан живет в Новгороде — проведем сплошную линию. Но тот, кто живет в Новгороде, преподает химию — эта линия тоже сплошная. Так появляется третий треугольник из сплошных линий.

Ответ указан на графе треугольниками. Задача решена.

  ПРИНЦИПЫ СОЗДАНИЯ СХЕМЫ ЭВАКУАЦИИ В СЛУЧАЕ ЧС

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

План эвакуации учеников и учителей

1 этаж.

Графы, составленные к плану эвакуации

1 Вариант 2 Вариант

 

План эвакуации учеников и учителей

2 этаж.

Графы, составленные к плану эвакуации

1 Вариант 2 Вариант

 

План эвакуации учеников и учителей

3 этаж.

Графы, составленные к плану эвакуации

1 Вариант 2 Вариант

 

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

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

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

Заключение.

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

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

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

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

1. . Применение графов для решения логических задач.

// Математика в школе. — 1964. — № 3.

2. Шедивы Я. Решение логических задач при помощи графов.

// Математика в школе. — 1967. — № 6.

3. . Графы помогают решать логические задачи.

// Математика в школе. - 1972. - № 2.

4. Федосеев теории вероятностей для VII—VIII классов средней школы.

// Математика в школе. - 2002. - № 4.

5. Журнал «Математика в школе» №3,8-2003; №4,6-2004; №3-2005.

6.Энциклопедический словарь юного математика. Издательство «Педагогика».