Свойства операций над множествами
Свойства коммутативности (объединения, пересечения); Свойства ассоциативности; Ассоциативность объединения множеств; Ассоциативность пересечения множеств; Свойства дистрибутивности; Дистрибутивность пересечения относительно объединения; Дистрибутивность объединения относительно пересечения; Свойства универсального множества; Свойства пустого множества; Законы идемпотентности объединения и пересечения; Законы Де Моргана; Закон снятия двойного дополнения; Законы поглощения: Классификация графов Существует значительное число разновидностей графов. В каждом конкретном случае возможно применение того или иного типа графа. Возможно поэтапное преобразование графа одного типа в граф другого без изменения информационного наполнения графа. Эти преобразования называются изоморфными. При этих преобразованиях сохраняется неизменным число вершин графа и их соединения. Приведем наиболее применяемые разновидности графов. · Неориентированный граф – граф, в котором не указано направление рёбер; например, граф, описывающий принципиальную электрическую схему. · Ориентированный граф – граф, в котором указана ориентировка ребер. · Конечный граф – граф, число вершин в котором конечно. В основном дело имеют с конечными графами. · Пустой граф – граф, в котором число вершин и рёбер равно нулю. · Полный граф – граф, в котором все вершины соединены между собой рёбрами. · Связный граф – такой граф, в котором можно соединить последовательностью рёбер любые две вершины. Этот граф нельзя разделить на отдельные несвязные подграфы. · Несвязный граф – граф, в котором нельзя соединить хотя бы две вершины последовательностью рёбер. Такой граф можно разделить на несколько независимых подграфов.
· Планарный граф – граф, который может быть изображен на плоскости без пересечения рёбер. Определение планарности – задача нетривиальная и для этого используются специальные алгоритмы. Однако существуют два типа заведомо непланарных графа (графы Куратовского), и, если они входят в состав исходного графа, то последний не является планарным. · Плоский граф – уже изображенный на плоскости без пересечения рёбер. Плоский граф – модель реализации односторонней печатной платы. Плоский граф получают из планарного изоморфными преобразованиями графа. 2. Элементы графа Для реализации алгоритмов необходимо знать элементы графа, его части и структурные свойства. Основными элементами графа являются вершины и ребра. Смежными рёбрами называются два ребра, которые подходят к одной вершине, или выходят из неё. Иногда говорят, что эти рёбра инцидентны вершине. Степень r (Xi) вершины Xi – это число инцидентных ей рёбер. Если ни одного ребра к вершине Xi не подходит, то r (Xi) = 0; если подходит одно ребро, то r (Xi) = 1 и т.д.. Части графа Различают подграф и кусок графа. Подграф получают разбиением исходного графа по его вершинам. В этом случае вершины, по которым происходит разбиение, дублируются в подграфах, а ребра распределяются по ним. Кусок получается разделением исходного графа путём "перерезания" рёбер. При разделении графа на куски не происходит образования новых вершин, которые распределяются по кускам. Ребра в этом случае разделяются на внутренние ребра кусков и на соединительные ребра (которые были "разрезаны"), соединяющие куски. Их число минимизируется при выполнении задачи разбиения.
Читайте также: A- механические свойства материала из которого будет изготовлен протез Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|