Код: 316200

Назва:

Додаткові розділи теорії графів

Анотація: Вибіркова математична дисципліна. Розглядаються властивості важливих класів як неорієнтованих (графи перетинів, дерева, графи блоків, медіанні графи), так і орієнтованих графів (турніри, графи Маркова відображень дерев у себе). Курс має на меті поглибити знання дискретної математики та ознайомити студентів із вибраними розділами сучасної теорії графів.

Тип дисципліни: вибіркова (професійної та практичної підготовки)

Рік навчання: 2

Семестр: 3

Кількість кредитів: 3

Форма контролю: залік

Викладач(і): ст. в., к. н. Козеренко С.О.

Результати навчання: Формалізувати задачі, сформульовані мовою певної предметної галузі; формулювати їх математичну постановку та обирати раціональний метод вирішення; розв'язувати отримані задачі аналітичними та чисельними методами, оцінювати точність та достовірність отриманих результатів. Виявляти здатність до самонавчання та продовження професійного розвитку. Уміти організувати власну діяльність та одержувати результат у рамках обмеженого часу. Уміти здійснювати збір, опрацювання, аналіз, систематизацію науковотехнічної інформації, уникаючи при цьому академічної недоброчесності. Демонструвати навички професійного спілкування, включаючи усну та письмову комунікацію українською мовою та принаймні однією з офіційних мов ЄС.

Спосіб навчання: дистанційний (аудиторний)

Необхідні обовязкові попередні й супутні модулі: базові знання з дискретної математики, теорії графів, комбінаторики.

Зміст дисципліни: Першою темою курсу є графічні мультимножини. Спочатку наводиться алгоритм Гавела-Хакімі та відповідний рекурсивний критерій графічності мультимножини. Потім формулюється теорема Ердеша-Галлаі й доводиться характеризація мультимножин степенів вершин дерев. Також розглядаються відповідні проблеми для псевдографів та мультиграфів. Після опануваня матеріалу даної теми, студенти повинні вміти користуватися алгоритмом перевірки мультимножини на графічність та критеріями графічних, псевдографічних та мультиграфіних мультимноин. У другій темі курсу досліджуються властивості центру та периферії зв'язного графа. Наводяться основні властивості радіусу та діаметру графа, будуються графи із цими заданими параметрами. Доводиться, що кожен граф є підграфом, породженим центром деякого зв'язного графа та дається характеризація периферій. Третя тема курсу присвячена основам метричної теорії графів. Вступ до останньої відбувається через розгляд основних типів множин вершин скінченного зв'язного графа та детальним розглядом важливих класів модулярних і медіанних графів. Після опанування цього підрозділу, студенти повинні вміти користуватися основними метричними властивостями графів та перевіряти на медіанність заданий граф. У четвертій темі розглядається зображення графів як графів перетинів, а саме, детально вивчаються дерева, графи блоків та реберні графи. За допомогою зовнішніх критеріїв для цих класів графів, студенти повинні вміти доводити різні властивості графів перетинів та перевіряти належність заданого графа одному з вищеназваних класів графів.


Рекомендована література: 1. Buckley F. , Harary F. Distance in graphs. Addison-Wesley, Reading, 1990. - 335.
2. Diestel R. Graph Theory. - Electronic edition, Springer-Verlag New York, 2000/ - 322.
3. Зыков А.А. Основы теории графов. - М.: Наука, 1987. -383 с.
4. Харари Ф. Теория графов. - М.: Мир, 1973. - 296 с.


Форми та методи навчання: лекції, практичні заняття , ідивідуальні роботи, обговорення методів і прикладів вирішення задач, опрацювання літератури, вивчення основних доведень.

Методи й критерії оцінювання: рейтингова система оцінювання за 100-бальноюшкалою: за роботу в семестрі (контрольні роботи. індивідуальне завдання, активність на практичних заняттях) -70%; залік - 30%.

Мова навчання: українська