# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results
If the communication graph is strongly connected, then both \(\mathcal{SM}\) and \(\mathcal{WM}\) are black and white SAT problems, so they are equivalent. Lemma 6: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{SM}\) be the strong model of \(\mathcal{D}\). Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). If_  
_(I)_ \(\mathcal{D}\) _is strongly connected, or_  
_(II)_ _Each vertex in \(\mathcal{D}\) has only one child,_  
_then \(\mathcal{SM}\) and \(\mathcal{WM}\) are equivalent._  
Proof: In the case of (I) we know that \(\mathcal{D}\) is strongly connected, so by Theorem 1, and by Theorem 2 we know that \(\mathcal{SM}\) and \(\mathcal{WM}\) are black and white SAT problems, so by the definition of clause set equivalent-ness they are equivalent. In case of (II) we have that \(NodeRep=\mathcal{SM}\) and \(NodeRep\subseteq\mathcal{WM}\). From this we obtain that \(\mathcal{WM}\geq\mathcal{SM}\). From Lemma 5 we know that \(\mathcal{SM}\geq\mathcal{WM}\). Hence, \(\mathcal{SM}\) and \(\mathcal{WM}\) are equivalent. The following lemma gives a criterion for the communication graph which makes the strong model stronger than the weak model. This lemma is not needed to prove the following theorems but it is still interesting. Lemma 7: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{SM}\) be the strong model of \(\mathcal{D}\). Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Then \(\mathcal{SM}>\mathcal{WM}\) iff \(\mathcal{D}\) is not strongly connected, and there is at least one vertex in it which has more than one child vertex._  
Proof: (From left to right:) We assume \(\mathcal{SM}>\mathcal{WM}\), so \(\mathcal{SM}\) and \(\mathcal{WM}\) are not equivalent. Since the right side of Lemma 6 is negated, the negation of the left side of Lemma 6 is implied. Hence, \(\mathcal{D}\) is not strongly connected, and there is at least one vertex in it which has more than one child vertex. (From right to left:) Assume \(\mathcal{D}\) is not strongly connected, and there is at least one vertex in it, say \(a\), which has more than one child vertex, say \(b_{1},b_{2},\ldots,b_{k}\), where \(k>1\). In this case \(WW\setminus\{b_{1}\}\cup\{\
eg b_{1}\}\) and \(BB\setminus\
eg a,\
eg b_{k}\cup\{a,b_{k}\}\) are solutions for \(\mathcal{WM}\) but they are not solutions of \(\mathcal{SM}\), since they do not satisfy the clause \(\{-a,b_{1}\}\) from \(\mathcal{SM}\). Thus, \(\mathcal{SM}\) and \(\mathcal{WM}\) are not equivalent. From this and from Lemma 5 we obtain that Then \(\mathcal{SM}>\mathcal{WM}\). The following theorem, the so called transitions theorem states that any \"transition\" between \(\mathcal{SM}\) and \(\mathcal{WM}\) is a black and white SAT problem iff the communication graph is strongly connected. This is one of the main results of this work. **Theorem 3** (Transitions Theorem). : _If for all communication graphs \(\mathcal{D}\) we have \(\mathcal{SM}\geq\mathcal{MM}\geq\mathcal{WM}\), where \(\mathcal{SM}\) is the strong model of \(\mathcal{D}\), \(\mathcal{WM}\) is the weak model of \(\mathcal{D}\) and \(\mathcal{MM}\) is an arbitrary but fixed model of \(\mathcal{D}\), then \(\mathcal{MM}\) is a black and white SAT problem iff \(\mathcal{D}\) is strongly connected._  
Proof. : Assume that \(\mathcal{D}\) is a communication graph. Assume that \(\mathcal{SM}\) is the strong model of \(\mathcal{D}\), \(\mathcal{WM}\) is the weak model of \(\mathcal{D}\) and \(\mathcal{MM}\) is an arbitrary but fixed model of \(\mathcal{D}\). We show that \(\mathcal{MM}\) is a black and white SAT problem iff \(\mathcal{D}\) is strongly connected. (From left to right:) Assume \(\mathcal{MM}\) is a black and white SAT problem. From this and from the assumption that \(\mathcal{SM}\geq\mathcal{MM}\), we have that \(\mathcal{SM}\) is a black and white SAT problem, since any strong model has always at least two solutions, the white assignment and the black one; see [1]. From this and from Theorem 1 we have that \(\mathcal{D}\) is strongly connected.