# Convert a Strongly Connected Directed Graph to
## 6 The Balatonboglar Model of Communication Graphs  
Since the weak model does not result in a 3-SAT problem, we introduce also the Balatonboglar model, which is a simplified version of the weak model, which uses the trick that instead of detecting each cycle in the graph, it generates from each path \(a,b,c\) the following 3-clause: \((\
eg a\vee\
eg b\lor c)\) even if there is no cycle which contains the vertices \(a\) and \(b\). This simplification allows very fast 3-SAT model generation from a directed graph, and the model will be black and white 3-SAT if and only if the input directed graph is strongly connected. Figure 5: A strongly connected communication graph with 4 vertices, 3 simple cycles, 1 non-simple cycle. We define the Balatonboglar model of communication graphs as follows. 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:  
\[NodeRep2:=\{\{\
eg a,b\}\mid a\in\mathcal{V}\wedge\{b\}=OutE(a)\}.\]  
\[NodeRep3(a):=\{\
eg a,b,c\},where\ a\in\mathcal{V}\wedge b\in OutE(a)\wedge c \in OutE(a)\wedge b\
eq c.\]  
\[NodeRep3:=\{\ NodeRep3(a)|\ a\in\mathcal{V}\}.\]  
\[TagForward:=\{\{\
eg a,\
eg b,c\}\mid a\in\mathcal{V}\wedge b\in OutE(a) \wedge c\in OutE(b)\wedge a\
eq b\
eq c\}.\]  
\[\mathcal{BM}:=NodeRep2\cup NodeRep3\cup TagForward.\]  
\(\mathcal{BM}\) is a Balatonboglar model of \(\mathcal{D}\). Note that \(NodeRep3(a)\) is not a deterministic function, it is just any 3 length subset of \(NodeRep(a)\). The name \(TagForward\) comes from the children's game tag: There is one child who has to catch someone else by touching he or she. This action is called tagging. There is a rule: the tagged one cannot tag back; he or she must tag someone else, so must tag forward. As a first example, we give the Balatonboglar model of the graph from Figure 2 (after each clause we list the indices of subsumed full-length clauses from (3)):  
\[ \begin{split}\mathcal{BM}&=\{\{\
eg a,b,c\}:6,7,\ \{ \
eg b,c,d\}:3,11,\ \{\
eg c,a,d\}:9,13,\\ &\{\
eg a,\
eg b,c\}:2,3,\ \{\
eg a,\
eg b,d\}:13,\ \{\
eg a, \
eg c,b\}:45,\\ &\{\
eg a,\
eg c,d\}:1,5,\ \{\
eg b,\
eg c,a\}:8,9,\ \{\
eg b, \
eg c,d\}:1,9\}.\end{split}  \tag{8}\]  
Note that \(b\) has three child nodes, so instead of \(\{\
eg b,c,d\}\), we could use either \(\{\
eg b,a,c\}\) or \(\{\
eg b,a,d\}\). Note also that Figure 2 is not strongly connected, so its Balatonboglar model is not a black and white SAT problem. For example, \(\{\
eg a,\
eg b,\
eg c,d\}\) is a solution of the SAT problem in (8). As a second example, we show the Balatonboglar model of the communication graph from Figure 3. Note that in this graph we have an edge from \(d\) to \(a\). The corresponding clauses are the last three clauses in this Balatonboglar model: (after each clause we list the indices of subsumed full-length clauses from (3)):  
\[ \begin{split}\mathcal{BM}&=\{\{\
eg a,b,c\}:6,7,\ \{ \
eg b,c,d\}:3,11,\ \{\
eg c,a,d\}:9,13,\\ \{\
eg d,a\}:8,10,12,14,\ \{\
eg a,\
eg b,c\}:2,3,\ \{\
eg a, \
eg b,d\}:13,\ \{\
eg a,\
eg c,d\}:15,\\ \{\
eg b,\
eg c,a\}:8,9,\ \{\
eg b,\
eg c,d\}:19,\ \{\
eg b, \
eg d,a\}:8,10,\\ \{\
eg c,\
eg a,b\}:45,\ \{\
eg c,\
eg d,a\}:8,12,\ \{\
eg d, \
eg a,b\}:46,\ \{\
eg d,\
eg a,c\}:3,7\}.\end{split}  \tag{9}\]  
Note that since the communication graph from Figure 3 is strongly connected, its Balatonboglar model is a black and white SAT problem; i.e., the SAT problem in (9) has only these two solutions: \(\{a,b,c,d\}\), and \(\{\
eg a,\
eg b,\
eg c,\
eg d\}\). As a third example, we show the Balatonboglar model of the communication graph from Figure 5 (after each clause we list the indices of subsumed full-length clauses from (3)):  
\[