Эксперт по сдаче вступительных испытаний в ВУЗах
Вопрос:» Определить, является ли граф G(X,U) транспортной сетью, если
#math U={#math#i((#l(x,1)$#l(x,2)),null,@arr$)%#i((#l(x,3)$#l(x,1)),null,@arr$)%#i((#l(x,1)$#l(x,4)),null,@arr$)%#i((#l(x,2)$#l(x,5)),null,@arr$)%#math#i((#l(x,5)$#l(x,3)),null,@arr$)%#i((#l(x,4)$#l(x,6)),null,@arr$)%#math#i((#l(x,6)$#l(x,7)),null,@arr$)%#i((#l(x,3)$#l(x,7)),null,@arr$)%#i((#l(x,5)$#l(x,7)),null,@arr$)%#i((#l(x,6)$#l(x,5)),null,@arr$)}.
Варианты ответа:
1. ДА, так как есть #math #l(x,i)@ pri$X такая, что #risg.jpgris.
2. ДА, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul.
3. НЕТ, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul и нет #math #l(x,i)@ pri$X такой, что #risg.jpgris.
4. ДА, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul и #math #l(x,i)@ pri$X такая, что #risg.jpgris.
В ответ введите номер верного варианта ответа. »
Ответ (3)
Вопрос: » Определить, является ли граф G(X,U) транспортной сетью, если
#math U={#i((#l(x,1)$#l(x,2)),null,@arr$)%#i((#l(x,3)$#l(x,1)),null,@arr$)%#i((#l(x,1)$#l(x,4)),null,@arr$)%#i((#l(x,2)$#l(x,5)),null,@arr$)%#i((#l(x,5)$#l(x,3)),null,@arr$)%#i((#l(x,4)$#l(x,6)),null,@arr$)%#i((#l(x,6)$#l(x,7)),null,@arr$)%#i((#l(x,3)$#l(x,7)),null,@arr$)%#i((#l(x,5)$#l(x,7)),null,@arr$)%#i((#l(x,6)$#l(x,6)),null,@arr$)%#i((#l(x,6)$#l(x,5)),null,@arr$)};
Варианты ответа:
1. ДА, так как есть #math #l(x,i)@ pri$X такая, что #risg.jpgris.
2. ДА, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul.
3. НЕТ, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul и нет #math #l(x,i)@ pri$X такой, что #risg.jpgris.
4. ДА, так как есть #math #l(x,k)@ pri$X такая, что #math Г$#l(x,k)=@nul и #math #l(x,i)@ pri$X такая, что #risg.jpgris.
5. Данный граф содержит дугу — петлю.
В ответ введите номера верных вариантов ответа через точку с запятой в порядке возрастания. »
Ответ (3;5)
Вопрос: »
Обозначим интерпретирующий транспортную сеть граф — #math G=(X%#i(U,null,@arr$)), а поток на ней #math teta$(u), исток — #math #l(х,0), сток — z, c(u) пропускная способность.
Поток #math teta$(u) на транспортной сети это целочисленная функция, заданная на множестве дуг графа #math G=(X%#i(U,null,@arr$)) и удовлетворяющая свойствам.
Определите какие это свойства.
Варианты ответа:
1. сумма потоков на дугах входящих в вершину #math х$(х@ne$#l(x,0)$prob$и$prob$х@ne$z) равна сумме потоков на дугах выходящих из вершины x.
2. сумма потоков на дугах исходящих из вершины #math х=#l(x,0) равна сумме потоков на дугах входящих в вершину x=z.
3. #math teta$(u)$<$=$c$(u).
4. #math teta$(u)$>$=$0.
5. #math teta$(u)$>$=$c$(u).
6. #math teta$(u)$<$=$0.
В ответ введите номера верных вариантов ответа через точку с запятой в порядке возрастания. »
Ответ (1;3;4)
Вопрос:» Определить является ли поток на сети T максимальным, если интерпретирующий его граф G=(X,U) содержит дуги
#math U={#2(#i((#l(x,1)$#l(x,2)),null,@arr$),22,18)%#2(#i((#l(x,2)$#l(x,3)),null,@arr$),9,6)%#2(#i((#l(x,1)$#l(x,3)),null,@arr$),9,2)%#2(#i((#l(x,2)$#l(x,4)),null,@arr$),7,7)%#2(#i((#l(x,2)$#l(x,5)),null,@arr$),6,5)%#2(#i((#l(x,3)$#l(x,5)),null,@arr$),8,8)%#2(#i((#l(x,5)$#l(x,4)),null,@arr$),4,4)%#2(#i((#l(x,5)$#l(x,6)),null,@arr$),9,9)%#2(#i((#l(x,4)$#l(x,6)),null,@arr$),12,11)}
(здесь за скобками нижний индекс соответствует пропускной способности, верхний — величине потока на дуге #math #2(#i((#l(x,i)%#l(x,j)),null,@arr$),m,n))?
При решении использовать процедуры алгоритма Форда-Фалкерсона.
Поток на сети Т <вписать>, так как при разметке вершин вершину #math #l(x,6) пометить <вписать>.
В ответ впишите пропущенные слова через запятую. »
Ответ key , = + end ({М+м}+аксимальный+{,+.}+{Н+н}+ельзя+)
Вопрос:»
Найти минимальный разрез T на сети #math G=(X%#i(U,null,@arr$)), где
#math #i(U,null,@arr$)={#2(#i((#l(x,1)$#l(x,2)),null,@arr$),22,18)%#2(#i((#l(x,2)$#l(x,3)),null,@arr$),9,6)%#2(#i((#l(x,1)$#l(x,3)),null,@arr$),9,2)%#2(#i((#l(x,2)$#l(x,4)),null,@arr$),7,7)%#2(#i((#l(x,2)$#l(x,5)),null,@arr$),6,5)%#2(#i((#l(x,3)$#l(x,5)),null,@arr$),8,8)%#2(#i((#l(x,5)$#l(x,4)),null,@arr$),4,4)%#2(#i((#l(x,5)$#l(x,6)),null,@arr$),9,9)%#2(#i((#l(x,4)$#l(x,6)),null,@arr$),12,11)}
(здесь за скобками нижний индекс соответствует пропускной способности, верхний — величине потока на дуге #math #i((#l(x,i)%#l(x,j)),null,@arr$)).
Варианты ответа:
1. #math T={#i((#l(x,1)$#l(x,4)),null,@arr$)%#i((#l(x,3)$#l(x,4)),null,@arr$)%#i((#l(x,3)$#l(x,6)),null,@arr$)}
2. #math T={#i((#l(x,2)$#l(x,4)),null,@arr$)%#i((#l(x,5)$#l(x,4)),null,@arr$)%#i((#l(x,5)$#l(x,6)),null,@arr$)}
3. #math T={#i((#l(x,2)$#l(x,3)),null,@arr$)%#i((#l(x,5)$#l(x,3)),null,@arr$)%#i((#l(x,5)$#l(x,6)),null,@arr$)}
В ответ введите номер верного варианта ответа. »
Ответ (2)
