Специальная математика. Соловьев А.Е. - 59 стр.

  Получим: acd  aef  bc  ce
Эти конъюнкции и дают множества внешней устойчивости.
.{a, c, d}, {a, e, f}, {b, c}, {c, e}
Минимальное из них дает число внешней устойчивости (здесь 2).

Множества, одновременно внутренне и внешне устойчивые называются ядром графа.
Для рассмотренного графа - {b, c}
В графе может быть несколько ядер (например - 2)




или не быть совсем.




                                                4.12. Клика

Клика - максимально большой полный подграф данного графа.

                                a


                f                           b

                    e                   c
                                    d

        a   b   c       d   e       f
a           1   1
b                       1   1       1
c                           1       1
d                           1       1
e                                   1
f

        a   b   c        d e f
a                       1 1 1
b               1
c                       1
d
e
f

Построение Клики.
1. Строим дополнительный граф исходного графа.


    G                   a

                                                  — 59 —