Clique tree

Материал из WikiGrapp
Версия от 12:08, 11 ноября 2013; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.