Графы
Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:
Граф – это набор вершин и связей между ними, называющихся рёбрами:
Граф, отображающий дороги между поселками
Матрица и список смежности
Связный граф – это граф, между любыми вершинами которого существует путь.
Связный граф
Дерево – это связный граф без циклов (замкнутых участков).
Дерево — связный граф без циклов
Взвешенные графы и весовая матрица
У взвешенных графов указан «вес ребра»:
Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.
Весовая матрица
ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)
Определение кратчайшего пути между пунктами A и D
- В заданиях ОГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
- Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
- На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.