Поделиться
9-10.pptx
ТЕСТ
ТЕСТ
№1
Строка в базе данных называется:
А) Поле
Б) Высота
В) Запись
№2
Табличная база данных называется
А) Сетевой
Б) Реляционной
В) Иерархической
№ 3
КЛЮЧ
№ 1 – В
№ 2 – Б
№ 3 – 2
Граф. Весовая матрица графа.
Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе.
«Три пути у человека, чтобы разумно поступать: первый, самый благородный, – размышление; второй, самый легкий, – подражание; третий, самый горький, – опыт.» Конфуций
Задача
Преступникам удалось скрыться с места преступления. Входе проведения оперативно – розыскных мероприятий было установлено, что подозреваемые направились в город К.
Для задержания подозреваемых необходимо определить количество возможных вариантов передвижения в г.К, а также по таблице построить граф и найти кратчайший путь из г.А в г. К.
А | Б | В | Г | Д | Е | К | |
А | 2 | 1 | 2 | ||||
Б | 2 | 3 | 2 | ||||
В | 1 | 3 | 2 | 3 | |||
Г | 2 | 2 | 1 | ||||
Д | 2 | 4 | |||||
Е | 1 | 1 | |||||
К | 3 | 4 | 1 | ||||
Основные понятия
Граф состоит из вершин, связанных линиями – ребрами.
Ориентированный граф- граф, ребра которого имеют направления.
Неориентированный граф- граф, ребра которого не имеют направления.
Взвешенный граф- его вершины или ребра характеризуются некоторой дополнительной информацией (весами).
Основные понятия
Цепь - путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза.
Цикл – цепь, начальная и конечная вершины которой совпадают.
Сеть – граф с циклом.
Семантическая сеть –
Дерево – граф, в котором нет циклов.
Задача 1
На рисунке - схем дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Решение
1
1
1
4
1
3
9
Ответ: 9
Задача 2
Преступник скрылся с места преступления и движется в город Е. Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:
Для задержания преступника необходимо определить длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.
А | B | C | D | E | |
A | 1 | ||||
B | 1 | 2 | 7 | ||
C | 2 | 3 | |||
D | 4 | ||||
E | 7 | 3 | 4 | ||
Решение
А | B | C | D | E | |
A | 1 | ||||
B | 1 | 2 | 7 | ||
C | 2 | 3 | |||
D | 4 | ||||
E | 7 | 3 | 4 | ||
E
B
D
C
E
E
A
1
2
2
7
8
3
4
6
7
Ответ: ABCЕ – 6 км
Задача
Преступникам удалось скрыться с места преступления. Входе проведения оперативно – розыскных мероприятий было установлено, что подозреваемые направились в город К.
Для задержания подозреваемых необходимо определить количество возможных вариантов передвижения в г.К, а также по таблице построить граф и найти кратчайший путь из г.А в г. К.
А | Б | В | Г | Д | Е | К | |
А | 2 | 1 | 2 | ||||
Б | 2 | 3 | 2 | ||||
В | 1 | 3 | 2 | 3 | |||
Г | 2 | 2 | 1 | ||||
Д | 2 | 4 | |||||
Е | 1 | 1 | |||||
К | 3 | 4 | 1 | ||||
Домашнее задание
§ 2.3 (п.1,2),
Основные понятия записать в тетрадь.
Вопросы и задания стр.117
№ 11
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
