4624
правки
Индифферентный граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Индифферентный граф''' (''Indifference graph'') - Неориентированный граф <math>G</math> явл...) |
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>. | ||
Неориентированный граф <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] | ||