Презентация, доклад по математике на тему Теория графов (10 класс)

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

в частности свойства пространств, которые остаются неизменными при непрерывных деформациях

Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры

Дискре́тность— свойство, противопоставляемое непрерывности, прерывность. Под дискретностью понимают:
Нечто, изменяющееся между несколькими различными стабильными состояниями.
Нечто, состоящее из отдельных частей, прерывистость, дробность.

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

Дерево — это связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями

Такой граф можно представить как n–угольник, в котором проведены все диагонали.

K4

K6

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

а)

б)

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

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

новой теории музыки' Л. Эйлера, 1739

2007 года

Швейцарская банкнота

математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

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

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

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

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

*Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. 

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

A

C

B

D

K

F

E

интересна не только своей теорией и красивыми теоремами, но также и своей широчайшей областью применения.

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

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

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

используются в