Аноним

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>.