Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов и процессов окружающего мира

Август 24, 2022

Главная
Математика
Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов и процессов окружающего мира

Содержание

2. Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) ,
3. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя),
4. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ Термин "граф" впервые появился в книге венгерского математика Д. Кенига в 1936 г.,
5. Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов и процессов окружающего мира. Бинарное
6. Граф Для отображения структурной модели (схемы) системы используются графы. Граф состоит из вершин, связанных линиями. Направленная
7. Неориентированный граф - граф, не имеющий выделенного направления, вершины такого графа соединены ребрами. Неориентированный граф
8. Ориентированный граф Ориентированный граф - граф, вершины которого соединены дугами.
9. Ориентированный граф I II IV III Известно, что существуют четыре группы крови человека. При переливании крови
10. Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать,
11. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Иерархия –
12. Граф иерархической структуры - «Дерево» Финалисты Участники ½ финала Участники ¼ финала Первоначальные игроки Олимпийская система
13. Локальный диск (С:) Проекты Рисунки Закат Зима Информатика История Эпоха Возрождения Интернет Компьютерные вирусы Граф иерархической
14. Граф иерархической структуры - «Дерево»
15. Бинарное дерево — это конечное множество элементов, связанных с двумя разными бинарными деревьями — правым и
16. ПРИМЕНЕНИЕ ГРАФОВ С помощью графов упрощается решение математических задач, головоломок, задач на смекалку. дальше
17. ПРИМЕНЕНИЕ ГРАФОВ Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
18. Использует графы и дворянство. На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого.
19. ПРИМЕНЕНИЕ ГРАФОВ Графами являются блок – схемы программ для ЭВМ.
20. ПРИМЕНЕНИЕ ГРАФОВ Типичными графами на географических картах являются изображения железных дорог.
21. ПРИМЕНЕНИЕ ГРАФОВ Типичными графами на картах города являются схемы движения городского транспорта.
23. Решение: Вершины графа – это деревья. Проведём стрелки от более высокого к более низкому дереву. Получим
26. Скачать презентацию

Слайд 2

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский,

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

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ

Слайд 3

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по

всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа).

В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Слайд 4

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ
Термин "граф" впервые появился в книге венгерского математика Д.

Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру.

Слайд 5

Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов

и процессов окружающего мира. Бинарное дерево.

Слайд 6

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

связанных линиями.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

петля

ребро

дуга

Слайд 7

Неориентированный граф - граф, не имеющий выделенного направления, вершины такого графа

соединены ребрами.

Неориентированный граф

Слайд 8

Ориентированный граф
Ориентированный граф - граф, вершины которого соединены дугами.

Слайд 9

Ориентированный граф
I
II
IV
III
Известно, что существуют четыре группы крови человека. При

переливании крови от одного человека к другому не все группы совместимы.
На схеме показаны возможные варианты переливания крови

Дуги

Петля

Петля – линия, выходящая и входящая в одну и ту же вершину. Направленные линии называют дугами (в отличии от ребер неориентированных графов).

Слайд 10

Взвешенный граф
Это граф, рёбрам или дугам которого поставлены в соответствие

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

Таблице (она называется весовой матрицей) соответствует граф.

Слайд 11

Отличительной особенностью дерева является то, что между любыми двумя его вершинами

существует единственный путь.
Иерархия – это расположение
частей или элементов целого в порядке от высшего к низшему.

Иерархический граф

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

Слайд 12

Граф иерархической структуры - «Дерево»
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Олимпийская система

спортивных соревнований

Чемпион

Корень – главная вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.

Слайд 13

Локальный диск (С:)
Проекты
Рисунки
Закат
Зима
Информатика
История
Эпоха
Возрождения
Интернет
Компьютерные вирусы
Граф иерархической структуры - «Дерево»

Слайд 14

Граф иерархической структуры - «Дерево»

Слайд 15

Бинарное дерево — это конечное множество элементов, связанных с двумя разными

бинарными деревьями — правым и левым поддеревьями.
Способ представления:

Слайд 16

ПРИМЕНЕНИЕ ГРАФОВ
С помощью графов упрощается решение математических задач, головоломок, задач на

смекалку.

дальше

Слайд 17

ПРИМЕНЕНИЕ ГРАФОВ
Лабиринт - это граф. А исследовать его - это найти

путь в этом графе.

Слайд 18

Использует графы и дворянство.
На рисунке приведена часть генеалогического дерева знаменитого дворянского

рода Л. Н. Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

ПРИМЕНЕНИЕ ГРАФОВ

Слайд 19

ПРИМЕНЕНИЕ ГРАФОВ
Графами являются блок – схемы программ для ЭВМ.

Слайд 20

ПРИМЕНЕНИЕ ГРАФОВ
Типичными графами на географических картах являются изображения железных дорог.

Слайд 21

ПРИМЕНЕНИЕ ГРАФОВ
Типичными графами на картах города являются схемы движения городского транспорта.

Слайд 22

Слайд 23

Решение:
Вершины графа – это деревья. Проведём стрелки от более высокого к

более низкому дереву. Получим граф, на котором видно, что самое низкое дерево – это клён. Далее яблоня, лиственница, рябина, сосна, дуб, береёз и тополь.

Слайд 24

Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов и процессов окружающего мира

Содержание

Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский,

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВТермин "граф" впервые появился в книге венгерского математика Д.

Структура информации. Деревья. Графы. Использование графов, деревьев, списков при описании объектов

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

Неориентированный граф - граф, не имеющий выделенного направления, вершины такого графа

Ориентированный графОриентированный граф - граф, вершины которого соединены дугами.

Ориентированный граф IIIIVIIIИзвестно, что существуют четыре группы крови человека. При

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие

Отличительной особенностью дерева является то, что между любыми двумя его вершинами

Граф иерархической структуры - «Дерево»ФиналистыУчастники ½ финалаУчастники ¼ финалаПервоначальные игрокиОлимпийская система

Локальный диск (С:)Проекты Рисунки ЗакатЗимаИнформатика ИсторияЭпохаВозрожденияИнтернетКомпьютерные вирусыГраф иерархической структуры - «Дерево»

Граф иерархической структуры - «Дерево»

Бинарное дерево — это конечное множество элементов, связанных с двумя разными

ПРИМЕНЕНИЕ ГРАФОВС помощью графов упрощается решение математических задач, головоломок, задач на

ПРИМЕНЕНИЕ ГРАФОВЛабиринт - это граф. А исследовать его - это найти

Использует графы и дворянство.На рисунке приведена часть генеалогического дерева знаменитого дворянского

ПРИМЕНЕНИЕ ГРАФОВГрафами являются блок – схемы программ для ЭВМ.

ПРИМЕНЕНИЕ ГРАФОВТипичными графами на географических картах являются изображения железных дорог.

ПРИМЕНЕНИЕ ГРАФОВТипичными графами на картах города являются схемы движения городского транспорта.

Решение:Вершины графа – это деревья. Проведём стрелки от более высокого к

Похожие презентации