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