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

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

Содержание ▲

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

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

Слайд 1

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

Слайд 2

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

Слайд 3

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

Слайд 4

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

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

Слайд 5

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

Задача о Кенигсбергских мостах. В прусском городке Кенигсберг на реке Прегель семь мостов. Можно ли найти маршрут прогулки, который проходит ровно 1 раз по каждому из мостов и начинается и заканчивается в одном месте?

Слайд 6

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

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

Слайд 7

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

Кирх Гоф Кэлли Жордан В 1847 году Кирх Гоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи. Кэлли в 1857 году, занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемый деревьями. Жордан (1869 год), независимо от Кэлли, ввел и изучал деревья как чисто математические объекты, совершенно не подозревая о значении своего открытия для современной химической науки.

Слайд 8

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

Д.Кениг Л.В.Канторович Начало бурного развития и практического применения теории графов было положено венгерским математиком Д. Кенигом, который опубликовал в 1936 г. монографию «Теория конечных и бесконечных графов». Российский академик Л. В. Канторович разработал метод решения транспортных задач для их сетевой постановки.

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

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

Слайд 14

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

Слайд 15

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

Слайд 16

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

Слайд 17

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

Слайд 18

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

Слайд 19

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

Слайд 20

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

Слайд 21

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

Слайд 22

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

Слайд 23

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

Слайд 24

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

Матрица смежности Граф

Слайд 25

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

Матрица инцидентности

Слайд 26

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

Слайд 27

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

Примеры Граф, не являющийся эйлеровым

Слайд 28

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

Слайд 29

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

Достаточные условия

Слайд 30

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

Достаточные условия

Слайд 31

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

11. ОПРЕДЕЛЕНИЕ ДЕРЕВА Связный неориентированный ациклический граф называется деревом. Множество деревьев называется лесом. Остовным деревом графа называется его подграф, содержащий все вершины графа.

Слайд 32

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

ОСТОВНОЕ ДЕРЕВО Пусть теперь каждому ребру x X связного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным. Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальной суммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа G). Определение. Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G.

Слайд 33

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

ОСТОВНОЕ ДЕРЕВО Алгоритм выделения МОД нагруженного связного графа G: Шаг 1. Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему вершинами оно образует подграф G2 графа G. Положим i=2. Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое МОД графа G. В противном случае переходим к шагу 3. Шаг 3. Строим граф Gi+1, добавляя к графу Gi новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно к какой-нибудь вершине графа Gi и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и инцидентные ему вершины, не содержащиеся в Gi . Присваиваем i:=i+1 и переходим к шагу 2.

Слайд 34

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

ОСТОВНОЕ ДЕРЕВО Определить МОД нагруженного графа G, изображенного на рис., используя алгоритм.

Слайд 35

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

ОСТОВНОЕ ДЕРЕВО

Слайд 36

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

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

Слайд 37

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

Кратчайшие пути на графе Вначале вершине x0 присваивается окончательная метка 0 (нулевое расстояние до самой себя), а каждой из остальных вершин присваивается временная метка (бесконечность). На каждом шаге одной вершине с временной меткой присваивается окончательная и поиск продолжается дальше. На каждом шаге метки меняются следующим образом. Каждой вершине xj, не имеющей окончательной метки, присваивается новая временная метка — наименьшая из ее временной и числа ( wij+ окончательная метка xi), где xi — вершина, которой присвоена окончательная метка на предыдущем шаге. Определяется наименьшая из всех временных меток, которая и становится окончательной меткой своей вершины. В случае равенства меток выбирается любая из них. Циклический процесс п.1+п.2 продолжается до тех пор, пока вершина z не получит окончательной метки. Легко видеть, что окончательная метка каждой вершины — это кратчайшее расстояние от этой вершины до начала x0.