Презентация на тему Графы. Информация и информационные процессы

Содержание

Графы «От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет

Слайд 1Графы

Графы

Слайд 2Графы
«От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и

Ягодное. Между Солнцевым и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное».
Графы «От посёлка Васюки три дороги идут в посёлки Солнцево, Грибное и Ягодное. Между Солнцевым и Грибным

Слайд 3Графы

Мультиграф – граф в котором пара вершин соединена несколькими

рёбрами
Графы    Мультиграф – граф в котором пара вершин соединена несколькими рёбрами

Слайд 4
Граф (англ. graph) — совокупность непустого множества вершин и наборов пар вершин (связей между вершинами); основной

объект изучения математической теории графов.
От греч. γράφω «царапаю, черчу, пишу»:
Граф (математика) — объект, состоящий из вершин и соединяющих их рёбер.

Граф (англ. graph) — совокупность непустого множества вершин и наборов пар вершин (связей между вершинами); основной объект изучения математической теории графов. От греч. γράφω «царапаю,

Слайд 5
Граф, или неориентированный граф G— это упорядоченная пара G:=(V,E), где V

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

Слайд 6
Вершины и рёбра графа называются также элементами графа,
число вершин в

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

Вершины и рёбра графа называются также элементами графа,  число вершин в графе |V| — порядком,

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

петлёй, если его концы совпадают, то есть e={v,v}.
Степенью deg V вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра;
Вершина называется висячей (или листом), если она является концом ровно одного ребра.

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

Слайд 8А
B
D
C
E

3

А B D C E  3

Слайд 9Теорема о сумме степеней вершин графа
Сумма степеней всех вершин графа (или

мультиграфа без петель) — равна удвоенному числу рёбер

для неориентированного графа

Если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю.
Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы.
Таким образом, сумма всех степеней вершин четна и равна удвоенному количеству рёбер.

Теорема о сумме степеней вершин графа Сумма степеней всех вершин графа (или мультиграфа без петель) — равна

Слайд 10Доказательство
1
2
4
6
1
1
2
1
1
2
3
2
3

Доказательство 1 2 4 6 1 1 2 1 1 2 3 2 3

Слайд 11Доказательство
1
2
4
6
1
1
 
2
1
 
1
2
 
3
2
 
3
 

Доказательство 1 2 4 6 1 1   2 1   1 2   3 2  

Слайд 12для ориентированного графа:
 

для ориентированного графа:  

Слайд 13Доказательство
1
2
4
6
1
1
2
1
1
2
3
2
3
3
5
1
1
.

Доказательство 1 2 4 6 1 1 2 1 1 2 3 2 3 3 5 1

Слайд 14Лемма о рукопожатиях
В любом графе число вершин нечётной степени чётно.
В любой

момент времени количество людей, сделавших нечетное число рукопожатий, чётно

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

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

Слайд 15Теорема о существовании вершин одинаковой степени
В любом графе есть по крайней

мере две вершины, имеющие одинаковую степень.
Теорема о существовании вершин одинаковой степени В любом графе есть по крайней мере две вершины, имеющие одинаковую

Слайд 16Теорема о существовании вершин одинаковой степени
 

Теорема о существовании вершин одинаковой степени  

Слайд 17Матрица и список смежности

