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

ГРАФЫ. Решение задач

Два вида задач на графы в ЕГЭ

• В чистом виде в ЕГЭ два вида задач на графы, хотя они могут применяться и других заданиях, например в задаче на логические уравнения.

1 вид

• Найди длину пути из одной вершины в другую

2 вид

• Найти количество различных путей из одной вершины в другую

Решение задач о количестве путей в графе

• Существуют разные способы, от перебора (при количестве 6 – 7 вершин), до построения дерева.
• Рассмотрим решение с помощью построения дерева

Построим дерево путей из А в Е

Дальнейшее решение

• Понятно, что теперь надо определить сколько путей из точки Е в Н. Тогда общее количество путей из А в Н будет 6*…=
• Попробуйте решить путем перебора

Ответ

• Путей из А в Е - 6
• Путей из Е в Н - 6
• Путей из Н в Т – 3
• Итого =

Σ =6*6*3=108

Кратчайший путь

• Одна из самых известных задач, связанных с графами, — определение длины кратчайше- го пути из одной вершины в другую. Человек, знакомый с теорией графов, сразу скажет, что нужно использовать алгоритм Дейкстры, однако на самом деле это не обязательно. Алгоритм Дейкстры действительно хорош, но он предназначен для автоматического решения задач этого типа. Автоматическое решение требуется, когда

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

Если же нужно решить одну простую задачу,

применение универсального, но непростого алгоритма Дейкстры — это, как говорят, “из пушки по воробьям”.

Задача

Задача сводится к поиску кратчайшего пути в графе.

Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых приведена в таблице. Определите кратчайший путь между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).

1 этап – построение графа

• По заданной таблице (весовой матрице графа) определяем, что граф содержит 7 ребер: AB (дли- ной 2), AC (4), AE (6), BC (1), CD (5), CE (1) и DE (3). Нарисуем граф, соответствующий этим данным (вершины можно располагать как угодно):

Решение перебором

• Теперь перебираем все возможные пути из вер- шины A в вершину D, не проходящие дважды через одну и ту же вершину, и считаем их длины:
• ABCD: 2 + 1 + 5 = 8
• ABCED: 2 + 1 + 1 + 3 = 7
• ACD: 4 + 5 = 9
• ACED: 4 + 1 + 3 = 8
• AECD: 6 + 1 + 5 = 12
• AED: 6 + 3 = 9

Решение с помощью дерева

• 1

• 2

• 3

ОТВЕТ

Сдать тест

• http://kpolyakov.spb.ru/school/ogetest/a3.htm