Граф - это топологическая модель, которая состоит из множества вершин и множества соединяющих их рёбер.
Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер;
Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен «вес».
Путь или Маршрут - это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути - количество рёбер в пути.
Табличная информационная модель – это модель, в которой объекты или их свойства представлены в виде списка, а их значения размещаются в ячейках прямоугольной таблицы. Такой тип моделей применяется для описания ряда объектов, обладающих одинаковым набором свойств.
В контексте описания реальных объектов и процессов таблицы могут быть использованы для представления качественных и количественных характеристик, свойств, параметров и зависимостей между объектами и процессами.
Рассмотрим, как решать 4 задание ОГЭ по информатике. Есть несколько способов решений этого задания.
Между населёнными пунктами
A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С.
Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Давайте проведем визуализацию данной таблицы. Для этого сначала расставим все населенные пункты, которые даны в таблице, они будут вершинами. Далее соединяем вершины ребрами ( ребра это дороги, идущие из пункта А) и указываем вес каждого ребра (числовое значение в таблице).
Из табличной структуры получили структуру в виде графов. Из полученного рисунка видно, что анализ будет проходить гораздо лучше. Мы должны найти кратчайший путь между пунктом А и Е проходящий через пункт С. Для этого свяжем все пунктами при помощи графа.
Проанализируем дороги (повторяющиеся учитывать не будем):
- Из пункта А можно попасть в В (1 км), C (4 км), D (3 км) и Е (7 км)
- Из пункта В можно попасть в С (2 км) и D (5 км)
- Из пункта С можно попасть в D (3 км)
- Из пункта D можно попасть в Е (2 км)
После рассмотрим получившиеся маршруты:
1) A-B-C-D-E=8
- A-C-D-E=9
- A-C-B-D-E=13
- A-B-C-D-E=8
- A-B-D-E — не подходит, так как не идет через С
- A-D-E — не подходит, так как не идет через С
- A-E - не подходит, так как не идет через С
Ответ: кратчайший маршрут - A-B-C-D-E=8
Рассмотрим, как решать 9 задание по информатике ОГЭ.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город В?
Начальны город А обозначаем за 1
А=1
В город Б ведет 1 дорога из города А, поэтому
Б=А(1)=1
В город В идет 2 дороги из города А и города Б
В=А(1)+Б(1)=2
В город Г идет 1 дорога из города В, дорогу из города А не учитываем
Г=В(2)=2
В город Д идет одна дорога из города В, дорогу из города Б не учитываем
Д=В(2)=2
В город Ж идет 2 дороги из города В и города Г
Ж=В(2)+Г(2)=4
В город Е идет 2 дороги из города В и города Д
Е=В(2)+Д(2)=4
В город К идут 3 дороги из Д, Е, Ж
К= Д(2)+Е(4)+Ж(4)=10
Ответ 10