Информационные модели на графах. Основные понятия
Граф — это средство для наглядного представления состава и структуры системы.
Граф состоит из вершин, связанных дугами или ребрами. Вершины могут быть изображены кругами, овалами, точками, прямоугольниками и пр. Связи между вершинами изображаются линиями. Если линия направленная (т.е. со стрелкой), то она называется дугой, если не направленная (без стрелки), то ребром. Принято считать, что одно ребро заменяет две дуги, направленные в противоположные стороны. Граф, в котором все линии направленные, называется ориентированным графом. Две вершины, соединенные дугой или ребром, называются смежными.
В случае представления информации о составе и структуре системы в виде графа компоненты системы изображаются вершинами, а связи между ними — линиями (дугами или ребрами).
Графы используются во многих областях практической и научной деятельности людей.
Дерево — это граф, предназначенный для отображения таких связей между объектами как вложенность, подчиненность, наследование и т.п.
Строится он следующим образом. Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной «1-го уровня». Далее добавляем вершины «2-го уровня». Их может быть сколько угодно, и все они обязательно связаны с корнем — вершиной 1-го уровня, но не связаны между собой. На следующем шаге добавим вершины 3-го уровня. Каждая из них будет связана ровно с одной вершиной 2-го уровня и не связана ни с одной другой вершиной. К любой вершине 2-го уровня может быть подсоединено сколько угодно вершин 3-го уровня (в том числе, ни одной). Следующий шаг — добавка вершин 4-го уровня, каждая из которых будет связана ровно с одной вершиной 3-го уровня и не связана больше ни с чем. И так далее. На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей.
|
|
|
Полученный граф напоминает ветвящийся куст, который «растет сверху вниз»: верхние уровни имеют меньшие номера, нижние — большие. Граф из примера 4, отражающий состав шариковой ручки, является деревом. Корень этого дерева — вершина «Шариковая ручка». Графы из примеров 3 и 5 деревьями не являются.
Вообще говоря, дерево может быть и неориентированным графом, но чаще дерево ориентировано, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин, а нижние вершины — потомками соответствующей верхней вершины.
На любом дереве существует единственная вершина, не имеющая предка, — корень — и может быть сколько угодно вершин, не имеющих потомков, — листьев. Все остальные вершины имеют ровно одного предка и сколько угодно потомков.
|
|
|
Если не принимать во внимание направленность связей, то в дереве из любой вершины можно по линиям дойти до любой другой вершины, причем по одному единственному пути.
В виде дерева удобно изображать системы, в которых нижние вершины в каком-то смысле «подчинены» верхним. Верхняя вершина может изображать начальника, нижние — подчиненных; верхняя — систему, нижние — ее компоненты; верхняя — множество объектов, нижние — входящие в него подмножества; верхняя вершина — предка, нижние — потомков и т.д.
10.3. Задание на лабораторную работу
Задания распределяются в зависимости от выданного преподавателем mn-кода. Если m — число нечетное, то ваш вариант 1, если четное — вариант 2.
Задание 1.Пусть структура системы изображается графом, приведенным на рисунке
Дата добавления: 2018-04-15; просмотров: 787; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!