Свойства операций над множествами

Классификация графов

Существует значительное число разновидностей графов. В каждом конкретном случае возможно применение того или иного типа графа. Возможно поэтапное преобразование графа одного типа в граф другого без изменения информационного наполнения графа. Эти преобразования называются изоморфными. При этих преобразованиях сохраняется неизменным число вершин графа и их соединения. Приведем наиболее применяемые разновидности графов.

· Неориентированный граф – граф, в котором не указано направление рёбер; например, граф, описывающий принципиальную электрическую схему.

· Ориентированный граф – граф, в котором указана ориентировка ребер.

· Конечный граф – граф, число вершин в котором конечно. В основном дело имеют с конечными графами.

· Пустой граф – граф, в котором число вершин и рёбер равно нулю.

· Полный граф – граф, в котором все вершины соединены между собой рёбрами.

· Связный граф – такой граф, в котором можно соединить последовательностью рёбер любые две вершины. Этот граф нельзя разделить на отдельные несвязные подграфы.

· Несвязный граф – граф, в котором нельзя соединить хотя бы две вершины последовательностью рёбер. Такой граф можно разделить на несколько независимых подграфов.

· Планарный граф – граф, который может быть изображен на плоскости без пересечения рёбер. Определение планарности – задача нетривиальная и для этого используются специальные алгоритмы. Однако существуют два типа заведомо непланарных графа (графы Куратовского), и, если они входят в состав исходного графа, то последний не является планарным.

· Плоский граф – уже изображенный на плоскости без пересечения рёбер. Плоский граф – модель реализации односторонней печатной платы. Плоский граф получают из планарного изоморфными преобразованиями графа.

2. Элементы графа

Для реализации алгоритмов необходимо знать элементы графа, его части и структурные свойства. Основными элементами графа являются вершины и ребра.

Смежными рёбрами называются два ребра, которые подходят к одной вершине, или выходят из неё. Иногда говорят, что эти рёбра инцидентны вершине.

Степень r (X_i) вершины X_i – это число инцидентных ей рёбер. Если ни одного ребра к вершине X_i не подходит, то r (X_i) = 0; если подходит одно ребро, то r (X_i) = 1 и т.д..

Части графа

Различают подграф и кусок графа.

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

Кусок получается разделением исходного графа путём "перерезания" рёбер. При разделении графа на куски не происходит образования новых вершин, которые распределяются по кускам. Ребра в этом случае разделяются на внутренние ребра кусков и на соединительные ребра (которые были "разрезаны"), соединяющие куски. Их число минимизируется при выполнении задачи разбиения.