Clique tree: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Clique tree''' --- кликовое дерево. Suppose <math>G</math> is any graph and <math>T</math> is a tree whose vertices --- call them ''nodes'' to hel…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Clique tree''' --- кликовое дерево.  
'''Clique tree''' — ''[[кликовое дерево]].''


Suppose <math>G</math> is any graph and <math>T</math> is a tree whose vertices --- call
Suppose <math>\,G</math> is any [[graph, undirected graph, nonoriented graph|graph]] and <math>\,T</math> is a [[tree]] whose [[vertex|vertices]] — call them ''[[node|nodes]]'' to help avoid confusing them with the vertices of <math>\,G</math> are precisely the ''[[maxclique|maxcliques]]'' of <math>\,G</math>. For every <math>\,v \in V(G)</math>, let <math>\,T_{v}</math> denote a [[subgraph]] of <math>\,T</math> induced by those nodes that contain <math>\,v</math>. If every such <math>\,T_{v}</math> is connected in other words, if every <math>\,T_{v}</math> is a [[subtree]] of <math>\,T</math> then call <math>\,T</math> a '''clique tree''' for <math>\,G</math>.
them ''nodes'' to help avoid confusing them with the vertices of <math>G</math>
 
--- are precisely the ''maxcliques'' of <math>G</math>. For every
==Литература==
<math>v \in V(G)</math>, let <math>T_{v}</math> denote a subgraph of <math>T</math> induced by those nodes
 
that contain <math>v</math>. If every such <math>T_{v}</math> is connected --- in other
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
words, if every <math>T_{v}</math> is a subtree of <math>T</math> --- then call <math>T</math> a '''clique tree''' for <math>G</math>.

Текущая версия от 10:46, 24 октября 2018

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.