Критерий

Статистический критерий.

Терминология.

Поиск минимальных остовов деревьев.

Метод обхода графа в глубину.

Поиск кратчайших путей.

Алгоритмы Флойда и Дейкстры. Поиск кратчайшего пути (вес, цена и т.д.). матрица, в которой найдены пути определенной длины. Когда мы суммируем два пути через промежуточный узел, меняем значение только в том случае, если сумма оказывается меньше. После этого берем еще один промежуточный и т.д., до тех пор, пока не переберем все варианты. Три цикла, по i, j и k.

Можно так же искать кратчайшие пути, но этот метод будет приближенным. Распределяются все узлы в порядке возрастания либо убывания. Потом берем вершину, которая имеет самое маленькое значение. Там есть ребра различной длины, начальный граф. Далее выбирается из оставшихся ребер то ребро, из них тоже берется минимально. Связываются. Берем то ребро, которое самое короткое. Кратчайший путь между первой и последней вершиной.

Между двумя вершинами существует два пути. Если одна связь порвалась, то есть резервный путь.

А

C

E

D

B

H

G

F

I

Ребра, сумма весов которых минимальна. Остов и обрамление остова. Остов – те узлы графа, которые уже обошли. Обрамление – на расстоянии одного ребра.

Алгоритм Крусскалла (Красскалла).

добавляется до тех пор, пока не закончатся вершины и граф не станет связным.

Эйлеров цикл

Граф неориентированный

Дерево

Ребро

Степень вершины

Порядок графа

Размер графа

Инцидентные ребра и узлы

Смежные

Кратные

Петля

Мультиграф

Псевдограф

Простой граф

Дуга

Ориентированный граф

Смешанный граф

Взвешенный или нагруженный граф

Сеть

Маршрут

Путь – маршрут в орграфе

Длина маршрута

Цикл – цепь, в которой первая и последняя

Эйлеров цикл

Гамильтонов путь (цикл)

Контур – цикл в орграфе

Простой путь или цепь

Ациклический граф

Связный граф или односвязный

Компонента связности графа

Сильно связный граф

Полный граф – в котором две вершины соединены ребром

Плотный граф

Разреженный или ненасыщенный граф

Матрица смежности или примыкания

Матрица инцидентности

Списки примыкания или смежности

29.04.10 г.

На сколько случайной является последовательность?

Хи-квадрат.

S = 2 3 4 5 6 7 8 9 10 11 12 – сумма значений.

Вероятности выпадения того или иного значения: P_s=1/36 + 1/18 + 1/12 + 1/9 + 1/36 + 5/36 + 1/9 + 1/12 + 1/18 + 1/36.

N=144 s = 2 3 4 5 6 7 8 9 10 11 12

Y_s = 2 4 10 12 22 29 21 15 14 9 6

N*P_s = 4 8 12 16 20 24 16 12 8 4

Оценить на сколько теоретические значения отличаются от практических.

V = (Y₂ – np₂)² + (Y₃ – np₃)² + … + (Y₁₂ – np₁₂)² = сумма (Y_s – np_s)²/np_s = 1/n сумма (Y_s²/p_s) – n.

	P=1%
ν=1 ν=2 … ν=5 … ν=10 … ν=50	0,00016     2,6   29,7	3,9				18,3	6,635     23,2   76,2

Значение np_s – должно быть не меньше 5. Для облегчения расчетов, рекомендуется объединять критерии.

Провести эксперимент 3 раза, если попадают в диапазоны 5-10 или 90-95, по 2 раза туда и туда, то генератор считается неудачным.

Случайная величина принимает дискретный ряд значений. Случайная величина принимает значения в диапазоне от 0 до 1.

Дата добавления: 2014-01-05