Рабочие листы
к вашим урокам
Скачать
1 слайд
Информационные модели. Графы.
2 слайд
Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач.
Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.
3 слайд
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа).
В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
4 слайд
Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е.
1 – 1, 2 – 2 и т.д.
А также 1 группу можно переливать всем остальным группам,
2 и 3 группу только 4 группе.
Задача.
5 слайд
I
II
III
IV
ПЕРЕЛИВАНИЕ КРОВИ
6 слайд
Графы
Граф – это информационная модель, представленная в графической форме.
Граф - множество вершин (узлов), соединённых рёбрами.
Граф с шестью вершинами и семью рёбрами.
Вершины называют смежными, если их соединяет ребро.
7 слайд
Ориентированные графы - орграфы
Каждое ребро имеет одно направление.
Такие ребра называются дугами.
Ориентированный граф
8 слайд
Взвешенный граф
Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать, например, расстояние между городами или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
1
2
4
2
3
A
B
C
D
E
Таблице (она называется весовой матрицей) соответствует граф.
9 слайд
Задача
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 9 2) 10 3) 11 4) 12
10 слайд
A
B
C
2
4
A
B
C
E
2
4
7
1
1.
2.
D
A
B
C
E
2
4
7
1
3
4
3.
D
A
B
C
E
2
4
7
1
3
4
3
4.
D
F
A
B
C
E
2
4
7
1
3
4
3
2
5.
Длина кратчайшего маршрута A-B-C-E-F равна 9
11 слайд
Задача
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
12 слайд
1)
13 слайд
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Графы. Поиск путей.
Г
В
А
К
Е
Б
Д
Ж
И
Рабочие листы
к вашим урокам
Скачать
6 626 959 материалов в базе
Настоящий материал опубликован пользователем Романова Ираида Михайловна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс повышения квалификации
72/180 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
600 ч.
Мини-курс
6 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.