Введение в анализ схем (графов)

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

Автор: С. В. Чайченков, МБОУ Грушевская СОШ

Основные понятия и определения

Справочная информация:

• Графы — графические информационные модели для отображения систем. Объекты системы изображаются вершинами, а связи между ними — линиями (рёбрами).
• У взвешенного графа вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
• Цепь — это путь по вершинам и рёбрам графа, в который любое ребро графа входит только один раз (например, С-D-E).
• Цикл — цепь, начальная и конечная вершины которой совпадают (например, С-D-E-C).
• Сеть — граф с циклом.
• Дерево — граф иерархической системы (между любыми двумя вершинами дерева существует единственный путь). Вершина верхнего уровня называется корнем.

Примеры:

Табличные информационные модели

Справочная информация:

Табличные информационные модели представляют информацию об объектах в наглядной форме в виде прямоугольной таблицы, состоящей из столбцов и строк. Таблица типа «объект-объект» — это таблица, содержащая информацию о некотором одном свойстве пар объектов одного или разных классов.

Например, приведённый ранее взвешенный граф может быть схемой дорог, соединяющих населённые пункты А, В, С, D, Е. Этому графу соответствует следующая таблица (весовая матрица):

Одной и той же таблице могут соответствовать графы, внешне не похожие друг на друга.

Заключение

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

Автор: С. В. Чайченков, МБОУ Грушевская СОШ