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

ignougroup
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