ДИСКРЕТНА МАТЕМАТИКА

Abstract

Навчальний посібник створений за матеріалами лекцій з курсу «Дискретна математика». Він містить основні положення теорії множин, комбінаторики та теорії графів. Зокрема розглянуті основи теорії множин, відповідностей та відношень на множинах. Представлені відношення еквівалентності та порядку, детально описані їх властивості. Основні положення комбінаторики представлені законами комбінаторики, комбінаторними вибірками та типовими комбінаторними алгоритмами. Значна увага приділена теорії графів. Розглянуті базові визначення теорії графів, способи створення та властивості графів, відношення та відображення на графах, магічні числа графів. Окремо розглянуто дерева, їх властивості та ліс. Описані основні алгоритми на графах, призначені для обходу графів, визначення найкоротших шляхів у них та побудови мінімальних остовних дерев. Наведені базові поняття та теореми, пов’язані з правильним мінімальним розфарбуванням графів. Дано код або псевдокод основних алгоритмів розфарбування. Посібник може бути корисним для інженерів та студентів технічних спеціальностей.