4.2. Распределение с древообразной структурой зависимостей

4.2.1. Предварительные сведения из теории графов.

Изложение начнем с напоминания основных понятий теории графов [134].

Определение 4.1. Простым графом G называется пара где — непустое конечное множество элементов, называемых вершинами графа — множество вершин G), а — конечное множество неупорядоченных пар различных элементов из , называемых ребрами графа G ( — множество ребер G). В дальнейшем термин «простой» опускается. Отметим, что так как Е (G) определено как множество, а не как совокупность и состоит из неупорядоченных элементов, то в графе G каждую пару вершин может соединять не более чем одно ребро а). В дальнейшем (как и на рис. 4.1 и 4.2) вершины графа мы будем отождествлять с координатами вектора, а ребра графа — со связями.

Определение 4.2. Граф называется подграфом G, если

Определение 4.3. Конечная непустая последовательность ребер графа называется простой цепью, соединяющей вершины если все вершины различны, кроме, быть может,

В последнем случае простая цепь называется циклом.

Определение 4.4. Граф G называется связанным, если для любых его вершин а и b существует простая цепь, соединяющая а и b.

Определение 4.5. Лесом называется граф, не содержащий циклов, связанный лес называется деревом.

Графы, изображенные на рис. 4.1 и 4.2, связанные и не имеют циклов. Следовательно, их можно назвать деревьями. На них легко проверяются утверждения следующей теоремы.

Теорема 4.1 [134]. Определяющие свойства графа-дерева. Пусть граф Т имеет вершин, тогда следующие утверждения эквивалентны: 1) Т является деревом; 2) Т не содержит циклов и имеет () ребер; 3) Т связан и имеет () ребер; 4) любые две вершины Т соединены ровно одной простой цепью; 5) Т не содержит циклов, но, добавляя к нему любое новое ребро, мы получим ровно один цикл.