# Convert a Strongly Connected Directed Graph to
## 5 The Weak Model of Communication Graphs  
We define the weak model of communication graphs. Let us assume that \(\mathcal{D}=(\{a,b,c\},\{(a,b),(a,c)\})\), as in the previous section. The weak model of \(\mathcal{D}\) contains the clause \((a\implies b)\vee(a\implies c)\), which means that if a node can send a message to more than one nodes, then it can send the message only to one of them. Note that \((a\implies b)\vee(a\implies c)\) is equivalent to \((-a\lor b\lor c)\). The only problem with this representation is that the message can be trapped if a graph contains a cycle. Let us assume that we have a cycle with two nodes, \(n_{1}\) and \(n_{2}\). Then \(n_{1}\) may send the message to \(n_{2}\), and \(n_{2}\) to \(n_{1}\), and so on, which means that other nodes could never get the message. This is not good, since our goal is to send a message to each node, if it is possible. Let us add a new edge to the graph \((\{a,b,c\},\{(a,b),(a,c)\})\). The new edge should go from \(b\) to \(a\). Now we have a cycle with the nodes \(a\) and \(b\). Now we have to add a clause to our model which ensures that if \(b\) sends a message to \(a\), and \(a\) can send a message to \(b\) or \(c\), then \(a\) should not send back the message to \(b\), but it has to send it to \(c\): \(((b\implies a)\wedge(a\implies(b\lor c))\implies(a\implies c).\) Note that this is equivalent to the clause: \((-a\vee\
eg b\lor c)\). In a more general way, node \(a\) which has outgoing edges to nodes \(b_{1},b_{2},\ldots,b_{k}\) is represented by the clause: \((-a\lor b_{1}\lor b_{2}\vee\cdots\lor b_{k})\) ; and the cycle \(a_{1},a_{2}\ldots a_{n},a_{1}\) with exit points \(b_{1},b_{2},\ldots,b_{m}\) is  
Figure 3: A strongly connected communication graph with 4 vertices, 6 cycles. represented by the clause: \((\
eg a_{1}\vee\
eg a_{2}\vee\dots\vee\
eg a_{n}\lor b_{1}\lor b_{2}\vee\dots \lor b_{m})\). We call this model as the weak model of communication graphs. We also define it formally: Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{V}\) be the set of vertices of \(\mathcal{D}\) and \(\mathcal{E}\) the set of edges of \(\mathcal{D}\). Since \(\mathcal{D}\) is a communication graph, we know that elements of \(\mathcal{V}\) can be used as positive literals. Then we define the following notion:  
\[OutE(a):=\{b\mid(a,b)\in\mathcal{E}\}.\]  
\[NodeRep(a):=\{\
eg a\}\cup OutE(a).\]  
\[NodeRep:=\{NodeRep(a)\mid a\in\mathcal{V}\wedge OutE(a)\
eq\emptyset\}.\]  
\[Cycles:=\{(a_{1},a_{2},\dots,a_{k})\mid k=1\vee\forall_{i=1\dots k}(a_{(i\;mod \;k)+1}\in OutE(a_{i})\},\]  
and for any two elements of \(Cycles\) they cannot be equal as a set. \[ExitPonts(\;(a_{1},a_{2},\dots a_{k})\;):=\{b\mid\exists_{i=1\dots k}(b\in Out E (a_{i}))\wedge\
eg\exists_{j=1\dots k}(b=a_{j})\}.\]  
\[CycleRep:=\{\
eg C\cup ExitPonts(C)\mid C\in Cycles\wedge ExitPonts(C)\
eq \emptyset\}.\]  
\[\mathcal{WM}:=NodeRep\cup CycleRep.\]  
\(\mathcal{WM}\) is the weak model of \(\mathcal{D}\). Note that \(NodeRep\) is a subset of \(CycleRep\), because we take each node itself as a cycle; see the constraint \(k=1\vee\dots\) in the definition of \(CycleRep\). Thus, alternatively we can define \(\mathcal{WM}\) as follows: \(\mathcal{WM}:=CycleRep\). We do not use this observation in this work, although some proofs would be shorter. Please note that each clause in \(\mathcal{WM}\) contains at least one positive and one negative literal, because a node is only represented if it has an outgoing edge, and a cycle is only represented if it has an exit point; therefore, \(\mathcal{SM}\) is satisfiable for any communication graph \(\mathcal{D}\). Figure 4 shows two simple communication graphs. Their \(NodeRep\) values are: \(\{\{\
eg a,b,c\}\}\), and \(\{\{\
eg a,b,c,d\}\}\), respectively. Figure 2 shows a communication graph with three cycles:  
\[(a,b),(a,b,c),(a,c).\]  
Thus, its weak model is (after each clause we list the indices of subsumed full-length clauses from (3)):  
\[