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

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

Изложены основные понятия и теоретические результаты применения теории графов. Приведены примеры, рассмотрены типовые задачи.
Для студентов факультета «Робототехника и комплексная автоматизация», изучающих курс «Дискретная математика».

Фрагмент из книги.
Теорема Эйлера. В связном графе можно обойти все ребра ровно по одному разу и вернуться в исходную вершину тогда и только тогда, когда все вершины четны. Такой граф называется эйлеровым, а замкнутый путь, содержащий все ребра — эйлеровым циклом.
В связном графе можно обойти все ребра ровно по одному разу, но не вернуться в исходную вершину, тогда и только тогда, когда в нем ровно две вершины нечетны. Такой граф называют полу-эйлеровым, а путь, содержащий все ребра, — эйлеровой цепью. В противном случае обход всех ребер только по одному разу невозможен.
В детских журналах часто публикуют задачи типа «нарисуй, не отрывая карандаша». Если считать, что точки, в которых сходятся несколько линий — это вершины графа, а сами линии — ребра, подобные рисунки можно рассматривать как графы. Эти задачи попадают под действие теоремы Эйлера и решаются с помощью алгоритма Флери.





ОГЛАВЛЕНИЕ
Предисловие.
1. Основные определения и понятия.
2. Способы задания графа.
3. Задачи об обходах графа.
4. Дерево. Минимальное остовное дерево.
5. Фундаментальная система циклов.
6. Построение дерева кратчайших путей.
7. Конденсация и база. Потоки в сетях.
8. Планарность. Вершинная раскраска.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов, метод, указания, Бояринцева Т.И., Мастихина А.А., 2014 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: Бояринцева :: Мастихина :: теория графов :: 2014