Запись графа в таблицу вершин

1 – 0,

2-1, 3-1, 4-2,5-2, 6-3, 7-3, 8-4, 9-4,10-5, 11-5, 12-6, 13-6, 14-7, 15-7,

16-8, 17-8, 18-9,19-9, 20-10, 21-10, 22-11, 23-11, 24-12, 25-12, 26-13, 27-13, 28-14, 29-14, 30-15, 31-15.

Таблица висячих вершин

16-8,17-8, 18-9, 19-9, 20-10, 21-10, 22-11,23-11, 24-12, 25-12, 26-13, 27-13, 28-14, 29-14, 30-15, 31-15.

________

1

2

4

8

16

31

Число всех узлов Р = 31

Число висячих вершин В = 16

Число путей П = 16

, =16 , В=Р/16

=2

Число путей П = число узлов ветвления +1 = 15 + 1 = 16

Алгоритм образования случайного графа-дерева

1.Граф рассматривается по уровням (послойно). На первом уровне всегда одна вершина (узел).

2.Число вершин (узлов) на втором уровне и всех последующих определяется числом ребер, исходящих и входящих в/ из узлов-родителей. Число этих ребер назначается при помощи датчика случайных чисел. Случайное число должно быть распределено равномерно в диапазоне 0 …1.

3. Настройки датчика случайных чисел производятся исходя из минимального числа ребер, исходящих из каждой вершины (узла) – 0, максимального – (m – 1).Для расчета случайного графа число m – задается в исходных данных. Например, еслиm – 1 = 3 (m=4),то диапазон случайных значений числа выходящих из узла ребер

либо 0, либо 1, либо 2, либо 3.

4. Вершины (узлы) каждого уровня помещаются в свою строку «таблицы вершин». По каждой строке таблицы проводится подсчет количества вершин.

Расчет графа и строкообразование таблицы не может продолжаться бесконечно. Этот процесс останавливается в соответствии с исходными данными и в соответствии с правилом остановки.

5.Правила остановки вычислений для построения графа.

В работе применено два правила остановки вычислений для построения графа: правило А и правило В.

Правило А – построение графа прекращается при достижении числа узлов заданного значения N.

Правило В-построение графа прекращается при выполнении двух условий. Первое условие - число узловзаданному числуN. Второе условие- последний уровень иерархии графа должен быть до конца заполнен висячими узлами иными словами во всех узлах предыдущего уровня процесс генерации узлов должен быть проведен.

Для этого в алгоритме построения графа с правилом остановки В необходимо запоминать имя последнего узла каждого уровня после чего проверять первое условие. Иными словами по правилу В расчет графаведется до тех пор, пока сумма числа узлов Q по всем завершенным строкам( уровням иерархии графа)не станетзаданного числа.

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

Для правила остановки А к висячим узлам надо добавить и узлы предпоследнего уровня, не успевшие дать потомков из-за остановки вычислений

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

6. Производится подсчет числа путей на графе. Это число характеризует, трудоемкость отладки ПО. Для дерева – это число висячих вершин. Подсчитывается также число уровней иерархии графа.

Производится подсчет параметра 

Число всех вершин

= ----------------------------- .

Число висячих вершин

Данное число является случайным, так как получено с помощью датчика случайных чисел.

7. Расчет построения повторяется для другого случайного графа, который образуется по описанному алгоритму (в цикле) при других значениях случайного числа ребер исходящих из узлов графа, но при тех же исходных данных mиN

Число построенных случайных графов Rзадается в исходных данных к заданию

8. Если при первом шаге для верхней вершины (корневой) датчик случайных чисел показывает 0 потомков ( такое вполне может быть), то расчет графа прекращается и делается следующая попытка. Это справедливо только для первого шага. Этот случай в отчете и при подсчете Rне учитывается.

9. Если граф обрывается ( такое вполне может быть при небольших значениях mв частности приm=3) при числе построенных узлов меньше 10 , то эта реализация также в отчет и счетчикRне берется см. п8.

10. В результате построения Rслучайных деревьев получаетсяRслучайных значений параметра. Необходимо вычислить математическое ожидание этого параметра и привести его в отчете.