0, c - цілі числа. Параметр с може бути негативним, проте він повинен задовольняти умові b + r + c (n - 1) gt; 0.
Рис. 1 Приклад Розподіл Пойа 1 (Вадзінскій Р.Н. Довідник з теорії ймовірності. Санкт-Петербург., 2001. с. 88)
Генерування випадкових чисел
(Вадзінскій Р.Н. Довідник з теорії ймовірності. Санкт-Петербург., 2001. с. 88)
Алгоритм реалізує стандартний спосіб імітації моделювання дискретних випадкових величин. Імовірність p0=P (X=0) обчислюється за формулою (1) (оператор (*)). Функція? (Х) обчислюється за формулою? (Х)=(n - 1 - x) [b + (x - 1) c]/{x [r + (nx) c]} (оператор (**)).
Алгоритм реалізований з урахуванням того, що ступінь вершини графа може бути рівної 0 або n, і що сума всіх ступенів графа спочатку повинна бути парному. В алгоритмі проводиться перевірка, і якщо х=0, вершині присвоюється ступінь 1, а максимальна ступінь спочатку може бути тільки в однієї (найчастіше середньої вершини).
Реалізація алгоритму
vector lt; int gt; Valency (vector lt; int gt; vertex)
{n=vertex.size ();// n - к-ть вершин
int b=3, c=1, key=0, sum=0; r=20, p0=1; (int i=1; i lt;=n; i ++)//генерування р=ро=p0 * (r + (i - 1) * c)/(b + r + (i - 1) * c); (int v=0; v lt; n; v ++)
{p=p0, be=(n + 1) * 100 ./ (1.05 + v); x=0, rafiky=be;=(rand ()% rafiky)/100 .; =R - p; (r gt; 0)
{(x lt; n - 1)
{++;=p * (n - 1 - x) * (b + (x - 1) * c)/(x * (r + (n - x) * c)) ;=r - p;
}
{[v]=(n - 2); break;
}
} (x == n - 1)
{(! key)//щоб був один максимум
{[v]=n - 2; ++;
}
} (x == 0) [v]=1; if (x!=0 || x lt; n - 2)
vertex [v]=x;
//перевірка на парність
sum +=vertex [v];
} (sum amp; 1)
{-=vertex [n/2]; (! key)
{[n/2]=n - 1; +=vertex [n/2]; ++;
}
{[n/2]=rand ()% (n - 2) +1; +=vertex [n/2];
}
} vertex;}
Рис. 3 Графік функції ймовірності розподілу Пойа 1 для 100 вершин.
Формування зв'язкового ациклического графа відповідно до розподілу Пойа 1
Граф називається зв'язковим, якщо для будь-якої пари різних вершин цього графа існує ланцюг, що з'єднує ці вершини. Циклом називають ланцюг, в якій перша і остання вершини збігаються. Відповідно ациклічності граф той, який не містить циклів.
Принцип побудови графа:
Граф будується орієнтований.
Функцією FindMax () вибирається вершина з найбільшим ступенем на даний момент з масиву ступенів вершин (якщо ступеня рівні, то береться та, чий номер менше). Ця вершина викреслюється зі списку можливих зв'язків. З решти вершин, не пов'язаних ще даної, функцією FindMax () вибирається вершина з максимальним ступенем (якщо ступеня рівні, то береться та, чий номер більше). Далі між собою порівнюються номера, обраних для зв'язку вершин, чий номер більше - від тієї вершини і буде виходити дуга. Після кожної зв'язку ступінь з'єднаних вершин зменшується на 1. Алгоритм повторюється, до тих пір, поки всі ступені вершин не обнуляться.
Даний алгоритм створює граф із кратними ребрами, однак потім, при побудові матриці суміжності, все кратні ребра виключаються.
Функція FindMax ()
Ця функція знаходить номер вершини з максимальним ступенем, в масиві ступенів вершин. При цьому, можна контролювати пошук максимуму: можна брати мінімальний або максимальний номер якщо є кілька вершин з максимальним ступенем.
int FindMax (vector lt; int gt; vertex, bool MorD)
{k=0; n=vertex.size (); (! vertex (k)) k ++; (int j=0; j lt; n; j ++)
{(vertex (j) amp; amp; k!=j)
{(vertex (k) lt; vertex (j))=j; (vertex (k) == vertex (j) amp; amp;! MorD)
k=j;
}
} k;
}
Реалізація алгоритму побудови зв'язного ациклічності графа:
vector lt; vector lt; int gt; gt; MakeGraph ()
{n=1;
cout lt; lt; endl lt; lt; Введіть кількість вершин (число повинне бути цілим, з...
