# Convert a Strongly Connected Directed Graph to
## 4 The Strong Model of Communication Graphs  
In our previous model [1], which we call in this paper the strong model of communication graphs, edges are represented by logical implication: Let us assume that the graph \(\mathcal{D}\) is \((\{\)_a,b,c\(\},\{(a,b),(a,c)\})\); i.e., \(\mathcal{D}\) is a graph with three vertices, \(a\), \(b\) and \(c\), and with two edges, from \(a\) to \(b\) and from \(a\) to \(c\). Thus, the strong model of \(\mathcal{D}\) is \((a\implies b)\wedge(a\implies c)\). The interpretation of this formula is the following in the field of wireless sensors networks: If node \(a\) is able to send a message to nodes \(b\) and \(c\), then node \(a\) sends the message to both nodes \(b\) and \(c\). However, this might result in an error, because both nodes have to send an acknowledgment that the message has arrived, but using the same frequency at the same time results in interference. A more natural way of communication is that we use some protocol, which decides where to send the message, either to node \(b\) or to node \(c\); see the next section. The strong model was defined formally in our previous work [1]. We recall its definition. Let \(\mathcal{D}=(\mathcal{V},\mathcal{E})\) be a communication graph; then the strong model of \(\mathcal{D}\) is denoted by \(\mathcal{SM}\), and defined as follows:  
\[\mathcal{SM}:=\{\{\
eg a,\ b\}\mid(a,b)\in\mathcal{E}\}.\]  
Note that \(\mathcal{SM}\) is a 2-SAT problem and has a nice property: each clause in it has exactly one positive and one negative literal; therefore, \(\mathcal{SM}\) is satisfiable for any communication graph \(\mathcal{D}\). Furthermore, \(\mathcal{SM}\) is a black and white SAT problem iff \(\mathcal{D}\) is strongly connected; see Theorem 1 in [1]. Since we use this theorem several times herein, we recall it:  
**Theorem 1** (Theorem 1 from [1]). : _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{SM}\) be the strong model of \(\mathcal{D}\). Then \(\mathcal{SM}\) is a black and white 2-SAT problem if and only if \(\mathcal{D}\) is strongly connected._  
As an example we show the strong model of the communication graph of Figure 2:  
\[ \begin{split}\mathcal{SM}=\{\{\
eg a,b\},\{\
eg a,c\},\{\
eg b, a\},\{\
eg b,c\},\\ \{\
eg b,d\},\{\
eg c,a\},\{\
eg c,d\}\}.\end{split}  \tag{1}\]  
Note that since the communication graph from Figure 2 is not strongly connected, its strong model (1) is not a black and white SAT problem. For example, \(\{\
eg a,\
eg b,\
eg c,d\}\) is a solution of it. As a second example we show the strong model of the communication graph from Figure 3. This graph is almost the same as the previous one (Figure 2), but here we have an edge from \(d\) to \(a\), which makes this graph strongly connected. Its strong model is:  
\[ \begin{split}\mathcal{SM}=\{\{\
eg a,b\},\{\
eg a,c\},\{\
eg b,a\},\{\
eg b,c\},\\ \{\
eg b,d\},\{\
eg c,a\},\{\
eg c,d\},\{\
eg d,a\}\}.\end{split}  \tag{2}\]  
Figure 2: A communication graph with 4 vertices, 3 cycles. Note that since the communication graph from Figure 3 is strongly connected, its strong model is a black and white SAT problem; i.e., the SAT problem in (2) has only these two solutions: \(\{a,b,c,d\}\) and \(\{-a,-b,-c,-d\}\). It is not easy to check that this SAT problem is indeed a black and white SAT problem. Therefore, first we show the set of all full-length clauses on the variables \(\{a,b,c,d\}\) with an index number (index number: full-length clause):  
\[ \begin{split}\{0:\{&\
eg a,-b,-c,-d\},\;1:\{-a,-b,- c,d\},\;2:\{-a,-b,c,-d\},\\ &\;3:\{-a,-b,c,d\},4:\{-a,b,-c,-d\},\;5:\{-a,b,-c,d\},\\ &\;6:\{-a,b,c,-d\},\;7:\{-a,b,c,d\},8:\{a,-b,-c,-d\},\\ &\;9:\{a,-b,-c,d\},\;10:\{a,-b,c,-d\},\;11:\{a,-b,c,d\},\\ &\;12:\{a,b,-c,-d\},\;13:\{a,b,-c,d\},\;14:\{a,b,c,-d\},\\ &\;15:\{a,b,c,d\}\},\end{split}  \tag{3}\]  
As a second step, we give which clause from (2) subsumes which full-length clauses (clause: indices of subsumed full-length clauses):  
\[