Краткое содержание: Параграф §2.3 / Информатика 9 класс

Основные положения о графических информационных моделях

Графические информационные модели применяются для наглядного представления объектов, используя условные графические изображения, часто дополняемые числовыми данными или текстом. К основным видам таких моделей относятся схемы, карты, чертежи, графики и диаграммы.

• Схема — это модель, которая отражает объект в общих чертах с помощью условных знаков, показывая его внешний вид и/или структуру. Примеры схем включают электрические цепи, схемы в биологии (например, наследование признаков) или исторические схемы сражений.
• Карта — уменьшенное обобщенное изображение поверхности Земли на плоскости, использующее определенную систему условных обозначений.
• Чертеж — условное графическое изображение, показывающее предмет с точным соблюдением его размеров, полученное методом проецирования. Он содержит данные о размерах, форме частей, и может включать надписи, масштаб.
• График — графическое изображение, которое наглядно демонстрирует зависимость одной величины от другой (например, пути от времени) и позволяет изучать динамику изменений данных.
• Диаграмма — графическое представление соотношения нескольких величин или их изменения, используемое для наглядного сравнения или демонстрации структуры данных.

Понятие Графа

Графы являются мощным инструментом моделирования, где объекты представляются вершинами (кругами, овалами, точками), а связи между ними — ребрами (линиями) или дугами (направленными линиями со стрелками). Ребро соединяет вершины в неориентированном графе, а дуга — в ориентированном графе, указывая направление от начальной вершины к конечной. Граф называется связным, если можно добраться от любой вершины до любой другой по ребрам/дугам.

• Взвешенный граф — граф, в котором вершины или ребра/дуги имеют дополнительную информацию, называемую весом. Например, вес ребра может обозначать расстояние, стоимость или время.
• Путь — это последовательность ребер или дуг, по которой можно перейти из одной вершины в другую.
• Цепь — путь в неориентированном графе, где каждое ребро используется не более одного раза.
• Цикл — путь, в котором начальная и конечная вершины совпадают.
• Сеть — граф, содержащий циклы. Ациклический граф — не содержит циклов.
• Семантическая сеть — граф, где вершины представляют объекты или понятия (например, героев произведения), а ребра/дуги — связи между ними.

Задача о мостах Кёнигсберга

Эта старинная задача, решенная Леонардом Эйлером в 1736 году, спрашивает, можно ли пройти по всем семи мостам города, не проходя ни по одному из них дважды. Эйлер свел ее к задаче обхода графа, где части суши — вершины, а мосты — ребра. Он сформулировал условия обхода графа (эйлерова цикла или пути):

• Если у графа все вершины четные (из каждой выходит четное число ребер), обход возможен, начиная с любой вершины.
• Если у графа две нечетные вершины, обход возможен, но он должен начинаться в одной из нечетных вершин и заканчиваться в другой.
• Если у графа более двух нечетных вершин, обход с использованием каждого ребра ровно один раз невозможен.

Эйлер считается основоположником теории графов.

Деревья как особый вид графа

Дерево — это особый вид связного графа, который не содержит циклов. Главное отличие дерева в том, что между любыми двумя вершинами существует единственный путь. Дерево имеет корень (главную вершину, из которой исходят все остальные) и листья (вершины, не имеющие потомков). Уровень вершины определяется длиной пути от корня (у корня уровень 0). Высота дерева — это максимальный уровень вершины (глубина).

• Поддерево — любая вершина дерева вместе со всеми ее потомками.
• Деревья используются для моделирования иерархических систем (например, генеалогических или родословных деревьев) и решения комбинаторных задач (например, дерево вариантов для перебора комбинаций).
• Дерево игры — это граф, который используется для моделирования действий противоборствующих сторон в соревнованиях, бизнесе или военных действиях, позволяющий разработать план действий, обеспечивающий наилучший результат с учетом возможных ходов противника.