1.3 Графическое представление иерархической структуры системы
1.3.1 Графы и деревья. Основные понятия, формализация информации в виде матриц смежности и инцидентности.
Материальная система, которая состоит из двух множеств: точек (вершин, узлов, блоков, мест) и линий (связей, рёбер), которые находятся между собой в каком-либо отношении называется графом. Множество точек соответствует множеству вершин
Множество линий, соединяющих пары вершин, называется множеством ребер или дуг
Граф, содержащий только ориентированные линии, называется ориентированным графом или орграфом. Граф, содержащий только неориентированные линии, называется неориентированным графом. Граф, у которого существует хотя бы одна пара вершин, соединяемых m ребрами (m >= 2), называется мультиграфом, а наибольшее число m называется мультичислом графа.
Ребра, соединяющие одну и ту же пару вершин, называются кратными. Ребро, соединяющее две вершины называется инцидентным, а вершины инцидентны ребру. Смежными называют две вершины, если есть соединяющее их ребро; два ребра инцидентны одной вершине.
Конечный граф – граф, включающий конечное множество узлов и связей (X и U). Нулевой граф – граф, в котором вершины не соединены ребрами, при этом множество U пустое U = <>. Полный граф — граф, в котором каждая пара вершин соединена ребром.
Степень вершины — число ребер, инцидентных данной вершине. Граф, степени всех вершин которого равны K, называется однородным или регулярным графом степени К. Подграф — часть графа, образованная некоторым подмножеством ребер графа и всеми инцидентными им вершинами. Суграф — часть графа, образованного удалением из исходного графа некоторых ребер.
Квадратная матрица R[n, n] называется матрицей смежности, если ее столбцы и строки образованы вершинами графа (i = 1, … i = n; j = 1, … j = n), а значения в ячейках таблицы R[i, j] показывают наличие связей между вершинами. Если R[i, j] = 1 то Xi смежно с Xj а если вершины не соединены R[i, j] = 0. Если граф неориентированный то R[i, j] =R[j, i].
Прямоугольная матрица S[n, m] называется матрицей инцидентности, если ее строки образованы вершинами графа (i = 1, … i = n), а столбцы — связями (j = 1, … j = m) или наоборот. Элементы в ячейках образуются по правилу Sij = 1, если связь (ребро) Uj выходит из Xi ; Sij = — 1, если связь Uj входит в Xi.. Если ребро Uj не связано с вершиной Xi , то Sij = 0.
1.3.2 Особенности выделения уровней иерархии
Для описания иерархической структуры конкретных систем (изделий) обычно применяются И – деревья. Эти деревья представляют собой совокупность вершин и связывающих их ребер, сгруппированных на различных иерархических уровнях (ярусах). Каждый иерархический уровень представляет собой проектируемую систему с различной степенью детализации. Нулевой иерархический уровень (система) является наиболее абстрактным, а последний – наиболее детализированным.
Количество уровней декомпозиции должно соответствовать поставленной задаче. Минимальная неделимая часть в рамках задачи называется элементом. Дерево не всегда отражает чисто конструктивную декомпозицию объекта.
Применение иерархической декомпозиции помогает формировать словарь предметной области, в которой существует рассматриваемая система, и позволяет выделить базовые понятия (абстракции) предметной области, которые необходимы при ее анализе, в том числе и при создании САПР [3]. Кроме того, на каждом уровне абстракции применяются свои принципы и методики описания системы, соответствующие степени ее декомпозиции.
Таким образом, разбиение объекта находится в рамках блочно — иерархического подхода к структурному описанию объектов. Вершины отображают составные части проектируемого объекта. Рёбра отражают всевозможные связи между вершинами (механические, тепловые, электрические). При создании программных продуктов указывают, например, потоки данных между блоками, модулями. Вершины (элементы) самого нижнего яруса (иерархического уровня) в рамках принятого представления сложной системы – (например автомобиля) называются базовыми элементами или листьями. Таким образом И – дерево является представлением конкретной системы, в котором элементы объединены связями в узлах И, в соответствии с иерархической декомпозицией системы (рис. 8). Поскольку все узлы одинаковы (имеют тип И), их иногда на рисунках не показывают.
Техническое решение для системы, представленной И-деревом, на каждом уровне абстракции включает в себя информацию обо всех элементах системы. Эти элементы представляют собой множество конструктивных решений (деталей, узлов), предназначенных для выполнения функций системы. Дерево И может включать также информацию об особенностях конструктивного исполнения элементов: о геометрической форме, основных признаках и параметрах.
Источник
Информационные модели на графах. Схемы. Информатика.
Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Если линия направленная (со стрелкой), то она называется дугой;линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. Вершины могут изображаться кругами, овалами, точками, прямоугольниками и т. д.
Если объекты некоторой системы изобразить вершинами, а связи между ними — линиями, то мы получим информационную модель рассматриваемой системы в форме графа.
Ранее мы рассматривали графы — схемы отношений, отражающие имеющиеся связи между объектами.
Например, граф, отражающий отношение «переписываются» между объектами класса «дети», может выглядеть, как показано на рис. 44.
Отношение «переписываются» («пишут письма друг другу») является двухсторонним (симметричным). Поэтому соответствующие вершины соединены линиями без стрелок (рёбрами).
Граф называется неориентированным, если его вершины соединены ребрами.
Путь по вершинам и рёбрам графа, включающий любое ребро графа не более одного раза, называется цепью.
Пример цепи: Юра — Аня — Витя — Коля (см. рис. 44).
Цепь, начальная и конечная вершины которой совпадают, называется циклом.
Пример цикла: Аня — Коля — Витя — Аня.
Иначе выглядит граф, отражающий отношение «пишет письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл (рис. 45).
Граф называется ориентированным, если его вершины соединены дугами.
Приведите примеры цепи и цикла в графе на рис. 45.
Граф называется взвешенным, если его вершины или рёбра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).
На рисунке 46 информация о городах Золотого кольца представлена взвешенным графом: веса его вершин — года основания городов, веса рёбер — расстояния в километрах между городами.
Назовите пути и циклы в графе на рис. 46.
Граф с циклами называется сетью.
На рисунке 47 в виде графа представлена информационная модель сказки про Царевну-лягушку.
Вершины этого графа — персонажи и предметы из сказки, дуги — связи между ними. В отличие от предыдущих примеров, здесь все связи различны. Поэтому они подписываются рядом с соответствующими дугами.
Такой граф называется семантической сетью. Считается, что любую информацию можно представить в виде семантической сети, на которой будут отражены объекты (понятия) и связи (отношения) между ними.
Деревья (Граф иерархической системы)
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчинённости, называются иерархическими системами (системами с иерархической структурой).
Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчинённости: директор — заместители директора — учителя — ученики.
Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».
На рисунке 48 изображён граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порождённых вершин, называются листьями.
Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов (рис. 49).
Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:
По иерархическому принципу организована система хранения файлов во внешней памяти компьютера. Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева (рис. 50).
Родственные связи между членами семьи удобно изображать с помощью схемы, называемой генеалогическим или родословным деревом. Изображать генеалогическое дерево можно в любом направлении — это дело вкуса разработчика модели.
Источник