# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
: _For each \(\alpha\)-acyclic hypergraph \(H\) and each join tree \(T\) of \(H\), \(UJ(H)=tuj(T)\)._

Proof. : Let \(H=(V,\mathcal{E})\) and let \(\{X,Y\}\subseteq\mathcal{E}\). Let us show that \(XY\) is an edge of \(UJ(H)\) if and only if \(XY\) is an edge of \(tuj(T)\). \(\Rightarrow\) : let \(T^{\prime}\) be a join tree of \(H\), such that \(XY\) is an edge of \(T^{\prime}\), and let \(\mathcal{E}_{X}\) (resp. \(\mathcal{E}_{Y}\)) be the connected component of \(T^{\prime}-\{XY\}\) containing \(X\) (resp. \(Y\)). As \(X\in\mathcal{E}_{X}\) and \(Y\in\mathcal{E}_{Y}\), there is an edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\) such that \(X^{\prime}\in\mathcal{E}_{X}\) and \(Y^{\prime}\in\mathcal{E}_{Y}\). As \(T^{\prime}\) is a join tree and \(XY\) is an edge of \(P_{T^{\prime}}(X^{\prime},Y^{\prime})\), \(X^{\prime}\cap Y^{\prime}\subseteq X\cap Y\). Hence, \(XY\) is an edge of \(tuj(T)\). \(\Leftarrow\) : let \(X^{\prime}Y^{\prime}\) be an edge of \(P_{T}(X,Y)\), such that \(X\cap Y=X^{\prime}\cap Y^{\prime}\), and let \(T^{\prime}\) be the graph \((T-\{X^{\prime}Y^{\prime}\})+\{XY\}\). \(T^{\prime}\) is a tree with the same weight as \(T\) (since \(w(XY)=w(X^{\prime}Y^{\prime})\)), so by Characterization 4, \(T^{\prime}\) is also a join tree of \(H\), and therefore, \(XY\) is an edge of \(UJ(H)\). Thus, we refind Characterization 8 from Property 10 and Characterization 12. Conversely, Characterization 12 can be deduced from Characterization 8 and Property 11 below, which shows that any \(\alpha\)-acyclic hypergraph is an atom hypergraph up to isomorphism. **Notation 3**. : _Let \(\mathcal{E}\) and \(\mathcal{E}^{\prime}\) be two sets and let \(f\) be a one-to-one mapping from \(\mathcal{E}\) to \(\mathcal{E}^{\prime}\). For each graph \(K=(\mathcal{E},E_{K})\), \(f(K)\) denotes the graph obtained from \(K\) by isomorphism \(f\), i.e., \(f(K)=(\mathcal{E}^{\prime},\{f(X)f(Y),XY\in E_{K}\})\)._

**Property 11**. : _Let \(H=(V,\mathcal{E})\) be an \(\alpha\)-acyclic hypergraph. Then there is a connected chordal graph \(G=(V^{\prime},E_{\mathcal{C}})\) and a one-to-one mapping \(f\) from \(\mathcal{E}\) to \(\mathcal{A}(G)\) such that : (1) for each tree \(T=(\mathcal{E},E_{T})\), \(T\) is a join tree of \(H\) if and only if \(f(T)\) is an atom tree of \(G\); (2) \(AG(G)=f(U\!I(H)\); (3) If \(H\) is connected, then for each pair \(\{X,Y\}\) of \(\mathcal{E}\), \(f(X)\cap f(Y)=X\cap Y\); otherwise, there is an element a of \(V^{\prime}\), such that, for each pair \(\{X,Y\}\) of \(\mathcal{E}\), \(f(X)\cap f(Y)=(X\cap Y)+\{a\}\); (4) for each join tree \(T\) of \(H\), \(tuj(f(T))=f(tuj(T))\)._

Proof. : By Characterization 11, it is sufficient to find a connected \(\alpha\)-acyclic clutter \(H^{\prime}=(V^{\prime},\mathcal{E}^{\prime})\) and a one-to-one mapping \(f\) from \(\mathcal{E}\) to \(\mathcal{E}^{\prime}\), such that: 1) for each tree \(T=(\mathcal{E},E_{T})\), \(T\) is a join tree of \(H\) if and only if \(f(T)\) is a join tree of \(H^{\prime}\); 2) \(U\!I(H^{\prime})=f(U\!I(H)\), and items 3) and 4). Let \(\mathcal{E}^{\prime}\) be defined from \(\mathcal{E}\) by adding a new specific element \(a_{X}\) to each element of \(\mathcal{E}\), which is not inclusion-maximal in \(\mathcal{E}\), and adding a new common element \(a\) to each element of \(\mathcal{E}\) if \(H\) is not connected. Let \(f\) map each element of \(\mathcal{E}\) to the element of \(\mathcal{E}^{\prime}\) obtained from it, let \(V^{\prime}=\cup_{X\in\mathcal{E}^{\prime}}X\), and let \(H^{\prime}=(V^{\prime},\mathcal{E}^{\prime})\). By definition, \(H^{\prime}\) is a connected clutter satisfying 3). As for each added element \(a_{X}\) (resp. \(a\)), the set of elements of \(\mathcal{E}^{\prime}\) containing it is reduced to \(\{X\}\) (resp. equal to \(\mathcal{E}^{\prime}\)), \(H^{\prime}\) is \(\alpha\)-acyclic and satisfies 1); 2) follows from 1), and 4) follows from 3).