Дробно-хроматическое число: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Дробно-хроматическое число''' (''Fractional-chromatic number'') - Отображение <math>c</math> из ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Дробно-хроматическое число''' (''Fractional-chromatic number'') | '''Дробно-хроматическое число''' (''[[Fractional-chromatic number]]'') — Отображение <math>c</math> из набора <math>{\mathcal C}</math> независимых множеств [[граф|графа]] <math>G</math> в интервал <math>[0,1]</math> есть '''[[дробная раскраска]]''', если для каждой [[вершина|вершины]] <math>x</math> из <math>G</math> справедливо соотношение | ||
Отображение <math>c</math> из набора <math>{\ | |||
множеств графа <math>G</math> в интервал <math>[0,1]</math> есть '''дробная | |||
раскраска''', если для каждой вершины <math>x</math> из <math>G</math> справедливо | |||
соотношение | |||
<math>\sum_{S \in {\ | ::::::::<math>\sum_{S \in {\mathcal C}\mbox{ таким, что } x \in S} c(S) = 1.</math> | ||
S} c(S) = 1.</math> | |||
Величина дробной раскраски <math>c</math> есть <math>\sum_{S | Величина дробной раскраски <math>c</math> есть <math>\sum_{S \in {\mathcal C}} c(S)</math>. '''Дробно-хроматическим числом''' <math>\chi_{f}(G)</math> называется инфинум величин дробных раскрасок <math>G</math>. | ||
\in {\ | |||
<math>\chi_{f}(G)</math> называется инфинум величин дробных раскрасок | |||
<math>G</math>. | |||
==Литература== | ==Литература== | ||
[Discrete Math.] | * [Discrete Math.] | ||
Текущая версия от 16:48, 7 февраля 2011
Дробно-хроматическое число (Fractional-chromatic number) — Отображение [math]\displaystyle{ c }[/math] из набора [math]\displaystyle{ {\mathcal C} }[/math] независимых множеств графа [math]\displaystyle{ G }[/math] в интервал [math]\displaystyle{ [0,1] }[/math] есть дробная раскраска, если для каждой вершины [math]\displaystyle{ x }[/math] из [math]\displaystyle{ G }[/math] справедливо соотношение
- [math]\displaystyle{ \sum_{S \in {\mathcal C}\mbox{ таким, что } x \in S} c(S) = 1. }[/math]
Величина дробной раскраски [math]\displaystyle{ c }[/math] есть [math]\displaystyle{ \sum_{S \in {\mathcal C}} c(S) }[/math]. Дробно-хроматическим числом [math]\displaystyle{ \chi_{f}(G) }[/math] называется инфинум величин дробных раскрасок [math]\displaystyle{ G }[/math].
Литература
- [Discrete Math.]