Презентация по математике Тема : « Графы » Презентацию подготовил Студент группы 11-ЭОП-30Д Овсянников Егор

Содержание История возникновения теории графов История возникновения теории графов Задача Эйлера о семи мостах Задача Эйлера о семи мостах Виды графов Виды графов

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

Леонард Эйлер (, Базель, Швейцария 7 (18) сентября 1783, Санкт- Петербург, Российская империя) швейцарский, немецкий и российский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук. Леонард Эйлер (4 (15) апреля 1707, Базель, Швейцария 7 (18) сентября 1783, Санкт- Петербург, Российская империя) швейцарский, немецкий и российский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук. Эйлер автор более чем 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др.

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

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

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

Задача Эйлера

Виды Графов Ориентированный граф (кратко орграф ) (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами. Записывается в виде G:= (V, A), где V – это не пустое множество вершин или узлов, А - это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Н е о р и е н т и р о в а н н ы й г р а ф - з а п и с ы в а е т с я в в и д е G : = ( V, E ), г д е V – э т о н е п у с т о е м н о ж е с т в о в е р ш и н и л и у з л о в, E - э т о м н о ж е с т в о п а р ( в с л у ч а е н е о р и е н т и р о в а н н о г о г р а ф а н е у п о р я д о ч е н н ы х ) в е р ш и н, н а з ы в а е м ы х р ё б р а м и. V ( а з н а ч и т и E, и н а ч е о н о б ы б ы л о м у л ь т и м н о ж е с т в о м ) о б ы ч н о с ч и т а ю т с я к о н е ч н ы м и м н о ж е с т в а м и.

Многие хорошие результаты, полученные для конечных графов, неверны (или каким- либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств. Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| - порядком, число ребер|E| - размером графа.

Смешанный граф – это граф, в котором некоторые ребра могут быть ориентированными, а некоторые – неориентированными. Записывается в виде G:= (V, E, A). Ориентированный и неориентированный графы являются частными случаями смешанного.

Неориентированный графОриентированный граф Смешанный граф

Спасибо за внимание !!!