Tree model

Tree model --- древесная модель.

For a given graph [math]\displaystyle{ G = (V,E) }[/math], a tree model of [math]\displaystyle{ G }[/math] is a pair [math]\displaystyle{ (T, {\mathcal T}) }[/math], where [math]\displaystyle{ T }[/math] is a tree, and [math]\displaystyle{ {\mathcal T} }[/math] is a set of subtrees of [math]\displaystyle{ T }[/math], [math]\displaystyle{ {\mathcal T} = \{T_{v}: \; v \in V\} }[/math], such that [math]\displaystyle{ T_{u} \cap T_{v} \neq \emptyset }[/math] iff [math]\displaystyle{ (u,v) \in E }[/math]. It is well known that a graph has a tree model iff it is chordal.

A tree model for a chordal graph [math]\displaystyle{ G }[/math] is called a clique model, if the node set of [math]\displaystyle{ T }[/math] is the set [math]\displaystyle{ Cl }[/math] of cliques in [math]\displaystyle{ G }[/math] and [math]\displaystyle{ c \in T_{v} }[/math] is equivalent to [math]\displaystyle{ v \in c }[/math] for all [math]\displaystyle{ c \in Cl }[/math] and [math]\displaystyle{ v \in V }[/math]. It is known that every chordal graph has a clique model.

See also

• Tree-decomposition.