Понравилась презентация – покажи это...
Слайд 0
Графы и их применение
Мастер-класс
12 февраля
ГМО учителей информатики
Слайд 1
Некоторые основные понятия теории графов
Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек.
Степень вершины называется число ребер графа, которым принадлежит эта вершина.
Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины.
Граф называется несвязным, если существуют хотя бы две вершины несвязные путем
Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь
Рис. 1
Слайд 2
Зачем нужны деревья?
Для организации данных
Классификация объектов
Описания структуры
Для решения задач, в которых надо найти
Все существующие решения
Самое короткое решение или длинное решение
Разработать стратегию игры
И так далее.
Слайд 3
Отыскание пути
На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?
Слайд 4
Решение задачи
Кратчайший путь: 1 5 9. Его длинна 2.
Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9.
Число путей 14
Слайд 5
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
3,18, ? 21
3,2, ? 5
Слайд 6
МАТРИЦЫ ГРАФОВ
.
B0
B1
B2
B3
B4
B5
B6
B0
0
4
6
5
B1
4
7
3
B2
7
11
9
B3
6
3
4
5
B4
11
4
4
2
B5
5
5
4
8
B6
9
2
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Слайд 7
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда
из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
1)
2)
3)
4)
AC C B - 7
AC CE EB - 7
AC C B - 7
AE EC CB - 7
AC C B - 7
AC CE EB - 6
AD DC CB - 9
AD DC CE EB - 8
Слайд 8
Спасибо за внимание
