Соотношение глубины первого обхода между узлами 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.

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

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

Но я застрял в (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) неверно.