Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 5

Графы и алгоритмы - тест 5

Упражнение 1:

Номер 1

Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Ответ:

(1)

(2)

(3)

(4)

Номер 2

Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Ответ:

(1)

(2)

(3)

(4)

Номер 3

Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

Ответ:

(1)

(2)

(3)

(4)

Упражнение 2:

Номер 1

Поиск в глубину применяется к графу . Какова будет высота DFS-дерева?

Ответ:

(1) 2

(2) 4

(3) 2 или 4

(4) 2, 3 или 4

Номер 2

Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

Ответ:

(1) всегда math

(2) h может быть меньше, чем радиус графа

(3) h может быть больше, чем диаметр графа.

(4) h не может быть меньше, чем эксцентриситет стартовой вершины.

Номер 3

Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

Ответ:

(1)

(2)

(3)

(4)

Упражнение 3:

Номер 1

Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

Ответ:

(1)

(2)

(3)

(4)

Номер 2

Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?

Ответ:

(1) если вершина x не является листом DFS-дерева, то у нее имеется такой сын y, что math

(2) если math

то вершина x - предок вершины y в DFS-дереве

(3) если вершина x - предок вершины в DFS-дереве, то math

(4) если math

и вершины x,y смежны в графе, то вершина x - предок вершины y в DFS-дереве

Номер 3

Какие из следующих утверждений верны?

Ответ:

(1) лист DFS-дерева не может быть шарниром графа.

(2) если (x,y)- обратное ребро, то ни одна отличная от x и y вершина пути, соединяющего x и y в DFS-дереве, не является шарниром

(3) если вершина x является сыном вершины y в DFS-дереве и обе эти вершины - шарниры графа, то ребро (x,y) - перешеек

(4) если (x,y) - обратное ребро, то ни одно ребро пути, соединяющего x и y в DFS-дереве, не является перешейком

Номер 4

Какие из следующих утверждений верны?

Ответ:

(1) если вершина x - предок вершины y в DFS-дереве, то math

(2) если вершина x - предок вершины y в DFS-дереве, то math

(3) если в графе имеется ребро (x,y), то math

(4) если вершина x - предок вершины y в DFS-дереве и в графе имеется ребро (x,y),то math

Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 5