Ёмкость графа: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Ёмкость графа''' (''Graph capacity'') - параметр графа, выражаемый формулой <math> \theta...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Ёмкость графа''' (''Graph capacity'') - | '''Ёмкость графа''' (''[[Graph capacity]]'') - параметр [[граф|графа]], выражаемый формулой | ||
параметр графа, выражаемый формулой | |||
<math> \theta(G) \, = \, | <math> \theta(G) \, = \, \sup_{k \geq 1}\sqrt[k]{\alpha_{0}(G^{k})},</math> | ||
\sup_{k \geq 1}\sqrt[k]{\alpha_{0}(G^{k})},</math> | |||
где <math>\alpha_{0}</math>--- ''число независимости'', | где <math>\alpha_{0}</math>--- ''число независимости'', <math>G^{k}</math> --- ''[[сильная степень графа]]''. Введен К.Шенноном в связи с задачами из теории информации. | ||
<math>G^{k}</math> | |||
--- ''сильная степень графа''. Введен К.Шенноном в связи с | |||
задачами из теории информации. | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Берж] | [Берж] | ||
Версия от 17:32, 15 октября 2009
Ёмкость графа (Graph capacity) - параметр графа, выражаемый формулой
[math]\displaystyle{ \theta(G) \, = \, \sup_{k \geq 1}\sqrt[k]{\alpha_{0}(G^{k})}, }[/math]
где [math]\displaystyle{ \alpha_{0} }[/math]--- число независимости, [math]\displaystyle{ G^{k} }[/math] --- сильная степень графа. Введен К.Шенноном в связи с задачами из теории информации.
Литература
[Лекции],
[Берж]