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