Задание 4 Формализация описания реальных объектов и процессов, моделирование объектов и процессов
Элементы содержания: Возможность описания непрерывных объектов и процессов с помощью
дискретных данных.
Знания, умения: Анализировать простейшие модели объектов.
Графы
Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:
Граф – это набор вершин и связей между ними, называющихся рёбрами:
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_2f398090a7240594.png)
Граф, отображающий дороги между поселками
Матрица и список смежности
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_d1d20840a31f2b75.png)
Связный граф – это граф, между любыми вершинами которого существует путь.
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_5a1b38aea13123c8.png)
Связный граф
Дерево – это связный граф без циклов (замкнутых участков).
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_ba508bfe24a1b005.png)
Дерево — связный граф без циклов
Взвешенные графы и весовая матрица
У взвешенные графов указан вес ребра
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_fd213a632150daee.png)
Весовая матрица
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_157f109623d58cd5.png)
ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)
![](https://fsd.multiurok.ru/html/2022/06/21/s_62b18688be257/phpxhUdbh_Teoriya-OGE_html_2c38734f795d9773.png)
Определение кратчайшего пути между пунктами A и D
В заданиях ОГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.