Crystal Trees

This work introduces the class of crystal trees and their mathematical modeling. Consider a simple undirected weighted graph \(G=(V,E)\) of edge weights \(c_e>0\) , for all \(e\in E\) . Let \(T_k\) be a spanning tree of G rooted at vertex \(k\in V\) , and \(\mathcal {P}^{T_k}_{ij}\) denote the edge set of the path between vertices i and j in \(T_k\) . Associate with every vertex \(v\in V\) of \(T_k\) a potential \(\varPhi ^{T_k}_v =\{c_e |\, e\in \mathcal {P}^{T_k}_{kv}\}\) , with \(\varPhi ^{T_k}_k=\emptyset \) . Let \(\varDelta _{uv}=\varPhi ^{T_k}_v \varDelta \varPhi ^{T_k}_u\) be the multiset symmetric difference between the potentials of the extremities of an edge \(\{u,v\}\in E\) . We say that these potentials are: (i) in equilibrium if \(max \{c_e|\, e\in \varPhi ^{T_k}_v\varDelta \varPhi ^{T_k}_u\} \le c_{uv}\) ; or (ii) in non-equilibrium, otherwise. If, for all edges in E, the potentials of their extremities are in equilibrium, then \(T_k\) is a crystal tree. We show that this new class of trees generalizes the Minimum Spanning Trees (MSTs) of a graph. We present theoretical results for crystal trees and an algebraic representation allowing us to describe MSTs by a system of linear inequalities. This opens up new possibilities for solving optimization problems with optimal tree structure in the set of constraints.