петля
Матрица смежности
Список смежности
( A (B, C),

B (A, C, D), C (A, B, С, D), D (B, C) )
Матрица и список смежности  петля Матрица смежности Список смежности ( A (B, C),

Слайд 18Способы представления графа в информатике
Матрица смежности - бинарная матрица каждой ячейке

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

Слайд 19Способы представления графа в информатике
Список смежности —каждой вершине графа соответствует список, состоящий

из "соседей" этой вершины.

Реализация предложенная Гвидо ван Россумом использует хэш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления рёбер в этой структуре
Кормен и другие предложили реализацию в которой вершины представлены числовым индексом в массиве, в котором каждая ячейка массива ссылается на однонаправленный связанный список соседних вершин.
Объектно ориентированный список смежности, предложенный Гудричем и Таммасией, содержит специальные классы вершин и рёбер. Каждый объект вершины содержит ссылку на коллекцию рёбер. Каждый объект ребра содержит ссылки на исходящую и входящую вершины.

Способы представления графа в информатике Список смежности —каждой вершине графа соответствует список, состоящий из

Слайд 20Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме

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




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

Слайд 21Постройте матрицу смежности, найдите её порядок и размер

Постройте матрицу смежности, 
 найдите её порядок и размер

Слайд 22Постройте матрицу смежности


Постройте матрицу смежности

Слайд 23Нарисуйте граф

Нарисуйте граф

Слайд 24Нарисуйте граф

Нарисуйте граф

Слайд 25Нарисуйте граф

Нарисуйте граф

Слайд 26Связность графа

Связность графа

Слайд 27Дерево – это граф?
дерево

ABC ABDC
BCD CCC…

Дерево – это граф? дерево  ABC	ABDC BCD	CCC…

Слайд 28Взвешенные графы
12
8
2
5
4
6
Весовая матрица:
вес ребра

Взвешенные графы 12 8 2 5 4 6 Весовая матрица: вес ребра

Слайд 29Постройте весовую матрицу

Постройте весовую матрицу

Слайд 30Постройте весовую матрицу


Постройте весовую матрицу

Слайд 31Нарисуйте граф

Нарисуйте граф

Слайд 32Нарисуйте граф

Нарисуйте граф

Слайд 33Нарисуйте граф

Нарисуйте граф

Слайд 34Кратчайший путь (перебор)








A
B
С
E
С
D
С
D
E
D
2
4
6
2
4
6
1
3

1
3
9
7
5
8
4
1
3
7
дерево возможных путей


Определите кратчайший путь между пунктами A и

D.
Кратчайший путь (перебор)         A B С E С D

Слайд 35Кратчайший путь
Определите кратчайший путь между пунктами A и E.

Кратчайший путь Определите кратчайший путь между пунктами A и E.

Слайд 36Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь Определите кратчайший путь между пунктами A и B.

Слайд 37Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь Определите кратчайший путь между пунктами A и B.

Слайд 38Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь Определите кратчайший путь между пунктами A и B.

Слайд 39Кратчайший путь
Определите кратчайший путь между пунктами A и B.

Кратчайший путь Определите кратчайший путь между пунктами A и B.

Слайд 40Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра называю дугами.

Ориентированные графы (орграфы) Рёбра имеют направление (начало и конец), рёбра называю дугами.

Слайд 41Нарисуйте орграф

Нарисуйте орграф

Слайд 42Нарисуйте орграф

Нарисуйте орграф

Слайд 43Количество путей из А в Ж
1
1
1
1+1+1=3
1
1+1+1+1+3=7
1

Количество путей из А в Ж 1 1 1 1+1+1=3 1 1+1+1+1+3=7 1

Слайд 44Количество путей из А в К

Количество путей из А в К

Слайд 45Количество путей из А в К


Количество путей из А в К

Слайд 46Количество путей из А в К



Количество путей из А в К

Слайд 47Количество путей из А в К




Количество путей из А в К

Слайд 48Количество путей из А в Л не через В
А










Б
В
Г
Д
Е
Ж
И
К
Л
Сколько существует различных

путей из города А в город Л, не проходящих через B?
Количество путей из А в Л не через В А

Слайд 49Количество путей из А в Л через Д
А









Б
В
Г
Д
Е
Ж
И
К
Л
Сколько существует различных путей

из города А в город Л, проходящих через Д?



Количество путей из А в Л через Д А

Слайд 50Количество путей из А в Л через Д
Сколько существует различных путей

из города А в город Л, проходящих через Д?

А









Б

В

Г

Д

Е

Ж

И

К

Л





Количество путей из А в Л через Д Сколько существует различных путей из города А в город

Слайд 51Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
eremin@pspu.ac.ru
Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru  ЕРЕМИН

Слайд 52Источники иллюстраций
http://overhealth.ru
https://ufhealth.org
http://wmposters.com
http://ozon.ru
http://www.bikeshot.ru
http://ru.wikipedia.org
http://salestores.com
http://gimp-werkstatt.de
http://frontal-cortex.tumblr.com
http://www.intermedia.kg
http://pc-azbuka.ru
авторские материалы



Источники иллюстраций http://overhealth.ru  https://ufhealth.org  http://wmposters.com http://ozon.ru http://www.bikeshot.ru http://ru.wikipedia.org http://salestores.com http://gimp-werkstatt.de http://frontal-cortex.tumblr.com http://www.intermedia.kg http://pc-azbuka.ru авторские материалы

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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


Для правообладателей

Яндекс.Метрика