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


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

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

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

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



ОГЛАВЛЕНИЕ

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



Бесплатно скачать электронную книгу в удобном формате и читать:

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

Скачать




Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 


Книги, учебники, обучение по разделам




Не нашёл? Найди:





2016-12-05 22:58:00