Partitions of a directed graph - common prey and common enemy partitions

Problem Detail: 

Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting). For $v \in V$ define the following sets: $$v^+= \left\{w \in V|(v,w)\in E \right\}, v^-= \left\{w \in V|(w,v)\in E \right\}$$

For some $S \subseteq V$ we have, $S^+= \bigcup_{v \in S} v^+, S^-= \bigcup_{v \in S} v^-$.

Now define two related graphs, $G_{cp}=(V,E_{cp}),G_{ce}=(V,E_{ce})$ such that for two distinct nodes $v,w \in V$ we have $vw \in E_{cp}$ iff $v^+ \cap w^+ \neq \emptyset$ (we identify this by condition $C(p)$, and $vw \in E_{ce}$ iff $v^- \cap w^- \neq \emptyset$ (condition $C'(p)$ (The notations cp and ce come from "common prey" and "common enemy" )

Let $B_1,B_2,...,B_p$ be the sets of nodes of the connected components of $G_{cp}$ and $A_1,A_2,...,A_k$ be the set of connected components of $G_{ce}$. Obviously those sets are two partitions of $V$

Prove that $(B^+_1,B^+_2,...,B^+_p)$ and $(A^-_1,A^-_2,...,A^-_k)$ represent partitions of $V$. Also prove that $p=k$ (that is both graphs have the same number of connected components).

To prove the first part I thought about taking some arbitrary $v \in V$ and than proving that $v$ is in $(B^+_1,B^+_2,...,B^+_p)$. Then a proof by contradiction may be required to complete the first part, but I can't quite seem to make the connection. I don't even know how to start proving $p=k$. Could you help, give me some hints that I miss or something?

UPDATE

So, after some research, it seems that $G_{cp}$ is a competition graph.

Asked By : nightwing96

Answered By : Yuval Filmus

Let $p = p_1,\ldots,p_n$ be a sequence of vertices. We say that this is a +path from $p_1$ to $p_n$ if $n$ is even and $(p_1,p_2),(p_3,p_2),(p_3,p_4),(p_5,p_4),\ldots,(p_{n-1},p_{n-2}),(p_{n-1},p_n)$ are all directed edges. In other words, a +path is one that alternates taking the edges in the "correct" and "wrong" ways, starting with a "correct" and ending with a "wrong". A -path is defined analogously with the directions reversed.

Say that two vertices $p,q$ are +equivalent if there is a +-path from $p$ to $q$. I claim that this is an equivalence relation. Indeed:

• The empty +path connects a vertex with itself.
• The reverse of a +path from $p$ to $q$ is a +path from $q$ to $p$.
• The concatenation of a +path from $p$ to $q$ and a +path from $q$ to $r$ is a +path from $p$ to $r$.

The equivalence classes of this relation are $B_1,\ldots,B_p$. If $x \in B_i$ and $y \in B_j$ have a common out-neighbor $z$ then $x,z,y$ is a +path from $x$ to $z$, so $i = j$. This shows that the $B_i^+$ are distinct, and because every vertex has an incoming edge, they form a partition of the vertex set.

We can similarly define -equivalence, whose equivalence classes are $A_1,\ldots,A_k$, and show that the $A_j^-$ partition the vertex set (since every vertex has an outgoing edge).

Take any $x,y \in B_i^+$, say $(z,x),(w,y)$ are edges for $z,w \in B_i$ (possibly $z = w$) and there is a +path $\alpha$ from $z$ to $w$. It's not hard to check that $x,\alpha,y$ is a -path from $x$ to $y$. Conversely, suppose that $x \in B_i^+$ and $y \in B_j^+$, say $(z,x),(w,y)$ are edges for $z \in B_i, w \in B_j$. If there is a -path $\beta$ from $x$ to $y$ then $z,\beta,w$ is a +path from $z$ to $w$, so that $i = j$. We conclude that $\{B_1^+,\ldots,B_p^+\} = \{A_1,\ldots,A_k\}$, so $p = k$. Similarly $\{A_1^-,\ldots,A_k^-\} = \{B_1,\ldots,B_p\}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49073