Увод в теория на графите (екстремална теория)

вид:	изборен	Курс 2; зимен семестър
хорариум:	3 часа лекции
преподавател:	проф. дмн Н. Ненов
разписание:	Курсът не се чете през този семестър.

Анотация

В този курс ще бъдат разгледани редица класически и съвсем нови резултати за крайни графи. Тези резултати са свързани с основните параметри на краен граф (кликово число, число на независимост, хроматично число, matching number). Ще бъдат изложени класическите теореми на Хол, Фробениус, Кьониг, Тат-Берж за максималните сдвоявания в граф, теоремите на Зиков и Туран, разлагане на Галлаи и Едмондс на произволен граф и други (виж тематичния план) В курса ще бъдат формулирани някои нерешени проблеми и ще се обсъдят възможностите за тяхното решаване. Специално внимание ще бъде отделено на методите за получавне на малки графи с дадени свойства. Получаването на такива графи в момента е много актуално и се осъшествява с комбинирането на теоретични и компютърни методи.

Тематичен План

№	Тема	лекции
1.	Уводна част: Основни понятия и терминология. Изображение на графи. Пълни хроматични графи.	3 часа
2.	Клики на графи, теореми на Туран и Зиков.	6 часа
3.	Независими множества от ребра в граф (matchings), теореми на Кьониг, Хол и Фробениус.	3 часа
4.	Максимални сдвоявания (matchings) в произволни графи. Формула на Тат-Берж.	6 часа
5.	Разлагане на Галлай-Едмондс за произволни графи.	3 часа
6.	Хроматично число на граф. Критични хроматични графи.	3 часа
7.	Малки критични хроматични графи.	3 часа
8.	Максимални независими множества от върхове в граф. Алфа-критични графи. Теорема на Хайнал за алфа-критичните графи.	3 часа
9.	Обощени хроматични графи. Обобшения на теоремата на Туран.	3 часа
10.	Балансирани и наситени множества от върхове в даден граф.	3 часа
11.	Малки графи на Фолкман.	5 часа
12.	Спектър, спектрален радиус и квадратична форма на граф. Теорема на Моцкин и Щраус.	4 часа

Конспект

1. Основни понятия. Изоморфизъм на графи. Подграфи. Породени подграфи. Свързаност.
2. 2-хроматични графи. Теорема на Кьониг.
3. Теорема на Туран за графи без триъгълници (две доказателства).
4. Графи без 4-цикли. Оценка отгоре за броя на ребрата.
5. r-хроматични графи. Сума на Зиков. Оценка отгоре за броя на ребрата. Граф на Туран. Оценка отгоре за броя на ребрата с помощта на графа на Туран.
6. Теорема на Туран.
7. Сдвоявания в граф. Характеристика на максимум сдвояванията (теорема на Берж).
8. Върхови покрития и независимост.
9. Ребрени покрития и независимост.
10. Сдвоявания в 2-хроматични графи. Теорема на Кьониг.
11. Теорема на Филип Хол за сдвояванията в 2-хроматични графи.
12. Формула на Кьониг-Оре.
13. Хроматично число. Оценка отгоре. Алчен (greedy) алгоритъм. Две следствия.
14. Оценки отдолу на хроматичното число.
15. Теорема на Брукс.
16. Графи без триъгълници с произволно голямо хроматично число. Конструкция на Мицелски.
17. Критични хроматични графи.
18. Теорема на Дирак.
19. Минимални хроматични графи.
20. Спектър на граф. Коспектрални графи.
21. Пресмятане броя на маршрутите в даден граф. Основна теорема. Следствия.
22. Графи, чийто спектър се състои само от две собствени стойности.
23. Спектрален радиус на графа.

Актуални конспекти по "Увод в теория на графите (екстремални задачи)"

Год.	Преподавател	Забележки
11/12	Н. Ненов	Конспект за редовно обучение

Литература

1. C. Berge. Graphs and Hypergraphs, North-Holland Math. Library, v6, 1970.
2. J. Bondy, U. Murthy, Graph theory, Springer, 2008.
3. L. Lovasz, M. Plummer, Matching theory, Academiai Kiado, Budapest, 1986.