4.5. Дерево и лес

Н-граф называется неориентированным деревом (деревом), если он связан и не содержит циклов, а, следовательно, петель и кратных ребер.

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

Наличие связанности и отсутствие циклов позволяет жестко связать число вершин и ребер: в дереве с n вершинами всегда (n-1) ребро.

Лес – несвязанный н-граф без циклов; связанные компо­ненты леса – деревья. Любая часть леса или дерева также не имеет циклов, т.е. является лесом или деревом. Любая цепь в таком графе – простая, иначе она содержала бы цикл. В неориентированном де­реве, между любыми двумя вершинами существует цепь, и притом только одна.

Вершина vG называется концевой, или висячей, если ее степень (v)=1. Ребро, инцидентное концевой вершине называется концевым.

Ориентация неориентированного дерева происходит так:

В дереве G выбирается вершина v₀ – так называемый корень дерева G и все ребра такого дерева с корнем ориентируются от него. При выборе другого корня получаем другой орграф-дерево.

Пусть v- вершина дерева G с корнем v₀; B(v) – множество всех вершин, связанных с корнем цепями, проходящими через вер­шину v. Это множество порождает подграф G(v), называемый вет­вью вершины v в дереве с корнем v₀. Если дерево имеет более двух вершин, то среди них есть неконцевые.

Пусть дано конечное дерево G. Вершинами типа 1 назы­вают его концевые вершины. Если из дерева G удалить все вершины типа 1 и инцидентные им концевые ребра, то в оставшемся дереве G' концевые вершины называются вершинами типа 2 в дереве G. Аналогично определяются вершины типа 3, 4 и т.д. Конечное дерево имеет вершины лишь конечного числа типов, причем число вершин максимального типа равно единице или двум.

Цикломатическим числом конечного н-графа G называется

V(G)=V_c+ V_e+ V_V,

где V_c - число связанных компонент графа; V_e - число его ре­бер; V_V - число вершин. V(G) для любого конечного н-графа неотри­цательно. Цикломатическое число любого дерева и леса равно нулю. Действительно V­_c- V­_е =1, а число связанных компонент дерева V­_c=1.

4.6. Сети

Обобщим понятие графа.

Определение: Множество М={a₁, a₂,…} и набор N={E_o, E₁, E₂,...}, в котором каждое E­_i­ есть набор элементов из М, т.е. называется сетью и обозначается M={E_o; E₁; E₂,...}. Объекты множества М называются вершинами, а объекты из набора Е­₀ – полюсами сети.

Пример 4:

M={1,2,3,4,5,6,7,}, N={E_o, E₁, E₂, E₃, E₄, E₅},

где E₀=(1,2,6); E₁=(1,3,3,4,5); E₂=(4,4,4,5,6); E₃=E₄=(2,4), E₅=(2,5,6,7);

тогда M={E_o; E₁; E₂, E₃, E₄, E₅} будет сетью.

Если множество М и набор N конечны, сеть называется

конеч­ной.

Сеть, в которой бесконечно хотя бы М или N называется бесконечной. Частным случаем бесконечных сетей являются счетные сети, т.е. те, у которых М и N не более чем счетны.

Для любой счетной сети определена ее геометрическая реализация. Например, для рассмотренной сети:

Ф игура напоминает схему радиоприемника, из которой удалены все элементы: сопротивления, емкости, индуктивности и.т.д.

Определение: Сети M'={E_o'; E₁'; E₂',...} и M={E_o; E₁; E₂,...} называются изоморфными, если можно установить взаимно-однозначное соответствие между объектами множеств M' и M, а также между объектами из N' и N так, что:

1) соответствующие наборы E' и E состоят из соответствующих объектов (с учетом кратности их вхождения);

2) наборы E₀' и E₀ соответствуют друг другу.

Очевидно, что абстрактная сеть изоморфна своей геометриче­ской реализации. И поскольку интерес представляют сети с точно­стью до изоморфизма, то будем считать, что сети представляют со­бой геометрические объекты.

Очевидно, что класс сетей, у которых E₀ не определен и каж­дый набор E_i состоит из двух объектов множества М, совпадает с классом графов.