6
$\begingroup$

In one of my algorithm courses, there is this:

A subset $S$ of vertices in a directed graph $G$ is strongly connected if for each pair of distinct vertices ($v_i$, $v_j$) in $S$, $v_i$ is connected to $v_j$ and $v_j$ is connected to $v_i$.

And then the following example graph is given for this proposition:

enter image description here

Maybe i do not understand what that phrase means. What i think it means is this: A node, say $E$ can be a member of an ordered pair $(v_i, v_j)$ only once, ie. if $(E, A)$, then $\lnot (E, [someOtherNode]) $. But we clearly see here, that we have $(E,A)$ and $(E,D)$.

How should i correctly interpret this phrase. What does it mean exactly? Thanks.

$\endgroup$
  • 2
    $\begingroup$ distinct, I believe, refers not the the pairs but the vertices in the pair. So this condition would not require a vertex to be connected to itself. $\endgroup$ – Matthew Leingang May 12 '17 at 16:14
  • $\begingroup$ So there can be $(v_1, v_2)$ and $(v_1, v_3)$ and $(v_4, v_1)$, but not $(v_2, v_1)$ because both $v_2$ and $v_1$ have been used already in a pair? That's what i can make of it. $\endgroup$ – Nikos May 12 '17 at 16:20
  • 4
    $\begingroup$ No. The definition doesn't require that the pairs be distinct. In the phrase “pair of distinct vertices“, notice that the adjective “distinct” modifies “vertices”. Jose has it right. $\endgroup$ – Matthew Leingang May 12 '17 at 16:32
  • $\begingroup$ By the way, I don't think this is a soft question. It's a good question! $\endgroup$ – Matthew Leingang May 12 '17 at 16:33
  • 1
    $\begingroup$ Maybe I should write an answer then. $\endgroup$ – Matthew Leingang May 12 '17 at 16:43
9
$\begingroup$

I think "for each pair of distinct vertices $(v_i, v_j)$ in $S \times S$" means

"for each $(v_i, v_j) \in S \times S$, $v_i \neq v_j$."

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think here $v_i \neq v_j$ and $i \neq j$ are requirements that lead to same sets. In other words $i \neq j$ is redundant. $\endgroup$ – Nikos May 12 '17 at 16:29
  • $\begingroup$ @RestlessC0bra, thank you for pointing that out. I have removed the redundant condition. $\endgroup$ – Arnie Bebita-Dris May 12 '17 at 16:33
  • 12
    $\begingroup$ Actually, the indices $i,j$ themselves are superfluous. I'd prefer to see this written as "For each $(v,w)\in S\times S$ with $v\ne w$, we have ..." $\endgroup$ – Hagen von Eitzen May 12 '17 at 16:58
10
$\begingroup$

Also, "connected" does not mean by a directed edge, but by a directed path.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Good answer but I'd omit the "Also." It seems to me that the meaning of "connected" is the main thing the OP is confused about here. $\endgroup$ – bof May 13 '17 at 4:31
  • $\begingroup$ @bof, the reason I wrote "also", is that I am not answering the question being asked, as it was in its original form. $\endgroup$ – vadim123 May 13 '17 at 15:26
3
$\begingroup$

From your subset $S$ of vertices you can construct a set of pairs $P$, where $(v,w) \in P$ if there is a directed path from $v$ to $w$ (not necessarily confined to $S$). The set is strongly connected if $$ \forall v,w\in S, ( v\neq w \Rightarrow (v,w) \in P \wedge (w,v) \in P) $$ Let $S=G$ in the example graph. Notice that $(A,B)$, $(B,C)$, $(C,D)$, $(D,E)$, $(E,A)$ are all in $P$. So by transitivity, every pair of distinct vertices is in $P$.

The word distinct in the definition rules out the requirement that $(v,v) \in P$. However, it seems that $(v,w) \in P \wedge (w,v) \in P$ would imply that $(v,v)\in P$ anyway.

I'm not sure what you mean by “valid” pair. Any pair may be in $P$; the condition is only that certain pairs must be in $P$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.