50
правок
Изменения
→Нижняя оценка числом внутренней устойчивости
|definition=
Подмножество <tex>S</tex> вершин графа <tex>G</tex> называется '''внутренне устойчивымнезависимым''', если любые две вершины из <tex>S</tex> не смежны в <tex>G</tex>
}}
|definition=
'''Число внутренней устойчивостинезависимости''' <tex>\alpha(G)</tex> графа <tex>G(V,E)</tex> {{---}} <tex>max \{|S|:S \in V</tex> и S внутренне устойчиво в G<tex>\}</tex>
}}
{{Лемма
|statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориентированный граф с <tex>n</tex> вершинами .Тогда, <tex>n/\alpha \le \chi(G)</tex>.
|proof=
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>.Каждое из <tex>V_i</tex> {{---}} внутренне устойчивое независимое множество (поскольку вершины множества покрашены в один цвет при правильной покраски графа <tex>G</tex>, следовательно, они попарно не смежны внутри множества ).Заметим, что для произвольного <tex>i</tex>, <tex>|V_i| \le \alpha</tex> (т.к <tex>V_i</tex> внутренне устойчивонезависимое множество). То есть, <tex>\sum\limits^{\chi}_{i = 1}|V_i| = n \le \chi \alpha </tex>, следовательно <tex>n / \alpha \le \chi</tex>.
}}
== Верхняя оценка количеством ребер ==
{{Лемма
