Теория:
Одним из самых наглядных видов представления информации считаются схемы.
Одним из наиболее часто используемых видов схем является граф.
Граф — это набор вершин и соединяющих их рёбер (вспомнить теорию).
Ориентированный (направленный) граф — это граф, рёбра которого имеют направление, указанное стрелками (перемещаться по графу можно только по указанным направлениям).
Взвешенный граф — это граф, у которого каждое ребро связано с некоторым числом (это его вес).
Вес может обозначать расстояние между пунктами или стоимость проезда между ними, обозначается числами над рёбрами графа.
Взвешенный граф часто используют для обозначения дорог между населёнными пунктами.
Рис. \(1\). Взвешенный граф
Есть задачи, которые удобно решать с помощью графов, например, задание № \(9\) из ОГЭ.
Пример:
на рисунке изображены дороги, связывающие вершины А, Б, В, Г, Д, Е, З и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько есть различных путей из вершины А в вершину К?
Рис. \(2\). Пример
Для начала следует отметить, что существует три типа задания № \(9\).
1) Найти путь из вершины А в вершину К. Здесь мы просто считаем все возможные варианты путей из одной вершины в другую. Как это делается, мы разберём чуть позже на примере.
2) Найти путь из вершины А в вершину К, проходящий через вершину Б. Решается аналогично первому варианту, только следует исключить из ответа пути, не проходящие через вершину Б. Вариантов будет значительно меньше.
3) Найти путь из вершины А в вершину К, не проходящий через вершину Б. Решается аналогично первому варианту, только следует исключить из ответа пути, проходящие через вершину Б.
Обрати внимание!
Очень важно прежде всего выяснить, к какому типу относится твоё задание, и правильно представить, какой именно граф будет рассматриваться при решении твоего задания.
Источники:
Изображения. © ЯКласс.