АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ВВЕДЕНИЕ. Составители: Н.И. Житникова, Г.И

Составители: Н.И. Житникова, Г.И. Федорова, А.К. Галимов

УДК 519.6 (07)

ББК 22.193 (я7)

Теория графов: Практикум по дисциплине «Дискретная математика». /Уфимск. гос. авиац. техн. ун-т; Сост. Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005. - 39 с.

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

Ил. 15. Библиогр.: 8 назв.

Рецензенты: Бронштейн Е.М.

Хабибуллин Б.Н.

© Уфимский государственный

авиационный технический университет, 2005

Содержание

Введение 4

1. Краткий перечень основных понятий теории графов 5

1.1. Общие понятия 5

1.2. Понятия смежности, инцидентности, степени 7

1.3. Маршруты и пути 7

1.4. Матрицы смежности и инцидентности 8

1.5. Связность. Компоненты связности 9

1.6. Матрицы достижимости и связности 9

1.7. Расстояния в графе 10

1.8. Образ и прообраз вершины и множества вершин 10

1.9. Нагруженные графы 11

1.10. Деревья и циклы 12

2. Решение контрольных задач 13

2.1. Компоненты сильной связности ориентированного графа 13

2.2. Расстояния в ориентированном графе 16

2.3. Минимальный путь в нагруженном ориентированном графе 20

2.4. Эйлеровы циклы и цепи 23

2.5. Минимальное остовное дерево 25

2. 6. Задача о коммивояжёре 27

3. Задания для самостоятельного решения 35

Список литературы 38

ВВЕДЕНИЕ

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

Задачи на графах удобно переводить на языки программирования, то есть решать с использованием современной вычислительной техники.

Умение решать задачи на графах позволит будущему специалисту приобрести опыт разработки технологий и методов теории операций для решения задач при научных исследованиях и проектно-конструкторской деятельности

В данном практикуме рассмотрены основные типы задач на графах, подходы и методы их решения, конкретные примеры.

Цель раздела «Теория графов» состоит в формировании у студентов умений и навыков, необходимых при исследовании различных систем и проектировании технических объектов.

Для достижения указанной цели решаются следующие задачи:

- формирование знаний методов и алгоритмов эффективного решения задач дискретной оптимизации;

- формирование умений и навыков использования изученных методов для решения типовых задач математического моделирования и оценки пределов применимости полученных результатов.

Дата добавления: 2015-09-27 | Просмотры: 447 | Нарушение авторских прав