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$
9
  • 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$ May 12, 2017 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$
    – KeyC0de
    May 12, 2017 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$ May 12, 2017 at 16:32
  • $\begingroup$ By the way, I don't think this is a soft question. It's a good question! $\endgroup$ May 12, 2017 at 16:33
  • 1
    $\begingroup$ Maybe I should write an answer then. $\endgroup$ May 12, 2017 at 16:43

3 Answers 3

10
$\begingroup$

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

$\endgroup$
2
  • $\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, 2017 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, 2017 at 15:26
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$."

$\endgroup$
3
  • $\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$
    – KeyC0de
    May 12, 2017 at 16:29
  • $\begingroup$ @RestlessC0bra, thank you for pointing that out. I have removed the redundant condition. $\endgroup$ May 12, 2017 at 16:33
  • 13
    $\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$ May 12, 2017 at 16:58
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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .