Теория графов : УМК / Р. И. Тышкевич; БГУ, ММФ

Abstract

Теория графов является одним из наиболее бурно развивающихся разделов математики, что в значительной степени вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, теории расписаний и дискретной оптимизации. Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной степени через теорию графов происходит ныне проникновение математических методов в науку и технику. Материал дисциплины ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и другим дисциплинам. Основной задачей этой дисциплины является обучение студентов основам теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и, в связи с этим, — построению эффективных алгоритмов.