Презентация, доклад проекта по математике тема Математические графы

Кирносов Алексей
Руководитель: Шаповалова О.П.

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

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

18 веке, когда великий математик швейцарского происхождения Леонард Эйлер решил загадку о Кенигсбергских мостах. В то время, Кенигсберг (ныне Калининград) имел семь участков, соединенных мостами через реку Прегель.

(1707-1783 )

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

→

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

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

№1
В стране 607 городов, из каждого выходит по 4 дороги. Сколько всего дорог в стране?

Решение
Посчитаем, сколько концов дорог в стране. Их 607×4, так как из каждого города выходит ровно четыре дороги. Теперь заметим, что каждая дорога имеет ровно два конца, поэтому дорог в стране в два раза меньше, то есть 607×4÷2=1214.

все кроме Саши, дружат ровно с пятью одноклассниками. Может ли Саша ни с кем дружить?

Решение

Докажем, что у Саши есть друзья. Будем рассуждать от противного, то есть предположим, что у Саши нет друзей. Представим отношения между одноклассниками в виде графа. Вершины графа-это одноклассники. Ребрами соединены вершины, только если соответствующие одноклассники дружат. Посчитаем, сколько в этом графе рёбер. Всего в графе 25×5-нечетно, значит, существование такого графа невозможно. Это означает, что наше предположение о том, что у Саши нет друзей, неверно. Это означает, что у Саши есть друзья.

города выходит по три дороги и нет развилок и тупиков, быть ровно 95 дорог?

Решение

Будем рассуждать от противного и предположим, что описанная система (то есть граф «города-дороги» ) может существовать. В этой задаче, в отличии от предыдущих, нам известно число ребер в графе и не известно число вершин. Попробуем его вычислить, исходя из условий задачи. У каждой дороги два конца, в каждую вершину проходит по три конца. Значит, количество вершин в графе равно 95×2÷3. Но 190 не кратно трем, потому приходим к противоречию: если бы такой граф существовал, у него не было бы нецелое число вершин.

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

по двум трубам. Первая была открыта 0,6 ч, а вторая 0,4 ч. В результате поступило 3,32 л раствора. Сколько питательного раствора подается за 1 ч по второй трубе, если по первой поступает 3,6 л раствора за 1 ч?

Л

2 тр. Всего литров V2 - 0,4 x

V1 + V2 = 3,32 Л

Время t2 = 0,4 ч

Время t1 = 0, 6 ч

Кол-во Л за 1 ч, 1тр. = 3,6Л

Кол-во Л за 1 ч,
2 тр. = x Л

8,4 км по шоссе и 3,2 км по просёлочной дороге, затратив на весь путь 1 час. С какой скоростью ехал турист по проселочной дороге, если известно, что по шоссе он ехал в 1,75 раза быстрее?

Vп

tш + tп = 1 ч

S ш = 8,4 км

Ответ: 8 км/ч.

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