Question 1044147: Can anyone tell me if I'm on the right track with this:
Question:
Let G = (V, E) be a directed graph. Let u, v ∈ V be distinct vertices. Define C(u) to be a
strongly connected component of G that contains u, and C(v) a strongly connected component
of G that contains v. Prove that either C(u) and C(v) do not share any vertex or C(u) and
C(v) are equal. [5 marks]
[Hint: To write such a proof you can begin with: “If C(u) and C(v) do not share any vertex
then the result is true, so suppose C(u) and C(v) share a vertex.”]
My answer:
A directed graph is strongly connected if there is a path from a to b, and a path from b to a, whenever a and b are vertices in the graph.
therefore if C(u) and c(V) share a vertex say w,
for the graph to be directed there must be strongly connected components between C(u) and C(w), and strongly connected components between C(v) and C(w)
Therefore as C(u) is strongly connected to C(w) and C(v) is strongly connected to C(w) (we have previously proved this theorem u,v,w E G(V,E) so c(u) is strongly connected to C(v) so therefore as they are both strongly connected to w in order for the definition to hold they must be equal and part of the same graph
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! Your proof is fairly difficult to read. Not clear what "strongly connected component *between* C(u) and C(w)" refers to. It might be easier to draw pictures and think about the problem in terms of paths between vertices.
Suppose C(u) and C(v) share a vertex w. Our goal is to prove that the subgraphs C(u) and C(v) are equal.
To do this, consider some arbitrary vertex in C(u) (could be u, w, or a different vertex). Can you show that this vertex is also in C(v)? hint: use the hypothesis that there are paths from this vertex to w, and to u and v.
|
|
|
