Ответы на тесты по дисциплине Теория графов 6



Понятие достижимости и взаимодостижимости

Вопрос:t»Дан неорграф G #ris61.jpgris. Чему равно множество достижимости вершины #math #l(x,1)?
а) #math #l(R,x1)={#l(x,1)%#l(x,4)%#l(x,2)};
б) #math #l(R,x1)={#l(x,1)%#l(x,4)%#l(x,2)%#l(x,3)};
в) #math #l(R,x1)={#l(x,3)%#l(x,2)};
г) #math #l(R,x1)={#l(x,3)%#l(x,4)%#l(x,2)};»
Ответ: (б,{),$})

 

Вопрос:»Найдите множество контрдостижимости вершины #math #l(x,3) графа G: #ris62.jpgris
1. #math #2(R,x3,minus$1)={#l(x,2)%#l(x,3)};
2. #math #2(R,x3,minus$1)={#l(x,1)%#l(x,2)%#l(x,3)%#l(x,4)};
3. #math #2(R,x3,minus$1)={#l(x,1)%#l(x,2)%#l(x,4)};»
Ответ (2)

 

Вопрос: Отношение взаимодостижимости на графе есть
а) отношение эквивалентности;(Верно)
б) отношение частичного порядка;
в) отношение строгого порядка;

 

Вопрос: Матрица достижимости связного неорграфа есть
а) матрица, все элементы которой — единичные;(Верно)
б) матрица, элементы главной диагонали которой равны нулю, остальные элементы — единичные;
в) матрица, равная матрице смежности данного неорграфа;

 

Вопрос:»Элементы матрицы взаимодостижимости #math #l(s,ij) орграфа могут быть получены следующим образом: (#math #l(a,ij) -элементы матрицы смежности, #math #l(r,ij) — элементы матрицы достижимости, #math #l(q,ij) — элементы матрицы контрдостижимости)
1. #math #l(s,ij)=#l(a,ij)&#l(a,ji);
2. #math #l(s,ij)=(#l(r,i1)&#l(q,1j));
3. #math #l(s,ij)=#l(r,ij)&#l(q,ij);»
Ответ (3)