Теория графов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория графов. Доклад-сообщение содержит 58 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Основные вопросы лекции. Основные вопросы лекции. Введение Понятие графа.

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Начало развития теории графов как самостоятельной математической дисциплины положено Д. Кенигом, выпустившим в 1936 году книгу Начало развития теории графов как самостоятельной математической дисциплины положено Д. Кенигом, выпустившим в 1936 году книгу " Теория конечных и бесконечных графов".

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Представление в виде ориентированных графов логической или функционально - логической схемы

Слайд 10

Описание слайда:

Блок – схема алгоритма может быть представлена вероятностным графом

Слайд 11

Описание слайда:

Графом типа “дерево” можно отобразить практически любую структуру организации или предприятия

Слайд 12

Описание слайда:

Граф есть конечное множество V, называемое множеством вершин, на котором задано симметричное, антирефлексивное отношение R и выделено множество Е двухэлементных подмножеств V, определяемое как {а,b}  R тогда и только тогда, когда (а,b)R и аb. Граф есть конечное множество V, называемое множеством вершин, на котором задано симметричное, антирефлексивное отношение R и выделено множество Е двухэлементных подмножеств V, определяемое как {а,b}  R тогда и только тогда, когда (а,b)R и аb.

Слайд 13

Описание слайда:

Множество Е называется множеством ребер. Всякий элемент множества Е называется ребром. Множество Е называется множеством ребер. Всякий элемент множества Е называется ребром. Граф обозначается G(V, E). Элементы a и b графа V соединены или связаны ребром {a, b}, если {a, b}  Е.

Слайд 14

Описание слайда:

Пример. Пример. Граф с множеством вершин V = {a, b, c} и множеством ребер Е = {{a, b},{b,c}} R = {(а,b), (b,а), (b,c), (c,b)}.

Слайд 15

Описание слайда:

Пример. Пример. Граф, у которого V = {a, b, c, d, e} и Е = {{a, b},{a, e},{b, e},{b, d},{b, c},{c,d}}

Слайд 16

Описание слайда:

Для отношения более общего вида необходимо представление элемента (а,b)  R, Для отношения более общего вида необходимо представление элемента (а,b)  R, для которого возможно (b,a)  R. Это возможно представить с помощью ориентированного графа.

Слайд 17

Описание слайда:

Ориентированный граф, или орграф G, обозначаемый Ориентированный граф, или орграф G, обозначаемый G (V,E), состоит из множества V вершин и отношения E на V, называемого множеством ориентированных ребер, или просто ребер.

Слайд 18

Описание слайда:

Элемент множества Е называется ориентированным ребром. Элемент множества Е называется ориентированным ребром. Если (a,b)  E, то a называется начальной вершиной (a,b), а b – его конечной вершиной.

Слайд 19

Описание слайда:

Пример. Пример. Орграф с вершинами V = {x1,x2,x3,x4} и ребрами E = {(x1,x2), (x2,x3), (x2,x4), (x4,x2), (x4,x1)}.

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Граф есть конечное множество V, называемое Граф есть конечное множество V, называемое множеством вершин, и множество Е двухэлементных всех неупорядоченных различных подмножеств множества V. Множество Е называется множеством ребер. Элемент множества Е называется ребром. Граф обозначается G(V, E). Элементы a и b элементы множества V называются соединенными или связанными ребром {a, b}, если {a, b}  Е.

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

Конечный граф с n вершинами называется графом n-го порядка. Конечный граф с n вершинами называется графом n-го порядка.

Слайд 24

Описание слайда:

Если {a, b} – ребро, тогда вершины a и b называются концами ребра {a, b}. Ребро {a, b} называют также инцидентным к вершинам a и b. Если {a, b} – ребро, тогда вершины a и b называются концами ребра {a, b}. Ребро {a, b} называют также инцидентным к вершинам a и b.

Слайд 25

Описание слайда:

Две вершины называются смежными, если они являются концами ребра, или, что то же самое, если они инцидентны к одному ребру. Две вершины называются смежными, если они являются концами ребра, или, что то же самое, если они инцидентны к одному ребру.

Слайд 26

Описание слайда:

Два ребра называются смежными, если они инцидентны к общей вершине. Два ребра называются смежными, если они инцидентны к общей вершине.

Слайд 27

Описание слайда:

Граф G (V,E) – совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Граф G (V,E) – совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро е из Е инцидентно ровно двум вершинам, которые оно соединяет.

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Пример ориентированного графа Пример ориентированного графа

Слайд 33

Описание слайда:

Пример неориентированного графа

Слайд 34

Описание слайда:

Пример смешанного графа

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

Если G(V, E) – мультиграф, то Е может иметь несколько ребер (а,b). Если G(V, E) – мультиграф, то Е может иметь несколько ребер (а,b). Такие ребра называются кратными ребрами.

Слайд 37

Описание слайда:

Замечания: Граф – это мультиграф, у которого кратность каждого ребра равна единице. В графе две вершины могут быть соединены не более чем одним ребром. В мультиграфе две вершины могут быть соединены более чем одним ребром.

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

Псевдограф – граф в котором допускается как наличие петель, так и существование более одного ребра между двумя вершинами.

Слайд 40

Описание слайда:

Обыкновенный (простой) граф – граф без петель и кратных ребер

Слайд 41

Описание слайда:

Граф называется полным, если любые его две вершины соединены ребром.

Слайд 42

Описание слайда:

. Степенью вершины υ, обозначается deg(υ), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей или концевой. Ребро, инцидентное концевой вершине, также называется концевым.

Слайд 43

Описание слайда:

Смежные вершины: а и с; с и f; f и b; b и a; a и d; d и f. Смежные вершины: а и с; с и f; f и b; b и a; a и d; d и f. Смежные ребра: e1, e2 и e3; e2 и e6; e6, e4 и e5; e5 и e1; e3 и e4. Вершины a и f смежными не являются. e2 и e5 не являются смежными ребрами. Вершины b, c, d имеют степень 2, вершины a и f имеют степень 3.

Слайд 44

Описание слайда:

Лемма о рукопожатии. Лемма о рукопожатии. Сумма степеней всех вершин графа есть четное число.

Слайд 45

Описание слайда:

Доказательство. Доказательство. Каждое ребро графа имеет два конца, следовательно, степень каждого конца увеличивается на 1 за счет одного ребра.

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

Следствие. Следствие. В любом графе количество вершин нечетной степени четно.

Слайд 48

Описание слайда:

Граф G ′(V ′, E′) называется подграфом графа G(V, E), Граф G ′(V ′, E′) называется подграфом графа G(V, E), обозначается G′(V′, E′) G(V, E), если V′  V, E ′  E. Таким образом, каждая вершина в G ′ является вершиной в G, и каждое ребро в G′ является ребром в G.

Слайд 49

Описание слайда:

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

Слайд 50

Описание слайда:

Суграфом графа G называется граф , Суграфом графа G называется граф , где , т.е. суграф получается из исходного графа путем удаления некоторого числа ребер (с сохранением вершин).