Графы и их применение Мастер-класс 12 февраля ГМО учителей информатики. - презентация

1 Графы и их применение Мастер-класс 12 февраля ГМО учителей информатики

2 Некоторые основные понятия теории графов Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек. Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек. Степень вершины называется число ребер графа, которым принадлежит эта вершина. Степень вершины называется число ребер графа, которым принадлежит эта вершина. Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины. Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины. Граф называется несвязным, если существуют хотя бы две вершины несвязные путем Граф называется несвязным, если существуют хотя бы две вершины несвязные путем Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь Рис. 2 Рис. 1

3 Зачем нужны деревья? Для организации данных Для организации данных Классификация объектов Классификация объектов Описания структуры Описания структуры Для решения задач, в которых надо найти Для решения задач, в которых надо найти Все существующие решения Все существующие решения Самое короткое решение или длинное решение Самое короткое решение или длинное решение Разработать стратегию игры Разработать стратегию игры И так далее. И так далее.

4 Отыскание пути На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

5 Решение задачи ярус 2 ярус 3 ярус 4 ярус 5 ярус 6 ярус 7 ярус Кратчайший путь: Его длинна 2. Длина наиболее продолжительного пути 7: Число путей

6 Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. 2 ход 2 игрок 3,9, 12 12,2, 14 4,6, 10 5,2, 7 27,2, 29 3 ход 1 игрок 4 ход 2 игрок 15,3,18 12,4,16 12,9,21 12,4,16 36,3,39 13,3,16 12,9,21 4,27,31 3,18, 21 4,4, 8 5,3, 8 12,3, 15 4,9, 13 4,3, 7 3,4, 7 1 ход 1 игрок 3,6, 9 4,2, 6 3,3, 6 9,2, 11 3,2, 5

7 МАТРИЦЫ ГРАФОВ В0 В1 В2 В3В4 В5 В B0B1B2B3B4B5B6 B00465 B1473 B B36345 B B55548 B

8 Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: Минимальная стоимость проезда из А в B не больше 6. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.ABCDЕ A31 B42 C342 D1 Е22ABCDЕA311 B4 C342 D1 Е12ABCDЕA31 B41 C342 D1 Е12 ABCDЕA1 B41 C442 D14 Е12 1) 2) 3)4) B C D E A B C D E A B C D E A B C D E A 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

9 Спасибо за внимание