Индифферентный граф: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Индифферентный граф''' (''[[Indifference graph]]'') | '''Индифферентный граф''' (''[[Indifference graph]]'') — [[Неориентированный граф]] <math>\,G</math> является индифферентным [[граф|графом]], если существует действительная функция <math>\,f</math> на [[вершина|вершинах]] такая, что вершины <math>\,u</math> и <math>\,v</math> [[смежные вершины|смежные]], если и только если <math>|f(u)-f(v)| \leq 1</math>. | ||
Это понятие ввел Ф.Робертс в 1969 г.; он же показал, что этот класс | Это понятие ввел Ф.Робертс в 1969 г.; он же показал, что этот класс | ||
графов эквивалентен классу [[единичный интервальный граф|''единичных интервальных'' графов]]. | графов эквивалентен классу [[единичный интервальный граф|''единичных интервальных'' графов]]. | ||
==Литература== | ==Литература== | ||
[J. Graph Theory] | * [J. Graph Theory] | ||
Текущая версия от 12:14, 21 февраля 2011
Индифферентный граф (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]