Дискретная математика, Часть 3, Элементы теории графов, Петрякова Е.А., Синеговская Т.С., 2009

Дискретная математика, Часть 3, Элементы теории графов, Петрякова Е.А., Синеговская Т.С., 2009.

   В учебном пособии изложены основные вопросы теории графов, соответствующие требованиям к минимуму основной обязательной программы по подготовке дипломированных специалистов. Учебное пособие содержит большое количество подробно разобранных и проиллюстрированных примеров разного уровня сложности.
Пособие предназначено для студентов специальностей «Программное обеспечение вычислительной техники и автоматизированных систем» (230105), «Комплексное обеспечение информационной безопасности автоматизированных систем» (090105), «Информационные системы и технологии» (230201) дневной формы обучения, но может быть использовано студентами других специальностей, изучающих соответствующие разделы дискретной математики.




ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.
Теория графов - область дискретной математики, особенностью которой является графическая интерпретация при изучении свойств конечных множеств с заданными отношениями между ними.

Первой работой теории графов как математической дисциплины считают статью Эйлера, написанную в 1736 году, в которой рассматривалась задача о Кёнигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Долгое время этот результат оставался единственным результатом теории графов. Следующий импульс теория графов получила лишь в середине XIX века с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое дерево, которое также является графом.

СОДЕРЖАНИЕ.
Введение.
Основные обозначения.
4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.
4.1. Основные понятия теории графов. Виды графов.
4.1.1. Графы: основные определения.
4.1.2. Степени вершин графов.
4.1.3. Виды графов.
Упражнения.
4.2. Способы задания графов.
4.2.1. Матрица смежности.
4.2.2. Матрица инцидентности.
4.2.3. Списки.
4.2.4. Изоморфизм графов.
4.2.5. Графы и бинарные отношения.
Упражнения.
4.3. Операции над графами.
4.3.1. Подграфы.
4.3.2. Операция удаления ребра.
4.3.3. Операция удаления вершины.
4.3.4. Операция введения ребра.
4.3.5. Операция введения вершины в ребро.
4.3.6. Операция объединения графов.
4.3.7. Операция пересечения графов.
4.3.8. Операция произведения графов.
4.3.9. Операция соединения графов.
4.3.10. Операция отождествления вершин.
4.3.11. Операция стягивания ребра.
Упражнения.
4.4. Связные графы.
4.4.1. Маршруты, цепи, циклы.
4.4.2. Связные графы.
4.4.3. Метрические характеристики связных графов.
4.4.4. Эйлеровы графы.
4.4.5. Гамильтоновы графы.
Упражнения.
4.5. Двудольные и планарные графы.
4.5.1. Свойства двудольных графов.
4.5.2. Плоские графы.
4.5.3. Планарные графы. Плоская укладка.
4.5.4. Гомеоморфизм графов.
4.5.5. Критерий планарности графа.
4.5.6. Характеристики непланарных графов.
Упражнения.
4.6. Раскраски графов. Независимость и покрытия.
4.6.1. Правильная раскраска.
4.6.2. Раскраска ребер.
4.6.3. Раскраска планарных графов. Гипотеза четырех красок.
4.6.4. Покрытия. Независимые множества.
Упражнения.
4.7. Деревья.
4.7.1. Неориентированные деревья. Свойства деревьев.
4.7.2. Остовное дерево.
4.7.3. Центр дерева.
4.7.4. Ориентированные деревья.
Упражнения.
4.8. Взвешенные графы.
4.8.1. Определение взвешенного графа.
4.8.2. Задача построения минимального остовного дерева.
4.8.3. Задача нахождения кратчайшего пути.
4.8.4. Задача коммивояжера.
Упражнения.
Ответы к упражнениям.
Библиографический список.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Дискретная математика, Часть 3, Элементы теории графов, Петрякова Е.А., Синеговская Т.С., 2009 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Петрякова :: Синеговская