Съобщение Резултати от домашните по "Линейна алгебра" за студентите от специалност Информатика 1-ви курс, 1-ва група
29.01.2016
Съобщение Резултати от контролните и писмения изпит по "Линейна алгебра" за студентите от специалности Математика и Приложна математика
12.02.2016
Съобщение Резултати от контролните и писмения изпит по "Алгебра 1" за спец. "Компютърни науки", II курс, II поток.
25.01.2016
Съобщение Резултати от писмения изпит по "Висша алгебра" за спец. "Информатика", I курс.
05.07.2015
Съобщение Резултати от писмения изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, I поток.
01.07.2015
Съобщение Резултати от писмения изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, II поток.
1.07.2015
Съобщение Резултати от писмения изпит по "Линейна алгебра" за спец. "Информатика", I курс.
15.02.2015
Съобщение Резултати от писмения изпит по "Алгебра-1" за студентите от специалност Компютърни науки, поток 1 и резултати по "Алгебра" на спец. Информационни системи на студенти от минали години.
5.02.2015
Съобщение Резултати от писмения изпит по "Линейна алгебра" за студентите от специалности Математика, Приложна математика и Статистика
3.02.2015
Съобщение Резултати от писмения изпит по "Алгебра 1" за спец. "Компютърни науки", II курс, II поток.
27.01.2015
Съобщение Резултати от писмен изпит по "Алгебра 2" за спец. "Компютърни науки", II курс.
07.07.2014
Съобщение Резултати от писмен иэпит по "Висша Алгебра" за спец. "Информатика", I курс.
05.07.2014
Съобщение Резултати от писмения изпит по "Алгебра 2" за спец. "Компютърни Науки", II курс, II поток.
1.07.2014
Съобщение Занятията по "Алгебрична теория на числата" ще се провеждат в понеделник от 9 до 13 часа в ауд. 03 на ФМИ. Първата сбирка е на 10.03.2014.
Съобщение Резултати от писмен иэпит по "Алгебра 1" за спец. "Компютърни науки", I курс, I поток.
03.02.2014
Съобщение Резултати по "Алгебра 1" за спец. "Компютърни науки", I курс, I поток.
26.01.2014
Съобщение Резултати от Контролни работи по "Алгебра 1" за спец. "Компютърни Науки", I курс, II поток.
24.01.2014
Съобщение Контролна работа по "Висша Алгебра 2 " за спец. "Математика", I курс.
8.11.2013
Съобщение Писмен изпит по "Висша Алгебра" за спец. "Математика и Информатика", I курс.
5.07.2013
Съобщение Писмен изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, I поток.
5.07.2013
Съобщение Писмен изпит по "Висша Алгебра 1" за спец. "Математика", I курс.
5.07.2013
Съобщение Писмен изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, II поток.
5.07.2013
Съобщение Домашна работа №1 по "Алгебра 2" за спец. "Компютърни науки", II курс, II поток.
25.03.2013
Съобщение Писмен изпит по "Алгебра 1" за спец. "Компютърни науки", I курс, I поток.
12.02.2013
Съобщение Писмен изпит по "Алгебра 1" за спец. "Компютърни науки", I курс, II поток.
12.02.2013
Съобщение Резултати от писмения изпит по "Алгебра" за спец. "Информационни системи", I курс.
5.02.2012
Съобщение Резултати от писмения изпит по "Линейна алгебра" за спец. "Математика", I курс.
4.02.2013
Съобщение Резултати от писмения изпит по "Висша алгебра" за спец. "Информатика", I курс.
02.07.2012
Съобщение Резултати от писмения изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, II поток.
27.06.2012
Съобщение Резултати от писмения изпит по "Алгебра 2" за спец. "Компютърни науки", II курс, I поток.
22.06.2012
Съобщение Резултати от писмения изпит по "Висша алгебра" за спец. "Математика и Информатика", I курс.
11.06.2012
Съобщение Резултати от контролните работи по "Алгебра 2" за спец. "Компютърни науки", II курс, II поток.
2.06.2012
Съобщение Резултати от контролната работа по "Висша алгебра" за спец. "Математика и Информатика", I курс.
27.03.2012

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

вид: изборен Курс 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. Спектрален радиус на графа.

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

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

Литература

  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.
ФМИ  |  Home  |  Top