След като се запознахме с основите на графите, вече е време да ги ползваме с пълната им сила. Ще се запознаем с ключови концепции в графите като Хамилтонови и Ойлерови цикли и какви алгоритми съществуват за откриването им. Ще се запознаем с изключително ползваният алгоритъм на Дейкстра за търсене на път в претеглен граф, който е основополагащ за много практически задачи, както и е основата на алгоритъма A*. Също така ще разгледаме и алгоритмите на Форд-Белман и Флойд, решаващи подобни задачи, и ще ги сравним по ползваемост и бързодействие с този на Дейкстра. Друга важна концепция, която ще разгледаме, са критичните ребра и върхове в свързаните графи и техните приложения и откриване. Не на последно място ще говорим за изключително важните потоци и максимален поток в претеглен граф.
Ако имате нужда от настаняване за датите 20ти и 21ви март, можете да се възползвате от преференциалните условия, които Парк хотел Москва предоставя на нашите ученици. Запазили сме туристическа спалня за 2 нощувки от 20.03.2013г. за 4 човека на преференциалната цена от 17.00 лева/ легло без закуска
Име на лекция | Материали |
---|---|
1. Топологично сортиране | Докладвай грешка в материал |
2. Ойлерови цикли | Докладвай грешка в материал |
3. Хамилтонови цикли | Докладвай грешка в материал |
4. Алгоритми на Форд-Белман и Флойд | Докладвай грешка в материал |
5. Алгоритъм на Дейкстра | Докладвай грешка в материал |
6. Свързаност, критични (артикулационни) ребра и върхове | Докладвай грешка в материал |
7. Потоци в граф | Докладвай грешка в материал |
8. Задача 1 - Гладният Том | Докладвай грешка в материал |
9. Задача 2 - Разходка в парка | Докладвай грешка в материал |
10. Задача 3 - Търговия на гравитация | Докладвай грешка в материал |
11. Задача 4 - Пропускателна способност | Докладвай грешка в материал |
12. Задача 5 - Кольо Теротръбиста | Докладвай грешка в материал |
13. Задача 6 - Стачкостан | Докладвай грешка в материал |
14. Задача 7 - Бай Иван | Докладвай грешка в материал |
15. Задача 8 - Преселване | Докладвай грешка в материал |