3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint (for $A$, everything being symmetric for $B$): by the assumption, for any $v\in V$ there is some $w$ with $(v,w)\in E$ and therefore $v\in w^- \subseteq A^-$, where $A$ is the CC of $w$ in $G_{ce}$. Can you show that $A_i^-$ and $A_j^-$ are disjoint for $i\neq j$? $\endgroup$ – Klaus Draeger Nov 4 '15 at 13:41
  • $\begingroup$ Ideas for part two: (1) It is enough to show that $p \leq k$. (2) Find a third parameter $d$, defined symmetrically, and show that $p = d$. I don't know whether these ideas work here. $\endgroup$ – Yuval Filmus Nov 4 '15 at 18:45
  • $\begingroup$ Man, this are very usefull advices. Thanks. $\endgroup$ – nightwing96 Nov 5 '15 at 21:20
1
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ Such an elegant way to solve this. Thank you. $\endgroup$ – nightwing96 Nov 7 '15 at 10:17

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.