[cmps201] Fwd: DFS Properties (question 8D)
Brad Eric Hollister
I just posted this on Piazza...
From: "CMPS 201 on Piazza" <no-r...@piazza.com>
To: beho...@soe.ucsc.edu
Sent: Saturday, November 5, 2011 11:09:33 PM
Subject: DFS Properties (question 8D)
Your classmate posted a new Question.
DFS Properties (question 8D)
#practiceexam2
Statement: At the time v is just arrived at in DFS of an UNDIRECTED graph and has not been colored grey yet, if there is an edge v->w and w is black, then the graph is not connected.
breaking this down:
(v is white) AND (DFS of an UNDIRECTED graph) AND (there is an edge v->w) AND (w is black) --> (the graph is NOT connected).
This statement is impossible, since if there is an undirected edge v (white)<-->w (black) and w is black, then v would already have to be black itself in a DFS tree (according to the white path theorem, which is just a result of the definition of the DFS algorithm). An undirected edge is really a "two-way" edge.
So, assuming the first and second antecedent clauses (v is white) and (DFS on an undirected graph) are true, the second and third antecedents clauses can't BOTH be true, regardless of the conclusion in the statement. This is enough to invalidate the statement as a whole (i.e., a counterexample).
Is the answer consensus?
Click here to view. Search or link to this question with @13. Follow it to get notified when a response comes in.
Visit http://piazza.com/ucsc if you'd like to use Piazza for your other classes.
Thanks,
The Piazza Team
--
Contact us at te...@piazza.com
Allen Van Gelder
> DFS Properties (question 8D)
> ...
Please put this on the review agenda Monday.
I have not figured out how to post on piazza, but it is mainly for
students to talk to each other.
> the second and third antecedents clauses can't BOTH be true
> ... This is enough to invalidate the statement
What rule(s) of logic are you using to back this assertion up?
A truth table is the final way to determine if a propositional
statement is always true, never true, or somewhere in between.
--Allen
Brad Eric Hollister
(A := v is white) AND (B := DFS of an UNDIRECTED graph) AND (C := there is an edge v->w) AND (D := w is black) --> ( E := the graph is NOT connected).
The problems instance sets A = true, B = true, C = false, D = true and E = true. C is false since an UNDIRECTED graph doesn't have polarity to an edge and C specifies direction. This set of truth values corresponds to line 5 in the truth table. So, the statement must be true.
$$
\begin{tabular}{| c | c | c | c | c || c | }
\hline
A & B & C & D & E & if (A and B and C and D) then E \\
\hline
T & T & T & T & T & T \\
T & T & T & T & F & F \\
T & T & T & F & T & T \\
T & T & T & F & F & T \\
T & T & F & T & T & T \\
T & T & F & T & F & T \\
T & T & F & F & T & T \\
T & T & F & F & F & T \\
T & F & T & T & T & T \\
T & F & T & T & F & T \\
T & F & T & F & T & T \\
T & F & T & F & F & T \\
T & F & F & T & T & T \\
T & F & F & T & F & T \\
T & F & F & F & T & T \\
T & F & F & F & F & T \\
F & T & T & T & T & T \\
F & F & T & T & T & T \\
F & F & T & T & F & T \\
F & F & T & F & T & T \\
F & F & T & F & F & T \\
F & F & F & T & T & T \\
F & F & F & T & F & T \\
F & F & F & F & T & T \\
F & F & F & F & F & T \\
\hline
\end{tabular}
$$
Or, if you interpret all antecedents to be true (where v->w exists as one aspect of an undirected edge), and w has already been visited (i.e. black) this contradicts the white path theorem that states that if there is a path between a white vertex (say v) and another vertex (say w) in the same connected component, then there must be a path of white vertices to w, where w is white itself (since by definition if there is an edge v->w, v and w are in the same connected component). Therefore, the conclusion must be false (that the graph is not connected). This corresponds to line 2 in the truth table, which corresponds to a false statement.
Are the above answer(s) now correct?
--Allen
_______________________________________________
Allen Van Gelder
I still say, Please put this on the review agenda Monday if you have further
questions.
If you think your text beginning "Or, if you interpret all antecedents to be
true..." is a sound proof, put it in the 2-column format with
numbered lines and justifications.
This allows you to inspect each little piece separately.
The intention of "v->w" is that there is an edge between v and w.
If you see what looks like a notation error or syntax error on the exam,
ASK. All questions are supposed to make sense, at least grammatically.
Your truth table is missing some cases because it has less than 32
lines. The main question is, are there any other cases besides
line 2 that make the statement false?
You don't need to list all of the other 31 if they are all true -- just
say it.
Recall that in your first message you said something like
"since D is false, the whole statement is false".
My purpose in referring to a truth table was this statement.
See you all Monday.
--Allen