Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.2. Максимальные полные подграфы (клики)

Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф. Таким образом, максимальный полный подграф (клика) графа есть порожденный подграф, построенный на подмножестве вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа построенный на множестве вершин содержащем т. е. не является полным. Следовательно, в противоположность максимальному независимому множеству, в котором не могут встретиться две смежные вершины, в клике все вершины попарно смежны. Совершенно очевидно, что максимальное независимое множество графа соответствует клике графа и наоборот, где дополнение графа

Вполне очевидно также, что понятие клики для неориентированного графа подобно понятию клики для графа; однако эта аналогия более глубокая, чем та, которая существует между понятиями клики и сильной компоненты (см. гл. 2). Клику в действительности можно рассматривать как такую сильную компоненту, в которой достижимость ограничена путями единичной длины (см. разд. 5 в гл. 2).

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

<< Предыдущий параграф Следующий параграф >>
Оглавление