Clique tree

Clique tree — кликовое дерево.

Suppose [math]\displaystyle{ \,G }[/math] is any graph and [math]\displaystyle{ \,T }[/math] is a tree whose vertices — call them nodes to help avoid confusing them with the vertices of [math]\displaystyle{ \,G }[/math] — are precisely the maxcliques of [math]\displaystyle{ \,G }[/math]. For every [math]\displaystyle{ \,v \in V(G) }[/math], let [math]\displaystyle{ \,T_{v} }[/math] denote a subgraph of [math]\displaystyle{ \,T }[/math] induced by those nodes that contain [math]\displaystyle{ \,v }[/math]. If every such [math]\displaystyle{ \,T_{v} }[/math] is connected — in other words, if every [math]\displaystyle{ \,T_{v} }[/math] is a subtree of [math]\displaystyle{ \,T }[/math] — then call [math]\displaystyle{ \,T }[/math] a clique tree for [math]\displaystyle{ \,G }[/math].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.