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