Деревья.

Как мы уже сказали, сети Петри применяются при моделировании систем. В качестве примера использования сетей Петри рассмотрим задачу моделирования простой вычислительной системы. Система обрабатывает задания, поступающие с устройства ввода, и выводит результаты на устройство вывода. Задания поступают на устройство ввода. Когда процессор свободен и в устройстве ввода есть задание (в обеих входных позициях переходов есть по фишке), процессор начинает обработку задания. Когда задание выполнено, оно посылается в устройство вывода. Процессор же начинает обрабатывать другое задание, если оно поступило, либо ждет прихода задания, если устройство ввода еще не получило такового. Эта система представлена сетью Петри на рис. 5.

Все достижимые маркировки сети Петри представляются графом достижимости.

Маркировка сети М называется достижимой, если при некоторой последовательности срабатываний сети, начиная с начальной маркировки , она переходит к маркировке М.

При выполнении сети Петри получается две последовательности: последовательность маркировок и последовательность переходов, которые были запущены . Обе эти последовательности представляют описание выполнения сети Петри.

Рис. 5.

Дерево-это связный граф без циклов. Граф, не содержащий циклов, называется ацикличным. Можно дать другие определения дерева. Пусть граф G содержит n вершин и m ребер. Следующие утверждения эквивалентны:

1. Граф G – дерево.

2. Граф G – связный и m = n - 1.

3. Любая пара вершин в G соединена единственным путем.

4. Граф G – ацикличный и m = n - 1.

5. Граф G – ацикличный, но добавляя к нему любое новое ребро, мы получаем ровно один цикл.

Будем обозначать дерево буквой T.

Деревом графа G называется связный ацикличный подграф графа G. Дерево T называется остовым деревом графа G, если T – подграф графа G и каждая вершина в графе G является вершиной в дереве T. У каждого связного графа существует подграф, который является остовым деревом.

Рассмотрим пример:

Рис. 1.

На рисунке 1 изображен граф и его остовое дерево.

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

Заметим, что по определению деревья и леса являются простыми графами.

Рассмотрим примеры:

а) б) в)

Рис. 2.

Графы, изображенные на рисунке 2:

1. а – дерево;

2. б – не является деревом, т.к. содержит цикл;

3. в – лес, имеющий 3 компоненты связности.

Дерево должно обязательно иметь висячие вершины. Напомним, что висячей называется вершина, степень которой равна единице. Вершины степени 1 называются листьями. Другие вершины называются внутренними вершинами.

Дерево с одной выделенной вершиной называется корневым деревом или деревом с корнем. При необходимости можно заменить неориентированное корневое дерево T на корневое ориентированное дерево , как показано на рисунке 3.

Рис. 3.

Если корень выбран, уровень вершины v определяется длиной единственного пути корня в вершину v . Высотой дерева называется длина самого длинного пути от корня дерева до листа. Напомним, что длина пути определяется количеством пройденных ребер, таким образом, путь длиною k имеет k ребер. Если рассматривать корневое ориентированное дерево , порожденное данным корневым деревом T, то тогда вершина u называется родителем вершины v, а v называется сыном вершины u , если существует дуга из u в v. Если u – родитель v и , то тогда называются братьями. Если существует ориентированный путь из вершины u в вершину v, то тогда u называется предком вершины v, а v – потомком вершины u . Если наибольшая из степеней выхода для вершин дерева равна m, то дерево называется m-арным деревом. При m = 2, дерево называется бинарным деревом. В бинарном дереве каждый сын обозначается как левый, либо как правый сын.Рассмотрим пример.

Рис. 4.

Граф на рисунке 4 – бинарное дерево. Уровень вершины равен 2, уровень вершины равен 3. Высота дерева равна 3, т. к. длина пути равна 3 и не существует более длинного пути от корня к листу. Напомним, что длиной пути. Вершина является родителем для вершин и . Вершины и , например, братья. Вершина - предок вершин ,,, , соответственно, указанные вершины являются потомками . Вершина – левый сын вершины , а вершина – правый сын вершины .

Мы рассмотрели корневое ориентированное дерево, образованное из неориентированного корневого дерева. Теперь дадим общее определение ориентированного корневого дерева. Ориентированное дерево называется корневым ориентированным деревом, если существует единственная вершина такая, что полустепень входа и существует путь из в каждую другую вершину дерева. Ориентированное дерево на рисунке 2. удовлетворяет этому определению. Вместе с тем дерево, приведенное на рисунке 5, не является корневым ориентированным деревом.

Рис. 5.

На основе бинарного дерева строится бинарное дерево поиска, реализуется алгоритм сжатия данных Хаффмана,