Соотношение глубины первого обхода между узлами G и DFT

Question

Пусть G неориентированный граф. Рассмотрим обход в глубину G, и пусть T будет результирующим деревом поиска в глубину. Пусть u будет вершиной в G, и пусть v будет первой новой (не посещенной) вершиной, посещенной после посещения u в обходе. Какое из следующих утверждений всегда верно?

(A) {u,v} должно быть ребром в G, а u является потомком v в T

(B) {u,v} должно быть ребром в G, а v является потомком u в T

(C) Если {u,v} не является ребром в G, то u является листом в T

(D) Если {u,v} не является ребром в G, то u и v должны иметь одного и того же родителя в T.

================================================== =======================

Правильный ответ (С)

Но я застрял в (B), я не получаю контрпример для (B)

Answer 1

Рассмотрим следующий граф (который на самом деле является деревом).

G := (V, E) where
V := {a, u, v} and E := {{a,u}, {a,v}}.

Глубинный обход в G можно посетить первым a, затем u и наконец v, В точке, где u посещается, v это следующий не посещаемый узел. Тем не мение, {u, v} не край Eотсюда заявление (B) ложно