Информационное моделирование
НАВИГАЦИЯ ПО СТРАНИЦЕ
легко понять и запомнить
Вершины графа — это компоненты системы, изображаемые точками, кружками, овалами, прямоугольниками и т. д.
Дуги — это направленные линии (стрелки), связывающие вершины между собой определенным образом.
Ребра — это ненаправленные линии, связывающие вершины между собой определенным образом.
Петля — это ребро, входящее и выходящее из одной и той же вершины.
Вершины, которые не соединены ни одним ребром, называются «изолированными».
Граф с дугами называется ориентированным (направленным).
Если вершины/ребра графа обладают некоторой дополнительной информацией — весом вершины или ребра, то такой граф называется
С помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяженность дорог в километрах.
Теперь посмотрим, как будет выглядеть таблица, описывающая этот граф. Мы видим, что эта таблица симметрична относительно главной диагонали. Также в ней присутствуют пустые клетки. Это означает, что между соответствующими вершинами нет ребра. По данной таблице видно, что пути между пунктами 2 и 3, 3 и 4 не существует.
1 | 2 | 3 | 4 | |
|---|---|---|---|---|
1 | 22 | 35 | 15 | |
2 | 22 | 20 | ||
3 | 35 | |||
4 | 15 | 20 |
Цепь — путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза.
Цикл — цепь, у которой совпадают начальная и конечная вершины.
Сеть — граф с циклом.
Информационные модели в виде графов широко используются в повседневной жизни.
Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т. д. — ребрами графа. По таким графам удобно прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.
Граф, в котором отсутствуют циклы, называется деревом. В этом случае между любыми двумя вершинами существует только один путь. С помощью дерева удобно представлять иерархическую систему. У дерева выделяется одна главная вершина, которую называют корнем. Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня), но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня. Вершины, у которых отсутствуют порожденные вершины, называются листьями.
Существуют задачи, которые удобно решать с помощью графов. Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8. С помощью графов удобно решать задачи на определение выигрышной стратегии игроков.
Задача на анализ информации, представленной в виде графа, является одной из предлагаемых на государственной итоговой аттестации по информатике.
В заданиях ЕГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.
