'

Графы и их применение

Понравилась презентация – покажи это...





Слайд 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

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


×

HTML:





Ссылка: