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

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''<math>k</math>-Насыщенный граф''' (''<math>k</math>-Saturated graph'') - граф, который не содержит ...)
 
Строка 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

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

Литература

[J. Graph Theory]