2.2. Максимальные полные подграфы (клики)
Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф. Таким образом, максимальный полный подграф (клика) графа 
есть порожденный подграф, построенный на подмножестве 
вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа 
построенный на множестве вершин 
содержащем 
т. е. 
не является полным. Следовательно, в противоположность максимальному независимому множеству, в котором не могут встретиться две смежные вершины, в клике все вершины попарно смежны. Совершенно очевидно, что максимальное независимое множество графа 
соответствует клике графа 
и наоборот, где 
дополнение графа 
Вполне очевидно также, что понятие клики для неориентированного графа подобно понятию клики для графа; однако эта аналогия более глубокая, чем та, которая существует между понятиями клики и сильной компоненты (см. гл. 2). Клику в действительности можно рассматривать как такую сильную компоненту, в которой достижимость ограничена путями единичной длины (см. разд. 5 в гл. 2).
Аналогично тому, как было определено число независимости графа, с помощью соотношения (3.3) мы можем определить кликовое число графа (известное также как густота или плотность). Это — максимальное число вершин в кликах данного графа. Тогда, образно говоря, у «плотного» графа кликовое число будет, вероятно, больше, а число независимости меньше, в то время как у «разреженного» графа, по всей вероятности, будет иметь место противоположное соотношение между этими числами.
