Информационные модели. Графы

Информационные модели. Графы - Скачать Читать Лучшую Школьную Библиотеку Учебников
Смотреть онлайн
Поделиться с друзьями:
Информационные модели. Графы:
Презентация на тему Информационные модели. Графы к уроку по обществознанию

Презентация "Информационные модели. Графы" онлайн бесплатно на сайте электронных школьных учебников edulib.ru

Информационные модели. Графы.
1 слайд

Информационные модели. Графы.

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

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

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

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

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совмести
4 слайд

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе. Задача.

ПЕРЕЛИВАНИЕ КРОВИ I II III IV
5 слайд

ПЕРЕЛИВАНИЕ КРОВИ I II III IV

Графы Граф – это информационная модель, представленная в графической форме. Граф - множество вершин
6 слайд

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

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами.
7 слайд

Ориентированные графы - орграфы Каждое ребро имеет одно направление. Такие ребра называются дугами. Ориентированный граф

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

Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки). Вес графа равен сумме весов его рёбер. Таблице (она называется весовой матрицей) соответствует граф. 1 2 4 2 3 A B C D E

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена
9 слайд

Задача Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2
10 слайд

1. 2. 3. 4. 5. Длина кратчайшего маршрута A-B-C-E-F равна 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

Задача Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк
11 слайд

Задача Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.   A B C D Е A     3 1   B     4   2 C 3 4     2 D 1         Е   2 2       A B C D Е A     3 1   B     4   2 C 3 4     2 D 1         Е   2 2       A B C D Е A     3 1   B     4   2 C 3 4     2 D 1         Е   2 2       A B C D Е A     3 1   B     4   2 C 3 4     2 D 1         Е   2 2    

1)
12 слайд

1)

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двига
13 слайд

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? Графы. Поиск путей. Г В А К Е Б Д Ж И вершина откуда? N Кол-во путей Б А 1 Г А 1 В АБГ 3 Е Г 1 Д БВ 4 Ж ВЕ 4 И Д 4 К И+Д+Ж+Е= 13

Отзывы на edulib.ru"Информационные модели. Графы" (0)
Оставить отзыв
Прокомментировать