Презентация, доклад по теме Графы, решение задач

открытых дверей, который будет проходить в главном корпусе университета. Поезд приходит на ж/д вокзал, от которого отправляются множество автобусов. Сопровождающий получил следующую упрощенную схему следования маршрутных такси до пункта назначения.

Что нам мешает решить задачу?
Что нужно сделать чтобы решить задачу?
 

Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.

Виды графов

нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация)

груз необходимо доставить n потребителям. Известны стоимости перевозок. Требуется составить такой план перевозок, чтобы запасы всех поставщиков были вывезены, запросы всех потребителей удовлетворены и суммарные затраты на перевозку всех грузов были минимальны.

вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно.
Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.

маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);
составить наиболее выгодный маршрут доставки деталей рабочим или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).

и не содержать повторных посещений). Затраты на проезд приведены в табл.1.

Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

А

Б

В

Г

Д

Ж

Е

1. А-Б-Д-Ж

2. А-Б-Г-Д-Ж

3. А-Б-Г-Ж

4. А-В-Б-Д-Ж

5. А-В-Б-Г-Д-Ж

6. А-В-Б-Г-Ж

7. А-В-Г-Д-Ж

8. А-В-Г-Ж

9. А-В-Ж

10. А-В-Е-Ж

Ответ: 10 путей

Задача

итоговые затраты для каждого маршрута.
Маршрут, имеющий минимальные затраты и будет искомым решением.

что…
• я научился…
• я смог…
• было интересно узнать, что…
• меня удивило…
• мне захотелось…
• свою работу на уроке я оцениваю…..
• моя группа работала…
• в группе мне было работать…….

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

пути 7: 1 2 3 6 5 7 8 9.
Число путей 14