Бояринцева Т.И., Мастихина А.А. Теория графов: методические указания

М.: МГТУ им. Н.Э. Баумана, 2014. — 37[3] с.: ил. — ISBN 978-5-7038-3994-2 [Методические указания к выполнению домашнего задания по курсу «Дискретная математика»] Аннотация.
Изложены основные понятия и теоретические результаты применения теории графов.
Приведены примеры, рассмотрены типовые задачи. Для студентов факультета «Робототехника и комплексная автоматизация», изучающих курс «Дискретная математика». ПРЕДИСЛОВИЕ.
Данные методические указания предназначены для студентов МГТУ им. Н.Э. Баумана, выполняющих типовой расчет по теории графов. Задачи типового расчета приведены в конце работы.
Теория графов является разделом дискретной математики. С помощью графов решается ряд оптимизационных задач. Указания написаны по материалам лекций и семинаров курса «Дискретная математика», читаемого авторами в МГТУ им. Н.Э. Баумана.
В методических указаниях изложены основные понятия теории графов, рассмотрены типовые задачи, которые решаются средствами данной теории, и представлены алгоритмы их решения. ОГЛАВЛЕНИЕ.
Предисловие.
Основные определения и понятия.
Способы задания графа.
Задачи об обходах графа.
Дерево. Минимальное остовное дерево.
Фундаментальная система циклов.
Построение дерева кратчайших путей.
Конденсация и база. Потоки в сетях.
Планарность. Вершинная раскраска.
Литература.