# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight  
Our second algorithm, AG-max-weight (Algorithm 3), takes as input the weighted intersection graph of the atoms (which, in the case of a chordal graph, is the clique graph) and repeatedly adds the edges of weight \(k\) in decreasing order of \(k\). By Characterization 4, the atom trees of a connected graph \(G\) are the maximum weight spanning trees of the weighted intersection graph of the atoms of \(G\). We will present a general algorithm computing the union of the maximum weight spanning trees of \(G_{w}\) for each weighted connected graph \(G_{w}\) with natural integer weights on the edges. This general algorithm, called Union-max-weight (Algorithm 4), is inspired by the following algorithm from [PERSON], which computes a _minimum_ weight spanning tree of \(G_{w}\) : initialize graph \(T^{\prime}\) as edgeless and for each edge \(xy\) of \(G_{w}\) in _increasing_ order of weight, add \(xy\) to \(T^{\prime}\) if and only if \(x\) and \(y\) are in different connected components of \(T^{\prime}\). As we want to compute a _maximum_ weight spanning tree, we will process the edges in _decreasing_ order of weight; the algorithm computes each maximum weight spanning tree of \(G_{w}\). Thus, an edge \(xy\) of weight \(k\) may be added to \(T^{\prime}\) by this last algorithm if and only if \(x\) and \(y\) are in different connected components of \(T^{\prime}\) just after processing the edges of weight at least \(k+1\). These components are independent of the graph \(T^{\prime}\) computed so far by item a) of Lemma 2 below. Lemma 2: _Let \(G_{w}=(V,E,w)\) be a weighted connected graph with natural integer weights on the edges, let \(T\) be a maximum weight spanning tree of \(G\), let \(U\)M be the union of the maximum weight spanning trees of \(G\) and for a natural integer \(k\), and let \(G_{k}\) (resp. \(T_{k}\), \(U\)M\({}_{k}\)) be the graph whose vertex set is \(V\) and whose edges are the edges of \(G\) (resp. \(T\), \(U\)M) of weight at least \(k\). Then, (a) \(G_{k}\), \(T_{k}\) and \(U\)M\({}_{k}\) have the same connected components; (b) the edges of \(U\)M of weight \(k\) are the edges of \(G\) of weight \(k\) whose endpoints are in different connected components of \(U\)M\({}_{k+1}\)._  
Proof: (a) As each connected component of \(T_{k}\) is a subset of a connected component of \(U\)M\({}_{k}\), which is itself a subset of a connected component of \(G_{k}\), it is sufficient to show that each connected component of \(G_{k}\) is a subset of a connected component of \(T_{k}\), or equivalently, that, for each edge \(xy\) of \(G_{k}\), \(P_{T}(x,y)\) is a path in \(T_{k}\). Let \(xy\) be an edge of \(G_{k}\). For each edge \(x^{\prime}y^{\prime}\) of \(P_{T}(x,y)\), \(w(xy)\leq w(x^{\prime}y^{\prime})\) (otherwise, \((T-\{x^{\prime}y^{\prime}\})+\{xy\}\) would be a spanning tree of \(G\) of strictly greater weight than \(T\)), so \(P_{T}(x,y)\) is a path in \(T_{k}\). (b) Let \(xy\) be an edge of \(G\) of weight \(k\). Let us show that \(xy\) is an edge of \(U\)M if and only if \(x\) and \(y\) are in different connected components of \(U\)M\({}_{k+1}\). We assume that \(xy\) is an edge of \(U\)M. Let \(T\) be a maximum weight spanning tree of \(G\), such that \(xy\) is an edge of \(T\). \(x\) and \(y\) are in different connected components of \(T_{k+1}\), and therefore of \(U\)M\({}_{k+1}\) by a). Conversely, we assume that \(x\) and \(y\) are in different connected components of \(U\)M\({}_{k+1}\). Let \(T\) be a maximum weight spanning tree of \(G\). As \(x\) and \(y\) are in different connected components of \(T_{k+1}\), there is an edge \(x^{\prime}y^{\prime}\) of \(P_{T}(x,y)\) of weight at most \(k\). Then, \((T-\{x^{\prime}y^{\prime}\})+\{xy\}\) is a maximum weight spanning tree of \(G\), and therefore \(xy\) is an edge of \(U\)M.  
Item (b) of Lemma 2 provides an inductive definition of the edges of weight \(k\) of the union of the maximum weight spanning trees, and therefore a simple iterative algorithm to compute them.