игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 16

Комбинаторные алгоритмы для программистов - тест 16

Упражнение 1:
Номер 1 
Что называется меткой в графе G?

Ответ:

 (1) это однозначное соответствие между множеством вершин графа G и множеством чисел либо букв определенного алфавита и определенного регистра 

 (2) это однозначное соответствие между множеством вершин графа G и множеством чисел {1,...,n}. Числа 1,...,n называют метками графа G 

 (3) это однозначное соответствие между множеством вершин графа G и множеством чисел {1,...,n}. Числа 1,...,n называют метками графа G и обозначают вершины графа G через v1,...,vn 

 (4) это однозначное соответствие между множеством вершин графа G и множеством букв любого алфавита, написанных либо в верхнем, либо в нижнем регистре. Для обозначения меток одного графа используется один определенный алфавит 

Номер 2 
При каких условиях метод поиска в глубину в графе "хорош"?

Ответ:

 (1) когда граф имеет две вершины 

 (2) когда граф является ориентированным и имеет не более двух вершин 

 (3) если метод поиска позволяет алгоритму решения интересующей нас задачи легко погрузиться в этот поиск 

 (4) когда каждое ребро графа анализируется не более одного раза или, что существенно не меняет ситуации, числа раз, ограниченного константой 

Номер 3 
Что называется деревом G(V,E)?

Ответ:

 (1) пусть G(V,E) - произвольный неориентированный связный граф без циклов. Деревом называется произвольный неориентированный связный граф без циклов; дерево обозначается так: <V,T>, где Т⊆E 

 (2) пусть G(V,E) - произвольный неориентированный связный граф с циклами. Деревом называется произвольный неориентированный связный граф с циклами; обозначается так: <V,T>, где Т⊆E 

 (3) циклы в G(V,E) в произвольном ориентированном связном графе называются деревом. Дерево обозначается так: <V,T>, где Т⊆E 

 (4) пусть G(V,E) - произвольный неориентированный связный граф без циклов. Максимальный путь в G(V,E) называется деревом и обозначается так: <V,T>, где Т⊆E 

Упражнение 2:
Номер 1 
Чем отличается стягивающие дерево от каркаса и остова дерева?

Ответ:

 (1) стягивающие дерево, каркас и остова дерева - это одно и то же 

 (2) стягивающие дерево, каркас - это одно и то же, а остов дерева - это максимальный путь в графе 

 (3) стягивающие дерево, каркас и остова дерева - это одно и то же только в орграфе 

 (4) стягивающие дерево, каркас и остова дерева - это одно и то же только в циклическом графе 

Номер 2 
Что называется потомком определенной вершины в дереве <V,T>, где Т⊆E?

Ответ:

 (1) для двух различных вершин v и u дерева <V,T>, где Т⊆E, будем говорить, что u является потомком вершины v, если v лежит на пути (в дереве <V,T> ) из u в корень 

 (2) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v является отцом данной вершины 

 (3) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v является сыном данной вершины 

 (4) для двух различных вершин v и u дерева <V,T>, где Т⊆E будем говорить, что u является потомком вершины v, если v лежит на пути в дереве <V,T> в корень 

Номер 3 
Что называют мостом графа G(V,E)?

Ответ:

 (1) каждое ребро, присоединение которого приводит к увеличению числа связных компонент графа 

 (2) каждое ребро, удаление которого приводит к увеличению числа связных компонент графа 

 (3) каждое ребро, замена которого на петлю приводит к увеличению числа связных компонент графа 

 (4) каждое ребро, введение ориентации которого приводит к увеличению числа связных компонент графа 

Упражнение 3:
Номер 1 
Какие условия являются необходимыми для использования алгоритма Дейкстры?

Ответ:

 (1) все веса дуг неотрицательны, или граф бесконтурный 

 (2) все веса дуг отрицательны, или граф бесконтурный 

 (3) некоторые веса дуг неотрицательны, или граф бесконтурный 

 (4) только когда граф бесконтурный 

Номер 2 
Если последовательность вершин v0,v1,...,vp  определяет путь в G(V,E)  графе, то как определяется его длина?

Ответ:

 (1) files где α - вес ребра 

 (2) files где α - вес ребра 

 (3) files где α - вес ребра 

 (4) files где α - вес ребра 

Номер 3 
Что называют точкой сочленения в графе?

Ответ:

 (1) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины и всех инцидентных ей ребер ведет к увеличению числа компонент связности графа 

 (2) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины ведет к увеличению числа компонент связности графа 

 (3) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины и всех инцидентных ей ребер не ведет к увеличению числа компонент связности графа 

 (4) вершину α неориентированного графа будем называть точкой сочленения, если удаление этой вершины не ведет к увеличению числа компонент связности графа 



Главная / Алгоритмы и дискретные структуры / Комбинаторные алгоритмы для программистов / Тест 16