|
|
Факултет по математика и информатика - Теория на графите |
 |
| Лектор | доц. д-р Манчо Манев | Анотация | Основни понятия за неориентирани и ориентирани графи. Свързаност, факторизации и сдвоявания върху графи. Екстремални задачи. Равнинни графи. Оцветяване на графи. Класически задачи, решими с графи. | Съдържание | 1. Основни понятия за неориентирани графи. Геометрична реализация , изоморфизъм, матрично представяне, видове графи, термини, описващи локалните свойства, последователности от ребра и върхове. | 2. Свързаност от неориентиран граф. Свързаност и теорема на Менгер. Дърво и скелет на неориентиран граф. Разделящи множества и разрези. Прост, двувалентен, хомогенен граф. | 3. Основни понятия за ориентирани графи. Геометрична реализация, изоморфизъм, термини, описващи локалните свойства, последователности от дъги и върхове. | 4. Силна свързаност на ориентиран граф и бинарни отношения между ориентирани графи. Силна свързаност. Ориентирани дървета разрези. Генеалогично дърво. Квазинареденост. | 5. Факторизации и метрика върху граф. Реброва, дъгова, върхова факторизация. Ойлерови цикли и контури. Хамилтонови вериги и цикли, пътища и контури. Метрика върху свързан граф. | 6. Потоци в граф. Теорема на Форд-Фалкерсон за максималния поток и минималния разрез. | 7. Сдвоявания. Задача за максималното сдвояване. Теорема на Кьонг-Хол и нейни варианти. Пълно сдвояване теорема на Тат за 1-факторите. | 8. Екстремални задачи. Пълни подграфи и теорема на Туран. Двуделни подграфи и задача на Заранкиевич. | 9. Равнинни графи. Теорема на Понтягин-Куратовски. Дуален и спрегнат граф на равнинен граф. Правилни графи. Условия за равнинни графи. | 10. Оцветяване на граф. Оцветяване ва върхове, ребра и области на граф. Хроматично число и теорема на Брукс. Хроматичен клас и теорема на Визинг. Теорема за петте цвята. Проблема за четирите цвята. Графи върху повърхнини. | |
|
|
|
 |
 |
 |
© 2009 ФМИ |