Граф - это средство для наглядного представления состава и структуры системы.
Граф состоит из вершин, связанных дугами или ребрами. Вершины могу быть изображены кругами, овалами, точками, прямоугольниками т.д. Связи между вершинами изображаются линиями. Если линия направленная (т.е. со стрелкой), то она называется дугой, если не направленная (без стрелки), то ребром. Одно ребро заменяет две дуги, направленные в противоположные стороны.
Граф, в котором все линии направленные, называется ориентированным графом. Две вершины, соединенные дугой или ребром, называются смежными.
В случае представления информации о составе и структуре системы в виде графа компоненты системы изображаются вершинами, а связи между ними - линиями.
Примеры.
Взвешенный граф - это граф, в котором с вершинами или линиями связана некоторая дополнительная информация - вес вершины или линии. Вес позволяет отобразить на графе не только структуру системы, но и различные свойства компонент и связей, количественные характеристики.
Дерево - это граф, предназначенный для отображения таких связей между объектами, как вложенность, подчиненность, наследование и т.п. В дереве существует только одна вершина 1-вершина 1-го уровня - корень дерева, которая не зависит ни от одной другой вершины.
Дерево может быть неориентированным, но чаще всего дерево ориентированно, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин, а нижние вершины - потомками соответствующей верхней вершины. На любом дереве существует единственная вершина, не имеющая предка, - корень, и может быть сколько угодно вершин, не имеющих потомков, - листьев. Все остальные вершины имеют ровно одного предка и сколь угодно потомков. Такая структура называется иерархической.
В виде дерева удобно изображать системы, в которых нижние вершины в каком-то смыле "подчинены" верхним. Примеры: классификация животного мира, иерархия власти, файловая система компьютера, генеалогическое древо семьи, оглавление книги и т.д.
Алгоритм построения графа в виде дерева
Граф состоит из вершин, связанных дугами или ребрами. Вершины могу быть изображены кругами, овалами, точками, прямоугольниками т.д. Связи между вершинами изображаются линиями. Если линия направленная (т.е. со стрелкой), то она называется дугой, если не направленная (без стрелки), то ребром. Одно ребро заменяет две дуги, направленные в противоположные стороны.
Граф, в котором все линии направленные, называется ориентированным графом. Две вершины, соединенные дугой или ребром, называются смежными.
В случае представления информации о составе и структуре системы в виде графа компоненты системы изображаются вершинами, а связи между ними - линиями.
Примеры.
Взвешенный граф - это граф, в котором с вершинами или линиями связана некоторая дополнительная информация - вес вершины или линии. Вес позволяет отобразить на графе не только структуру системы, но и различные свойства компонент и связей, количественные характеристики.
Дерево - это граф, предназначенный для отображения таких связей между объектами, как вложенность, подчиненность, наследование и т.п. В дереве существует только одна вершина 1-вершина 1-го уровня - корень дерева, которая не зависит ни от одной другой вершины.
Дерево может быть неориентированным, но чаще всего дерево ориентированно, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин, а нижние вершины - потомками соответствующей верхней вершины. На любом дереве существует единственная вершина, не имеющая предка, - корень, и может быть сколько угодно вершин, не имеющих потомков, - листьев. Все остальные вершины имеют ровно одного предка и сколь угодно потомков. Такая структура называется иерархической.
В виде дерева удобно изображать системы, в которых нижние вершины в каком-то смыле "подчинены" верхним. Примеры: классификация животного мира, иерархия власти, файловая система компьютера, генеалогическое древо семьи, оглавление книги и т.д.
Алгоритм построения графа в виде дерева
