Ответы на тесты по дисциплине Дискретная математика 83

Максимальные полные и максимальные пустые подграфы. Обыкновенные графы. Вопрос: » Максимальный пустой подграф графа G=(X,U). Дать определение. Варианты ответа: 1. Это часть графа. 2. Это наибольший подграф данного графа G=(X,U). 3. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$=U. 4. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 5. Это ориентированный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 6. Это связный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 7. Это несвязный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 8. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 9. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U, и G’=(X’,U’) включает наибольшее число вершин. 10. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U, и G’=(X’,U’) не является подграфом никакого другого большего максимального пустого подграфа графа G=(X,U). В ответ введите номер верного варианта ответа. » Ответ (10)   Вопрос: » Образуют ли подмножества вершин #math {(#l(x,1)%#l(x,3))%(#l(x,4)%#l(x,3))%(#l(x,1)%#l(x,4))%(#l(x,2)%#l(x,3))} графа G(X,U), где #math U={(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,4)$#l(x,3)))%(!(#l(x,2)$#l(x,3)))%(!(#l(x,3)$#l(x,2)))%(!(#l(x,1)$#l(x,3)))%(!(#l(x,1)$#l(x,4)))%(!(#l(x,4)$#l(x,2)))}, семейство максимальных пустых подграфов? » Да, так как каждый подграф, входящий в указанное семейство подграфов, не является подграфом другого подграфа. Нет, так как подграфы данного семейства подграфов содержат только две вершины. Нет, так как подграфы данного семейства подграфов являются полными.(Верно) Нет, так как подграфы данного семейства содержат общие вершины. Да, так как граф G=(X,U) является обыкновенным графом. Нет, так как вершины в указанных подмножествах являются смежными.(Верно)   Вопрос: » Клика графа. Дать определение. Варианты ответа: 1. Это часть графа. 2. Это наибольший подграф данного графа G=(X,U). 3. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X. 4. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 5. Это ориентированный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 6. Это связный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 7. Это несвязный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 8. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 9. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U, и G’=(X’,U’) включает наибольшее число вершин. 10. Это полный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. В ответ введите номер верного варианта ответа. » Ответ (10)   Вопрос: » Определить, образуют ли подмножества вершин #math {(#l(x,1)$#l(x,2))%(#l(x,1)$#l(x,2)$#l(x,3))%(#l(x,1)$#l(x,3)$#l(x,4))%(#l(x,4)$#l(x,3))%(#l(x,2)$#l(x,3)$#l(x,4))} графа G(X,U), где #math U={(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,3)$#l(x,3)))%(!(#l(x,2)$#l(x,2)))%(!(#l(x,1)$#l(x,3)))%(!(#l(x,1)$#l(x,4)))%(!(#l(x,4)$#l(x,2)))}, семейство максимальных полных подграфов? Варианты ответа: 1. Нет, так как подмножество #math (#l(x,1)$#l(x,2)) входит в #math (#l(x,1)$#l(x,2)$#l(x,3)), а подмножество #math (#l(x,4)$#l(x,3)) входит #math (#l(x,1)$#l(x,3)$#l(x,4)) и #math (#l(x,2)$#l(x,3)$#l(x,4)). 2. Да, так как все подмножества вершин семейства #math {(#l(x,1)$#l(x,2))%(#l(x,1)$#l(x,2)$#l(x,3))%(#l(x,1)$#l(x,3)$#l(x,4))%(#l(x,4)$#l(x,3))%(#l(x,2)$#l(x,3)$#l(x,4))} образуют связные подграфы графа G(X,U). 3. Да, так как все подмножества вершин семейства #math {(#l(x,1)$#l(x,2))%(#l(x,1)$#l(x,2)$#l(x,3))%(#l(x,1)$#l(x,3)$#l(x,4))%(#l(x,4)$#l(x,3))%(#l(x,2)$#l(x,3)$#l(x,4))} oбразуют полные подграфы графа G(X,U). 4. Нет, так как для данного графа максимальными полными подграфами являются подграфы, образованные вершинами #math (#l(x,1)$#l(x,3)$#l(x,4) и #math (#l(x,1)$#l(x,2)$#l(x,4). 5. Нет, так как все подмножества вершин семейства #math {(#l(x,2)$#l(x,1))%(#l(x,1)$#l(x,2)$#l(x,3))%(#l(x,1)$#l(x,3)$#l(x,4))%(#l(x,4)$#l(x,3))%(#l(x,2)$#l(x,3)$#l(x,4))} образуют несвязные между собой подграфы графа G(X,U). В ответ введите номера верных вариантов ответа в порядке возрастания через точку с запятой. » Ответ (1;4)   Вопрос: » Максимальный полный подграф данного графа. Дать определение. Варианты ответа: 1. Это часть графа. 2. Это наибольший подграф данного графа G=(X,U). 3. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$=$U. 4. Это подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 5. Это ориентированный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 6. Это связный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 7. Это несвязный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 8. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U. 9. Это пустой подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$prob$и$prob$U$shtr$@ mle$U, и G’=(X’,U’) включает наибольшее число вершин. 10. Это полный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$%$U$shtr$@ mle$U и G’=(X’,U’) не является подграфом никакого другого большего макcимального пустого подграфа данного графа. 11. Это полный подграф G’=(X’,U’) графа G=(X,U), такой, что #math X$shtr@ mle$X$%$U$shtr$@ mle$U и G’=(X’,U’) не является подграфом никакого другого большего максимального полного подграфа данного графа. В ответ введите номер верного варианта ответа. » Ответ (11)