Индифферентный граф

Материал из WikiGrapp
Версия от 14:16, 27 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Индифферентный граф''' (''Indifference graph'') - Неориентированный граф <math>G</math> явл...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Индифферентный граф (Indifference graph) - Неориентированный граф [math]\displaystyle{ G }[/math] является индифферентным графом, если существует действительная функция [math]\displaystyle{ f }[/math] на вершинах такая, что вершины [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] смежные, если и только если [math]\displaystyle{ |f(u)-f(v)| \leq 1 }[/math]. Это понятие ввел Ф.Робертс в 1969 г.; он же показал, что этот класс графов эквивалентен классу единичных интервальных графов.

Литература

[J. Graph Theory]