Задания для лабораторных работ

Информационные технологии»

Г.н.

для специальности

Математическое обеспечение и

Администрирование информационных систем»

Г.н.

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

Требования к форме и содержанию отчетных материалов.

При выполнении лабораторных работ следует строго придерживаться указанных ниже правил. Работы, выполненные без соблюдения этих правил, не засчитываются и возвращаются студенту для переработки.

1. В работу должны быть включены все требуемые задания строго по положенному варианту. Работы, содержащие задания не своего варианта, не засчитывается.

2. Каждое задание следует оформлять на отдельном листе формата A4. Работа обязательно должна содержать титульный лист принятого образца с обязательным номером варианта.

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

4. Работа сдается преподавателю до защиты для проверки. При повторной сдачи работы сдается первоначальный вариант и исправленные задания.

5. Правильно выполненная работа подлежит защите.

Содержание курса лабораторных работ

Лабораторная работа должна содержать:

1) цель работы

2) краткие теоретические сведения по соответствующему разделу теории графов

3) аналитическое (ручное) решение примера

4) исходный код программы и результаты работы программы (в некоторых заданиях может отсутствовать).

5) вывод

6) список использованной литературы

Задания для лабораторных работ.

Лабораторная работа 1. Основные понятия теории графов

Задание 1. Какие из трех указанных графов являются изоморфными, а какие – неизоморфными? Для изоморфных графов указать соответствие вершин, сохраняющее смежность. Для неизоморфных графов пояснить причину этого. (Приложение 1).

Задание 2. Даны графы и . Построить графы: . Для графа найти матрицы смежности и инцидентности. (Приложение 2).

Задание 3. По заданной матрице смежности определить число циклов длины 3 и длины 4. (Приложение 3).

Задание 4. Дан орграф порядка 5. Сколько в нем путей длины 3. (Приложение 4).

Лабораторная работа 2. Связность в графах

Задание 1. Для неориентированного графа найти точки сочленения и мосты, выделить блоки графа, определить метрические характеристики графа и построить реберный граф. (Приложение 5).

Задание 2. Для ориентированного графа, указать компоненты сильной связности, получить конденсацию графа, найти матрицы достижимости и контрдостижимости. (Приложение 6).

Лабораторная работа 3. Остовное дерево в графе.

Задание 1. Для графа G, заданного матрицей весов, построить минимальный по весу остов и найти его вес, используя алгоритм Крускала. (Приложение 7).

Задание 2. Для графа G, заданного матрицей весов, построить минимальный по весу остов и найти его вес, используя алгоритм Прима. (Приложение 7).

Задание 3. Вычислить число остовных деревьев в графе. (Приложение 7).

Лабораторная работа 4. Эйлеровы и гамильтоновы графы.

Метрические характеристики графов.

Задание 1. По алгоритму Флёри найти эйлеровы циклы на графах. (Приложение 8).

Задание 2. Найти все гамильтоновы циклы графа. (Приложение 9).

Задание 3. Найти матрицы фундаментальных циклов и фундаментальных разрезов. Найти радиус, диаметр и центр графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным? (Приложение 10).

Лабораторная работа 5. Задача о кратчайшем пути.

Задание 1. Для заданного графа найти кратчайший путь от вершины 1 к вершине 12 по алгоритму Дейкстры. (Приложение 11).

Задание 2. Для заданного графа найти кратчайший путь от вершины 1 к вершине 12 по алгоритму Форда-Беллмана. (Приложение 11).

Задание 3. Для заданного графа найти кратчайшие расстояния между всеми парами вершин в графе по алгоритму Флойда. (Приложение 11).

Лабораторная работа 6. Потоки в сетях.

Задание 1. Задана пропускная способность дуг транспортной сети с началом в вершине 1 и концом в вершине 14. Используя алгоритм Форда-Фалкерсона, найти максимальный поток по сети. (Приложение 12).

Можно программировать на любом языке и использовать различные математические пакеты.

Литература для выполнения лабораторных работ

1. Шапорев, С.Д. Дискретная математика [Текст]: курс лекций и практ. занятий: учеб. пособие для вузов по специальностям 220200 "Автоматизированные системы обработки информации и управления", 071900 "Информационные системы в технике и технологиях" / С.Д. Шапорев. - СПб.: БХВ-Петербург, 2009. - 396 с. (Гриф).

2. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах [Текст]: учеб. пособие / В.Н. Степанов; ОмГТУ. – Омск: Изд-во ОмГТУ, 2010. – 118 с.

3. Использование MATLAB при решении оптимизационных задач на графах [Текст]: метод. указания к практ. работам по дисциплине "Методы оптимизации" / ОмГТУ; сост. Л. А. Денисова. - Омск: Изд-во ОмГТУ, 2007. - 27 с.

4. Типовой расчет по дискретной математике [Текст]: метод. указания / ОмГТУ; сост. В.Н. Степанов. – Омск: Изд-во ОмГТУ, 2010. – 58 с.

Поиск по сайту: