Tolerance graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Tolerance graph''' --- толерантный граф. A graph <math>G = (V,E)</math> is a ''' tolerance graph''' (an ''' interval tolerance graph'''), if ther…») |
(нет различий)
|
Текущая версия от 12:37, 4 августа 2011
Tolerance graph --- толерантный граф.
A graph [math]\displaystyle{ G = (V,E) }[/math] is a tolerance graph (an interval tolerance graph), if there exists a finite collection [math]\displaystyle{ I = \{I_{x}: x \in V\} }[/math] of closed intervals on a line and a set [math]\displaystyle{ t = \{t_{x}: x \in V\} }[/math] of positive numbers satisfying [math]\displaystyle{ (x,y) \in E }[/math] iff [math]\displaystyle{ |I_{x} \cap I_{y}| \geq \min \{t_{x}, t_{y}\} }[/math] (where [math]\displaystyle{ |I| }[/math] denotes the length of [math]\displaystyle{ I }[/math]).
The pair [math]\displaystyle{ (I,t) }[/math] is called a tolerance representation of [math]\displaystyle{ G }[/math]. A tolerance representation [math]\displaystyle{ (I,t) }[/math] is bounded if [math]\displaystyle{ t_{x} \geq |I_{x}| }[/math] for all [math]\displaystyle{ x \in V }[/math]. [math]\displaystyle{ G }[/math] is a bounded tolerance graph, if [math]\displaystyle{ G }[/math] is a tolerance graph which admits a bounded tolerance representation.
The class of tolerance graph is the subclass of weakly chordal graphs.