Ёмкость графа: различия между версиями

'''Ёмкость графа''' (''[[Graph capacity]]'') - параметр [[граф|графа]], выражаемый формулой  

<math> \theta(G) \, = \, \sup_{k \geq 1}\sqrt[k]{\alpha_{0}(G^{k})},</math>  

где <math>\alpha_{0}</math>--- ''число независимости'', <math>G^{k}</math> --- ''[[сильная степень графа]]''. Введен К.Шенноном в связи с задачами из теории информации.