Лекция: Расщепляющиеся графы

Расщепляющимся графом является граф, вершины который разделяются на клику и независимое множество вершин.

Расщепление графа на клику и независимое множество вершин не уникально и встречается у ряда графов. Например, путь a-b-c является можно представить тремя способами:

1. клика {a,b} и независимое множество {c};

2. клика {b,c} и независимое множество {a};

3. клика {a} и независимое множество {a,c}.

Для значений числа вершин n было высчитано число существующих расщепляющих графов: