Clique tree: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Clique tree''' --- кликовое дерево. Suppose <math>G</math> is any graph and <math>T</math> is a tree whose vertices --- call them ''nodes'' to hel…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Clique tree''' | '''Clique tree''' — ''[[кликовое дерево]].'' | ||
Suppose <math>G</math> is any graph and <math>T</math> is a tree whose vertices | 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> | |||
==Литература== | |||
<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 | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
words, if every <math>T_{v}</math> is a subtree of <math>T</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.