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

Правильный ответ:

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

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

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

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

• # Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
• # Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
• # В графе с весовой функцией строится каркас с помощью алгоритма Крускала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
• # Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
• # BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?