Теорема на Туран за графите

Обложка......Page 1
Титульный лист......Page 3
Посвящение и выходные данные......Page 4
СЪДЪРЖАНИЕ......Page 142
Предговор......Page 5
§ 1. Задачата за Кьонигсбергските мостове......Page 11
§ 2. „По света"......Page 12
§ 3. Какво е това, граф?......Page 14
§ 4. Изоморфни графи......Page 15
§ 5. Подграф......Page 17
§ 6. Път, верига и цикъл......Page 19
§ 7. Свързани графи......Page 21
§ 8. Компоненти......Page 22
§ 9. Ойлерови графи......Page 24
§ 10. Алгоритъм на Фльори за построяване на ойлерови цикли......Page 27
§ 11. Произволно-ойлерови графи......Page 28
§ 12. Произволно-полуойлерови графи......Page 30
§ 13. Път в свързан граф, който съдържа всяко ребро по веднъж в две посоки......Page 33
§ 14. Обосноваване на алгоритъма на Фльори......Page 35
§ 15. Задачи за най-късия път......Page 37
§ 16. Хамилтънови графи......Page 39
§ 17. Достатъчни условия на Дирак и Оре за съществуване на хамилтънова верига......Page 42
§ 1. Независими множества......Page 45
§ 2. Клики......Page 50
§ 3. Доминиращи множества......Page 56
§ 4. 2-хроматични графи......Page 59
§ 5. Теорема на Туран за графи, които не съдържат триъгълници......Page 63
§ 6. Една зависимост между $v(G)$, $e(G)$, $d(G)$ и $\alpha(G)$......Page 67
§ 7. Графи с четен брой върхове и с връх с максимална степен, през който минава точно един триъгълник......Page 71
§ 8. Върхове с максимална степен и триъгълници през тях в графи с четен брой върхове......Page 79
§ 9. Върхове с максимална степен и триъгълници през тях в графи с нечетен брой върхове......Page 81
§ 10. Графи с $n$ върхове, $\left[\frac{n^2}{4}\right] - 1$ ребра и с връх с максимална степен, през който не минават триъгълници......Page 82
§ 11. Някои неравенства, свързани с върховете с максимална степен и броя на триъгълниците през тях......Page 86
§ 1. Второ доказателство на теоремата на Туран за графи без триъгълници......Page 92
§ 2. 3-оцветими графи......Page 95
§ 3. Теорема на Туран за графи без тетраедри......Page 100
§ 4. Теорема на Зиков за графи без тетраедри......Page 104
§ 5. Върху броя на ребрата на графи без тетраедри с даден брой върхове и число на независимост......Page 108
§ 6. Граф без тетраедри с $n$ върхове, число на независимост $\alpha\geq\frac{n}{3}$ и максимален брой ребра......Page 115
§ 7. Граф без тетраедри с $n$ върхове, число на независимост $\alpha\geq\frac{n}{3}$ и максимален брой триъгълници......Page 118
§ 8. Второ доказателство на теоремата на Туран за графи без тетраедри......Page 119
§ 9. Второ доказателство на теоремата на Зиков за графи без тетраедри......Page 122
§ 10. Едно неравенство за броя на триъгълниците в граф......Page 126
§ 11. Една зависимост между $v(G)$, $\alpha(G)$, $d{G)$ и $t(G)$......Page 132
Выходные данные......Page 144
КНИГИ ОТ БИБЛИОТЕКА „АЛЕФ"......Page 145