Главная / Алгоритмы и дискретные структуры /
Графы и их применение / Тест 10
Графы и их применение - тест 10
Упражнение 1:
Номер 1
Какая вершина в ориентированном графе D
называется изолированной?
Ответ:
 (1) вершина, у которой и степень входа и степень выхода равны 0 
 (2) вершина, степень выхода которой положительна, а степень входа равна 0 
 (3) вершина, степень входа которой положительна, а степень выхода равна 0 
 (4) вершина, степень выхода и степень входа которой положительны и равны 
Номер 2
Что называется путем в ориентированном графе D
?
Ответ:
 (1) путем в ориентированном графе D
от v1
до vn
называется последовательность ориентированных дуг (ребер) (v1,v2),(v2,v3),...,(vn-1,vn)
, такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза 
 (2) если существует замкнутая цепь, проходящая через каждую вершину орграфа, то такая цепь называется путем в орграфе 
 (3) если существует разомкнутая цепь, проходящая через все вершины орграфа степени единица, то такая цепь называется путем 
 (4) путем в ориентированном графе D
от v1
до vn
называется последовательность ориентированных дуг (ребер) 
Номер 3
Что называется вектором вероятностей?
Ответ:
 (1) вектор-строка, все компоненты вектора неотрицательны и дают в сумме единицу 
 (2) вектор-строка, все компоненты вектора отрицательны и дают в сумме минус единицу 
 (3) вектор-строка, все компоненты вектора неотрицательны и дают в сумме нуль 
 (4) вектор-строка, все компоненты вектора отрицательны и дают в сумме нуль 
Упражнение 2:
Номер 1
Что называется матрицей перехода?
Ответ:
 (1) матрица перехода определяется как квадратная матрица, в которой каждая строка является вектором вероятностей 
 (2) матрица перехода определяется как прямоугольная матрица, в которой каждая строка является вектором вероятностей 
 (3) матрица перехода определяется как единичная матрица, в которой каждая строка является вектором вероятностей 
 (4) матрица перехода определяется как квадратная матрица, в которой каждая строка содержит только простые числа 
Номер 2
Когда цепь Маркова неприводима?
Ответ:
 (1) тогда и только тогда, когда ее ассоциированный орграф сильно связан 
 (2) тогда и только тогда, когда ее ассоциированный орграф слабо связан 
 (3) тогда и только тогда, когда ее ассоциированный орграф не связан 
 (4) тогда и только тогда, когда у нее нет ассоциированного орграфа 
Номер 3
Что называют цепью Маркова (или просто цепью)?
Ответ:
 (1) пару (P,x)
, где P
есть (n×n)
- матрица перехода, а x
есть (1×n)
- вектор-строка 
 (2) пару (P,x)
, где P
есть (n×n)
- матрица возврата, а x
есть (1×n)
- вектор-строка 
 (3) пару (P,x)
, где P
есть прямоугольная - матрица возврата, а x
есть (1×n)
- вектор-строка 
 (4) пару (P,x)
, где P
есть прямоугольная - матрица перехода, а x
есть (1×n)
- вектор-строка 
Упражнение 3:
Номер 1
Что называется дискретной стационарной цепью Маркова?
Ответ:
 (1) если каждый элемент pij
из P
рассматривать как вероятность перехода из позиции Ei
в позицию Ej
, а x
- как начальный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова 
 (2) если каждый элемент pij
из P
рассматривать как вероятность перехода из позиции Ei
в позицию Ej
, а x
- как конечный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова 
 (3) если каждый элемент pij
из P
рассматривать как вероятность перехода из позиции Ei
в позицию Ej
, а x
- как нулевой вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова 
 (4) если каждый элемент pij
из P
рассматривать как вероятность перехода из позиции Ei
в позицию Ej
, а x
- как вектор с отрицательными компонентами, то придем к классическому понятию дискретной стационарной цепи Маркова 
Номер 2
Что называется источником в орграфе?
Ответ:
 (1) вершина, степень выхода которой положительна, а степень входа равна 0 
 (2) вершина, степень входа которой положительна, а степень выхода равна 0 
 (3) вершина, степень входа которой положительна, а степень выхода отрицательна 
 (4) вершина, у которой и степень входа и степень выхода равны 0 
Номер 3
Что называется стоком в орграфе?
Ответ:
 (1) вершина, степень входа которой положительна, а степень выхода равна 0 
 (2) эргодическое состояние цепи Маркова 
 (3) эргодическая цепь Маркова 
 (4) вершина, у которой и степень входа и степень выхода равны 0