Презентация по теме "ГРАФЫ"

Слайд 1

Слайд 2

Возникновение Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Слайд 3

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

Слайд 4

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

Слайд 5

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами . В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V. Теория графов

Слайд 6

Граф , или неориентированный граф G — это упорядоченная пара , G : =(V,E) для которой выполнены следующие условия: V — это непустое множество вершин или узлов ; E — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами . V (а значит и, E иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов . Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств. Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| - порядком , число рёбер |E| — размером графа. Вершины u и v и называются концевыми вершинами (или просто концами ) ребра e = {u,v} . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними . Два ребра называются смежными , если они имеют общую концевую вершину. Два ребра называются кратными , если множества их концевых вершин совпадают. Общие сведения о графах Вершина Ребро E V

Слайд 7

Ориентированный граф Ориентированный граф (сокращённо орграф ) G — это упорядоченная пара , G :=( V,A) для которой выполнены следующие условия: V — это непустое множество вершин или узлов , A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами . Дуга — это упорядоченная пара вершин ( v,w ) где вершину v называют началом а w — концом дуги. Можно сказать, что дуга ведёт от вершины к вершине . Смешанный граф Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G := (V,E,A) где V , E и A определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного. Подвиды графов v w

Слайд 8

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

Слайд 9

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

Слайд 10

В химии (для описания структур, путей сложных реакций [1] , правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров углеводородов и других органических соединений. В информатике и программировании (граф-схема алгоритма) В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете. В экономике В логистике В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф ). Применение графов

Слайд 11

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