Tolerance graph

Материал из WikiGrapp
Версия от 12:37, 4 августа 2011; Glk (обсуждение | вклад) (Новая страница: «'''Tolerance graph''' --- толерантный граф. A graph <math>G = (V,E)</math> is a ''' tolerance graph''' (an ''' interval tolerance graph'''), if ther…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.