K-Насыщенный граф: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''<math>k</math>-Насыщенный граф''' (''[[k-Saturated graph|<math>k</math>-Saturated graph]]'') -
'''<math>\,k</math>-Насыщенный граф''' (''[[k-Saturated graph|<math>\,k</math>-Saturated graph]]'')
[[граф]], который не содержит полный граф <math>K_{k}</math> <math>k \geq 3</math>, но
[[граф]], который не содержит полный граф <math>K_{k},k \geq 3</math>, но
добавление любого [[ребро|ребра]] приводит к возникновению <math>K_{k}</math>. Известно,
добавление любого [[ребро|ребра]] приводит к возникновению <math>\,K_{k}</math>. Известно,
что если <math>G</math> <math>k</math>-насыщенный на <math>n \geq k-2</math> [[вершина|вершинах]], то <math>|E(G)| \geq
что если <math>\,G</math> <math>\,k</math>-насыщенный на <math>n \geq k-2</math> [[вершина|вершинах]], то <math>|E(G)| \geq
(k-2)n - \left(\begin{array}{c} k-1 \\ 2 \end{array} \right )</math>.
(k-2)n - \left(\begin{array}{c} k-1 \\ 2 \end{array} \right )</math>.
==Литература==
==Литература==
[J. Graph Theory]
* [J. Graph Theory]

Текущая версия от 11:56, 13 мая 2011

[math]\displaystyle{ \,k }[/math]-Насыщенный граф ([math]\displaystyle{ \,k }[/math]-Saturated graph) — граф, который не содержит полный граф [math]\displaystyle{ K_{k},k \geq 3 }[/math], но добавление любого ребра приводит к возникновению [math]\displaystyle{ \,K_{k} }[/math]. Известно, что если [math]\displaystyle{ \,G }[/math] [math]\displaystyle{ \,k }[/math]-насыщенный на [math]\displaystyle{ n \geq k-2 }[/math] вершинах, то [math]\displaystyle{ |E(G)| \geq (k-2)n - \left(\begin{array}{c} k-1 \\ 2 \end{array} \right ) }[/math].

Литература

  • [J. Graph Theory]