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