Введение
1. Наследственные классы 9
1.1. Терминология 9
1.2. Определение и примеры наследственных классов 12
1.3. Энтропия 17
2. Критические классы 24
2.1. А дольные графы и ранг 24
2.2. Лемма о матрицах 28
2.3. Энтропия и ранг 31
2.4. Критические классы 35
2.5. Примеры и следствия 38
3. Классы ранга 1 43
3.1. Слои и ярусы 43
3.2. Константный ярус 44
3.3. Полиномиальный ярус 45
3.4. Экспоненциальный ярус 49
3.5 Факториальный ярус 52
4. Независимые множества 55
4.1. Простые и сложные классы 55
4.2. Операции над классами графов 61
4.3. Сильно наследственные а-простые классы 65
4.4. Граничные классы 67
5. Некоторые а-простые классы 72
5.1. Область эффективности переборной стратегии 72
5.2. Класс Free(F,P8) 78
5.3. Класс Free(F) 87
5.4. Классы Free(P5) и Ргее{Р2+Ръ)
6. Кодирование графов 103
6.1. Универсальное кодирование 104
6.2. Оценки трудоемкости 108
Литература
