K-Насыщенный граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>k</math>-Насыщенный граф''' (''<math>k</math>-Saturated graph'') - граф, который не содержит ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Насыщенный граф''' (''<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}</math> <math>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] | ||
Версия от 16:35, 24 ноября 2009
[math]\displaystyle{ k }[/math]-Насыщенный граф ([math]\displaystyle{ k }[/math]-Saturated graph) - граф, который не содержит полный граф [math]\displaystyle{ K_{k} }[/math] [math]\displaystyle{ 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]