30

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

"Ижевский государственный технический университет"

УТВЕРЖДАЮ

Ректор

______________ И.В. Абрамов

"_____"________________ 200__г.

Методические указания для выполнения расчетно-графической работы

по дисциплине "Дискретная математика и теория графов"

на тему "Исследование графов"

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

220200 Автоматизированные системы обработки информации и управления,

220300 Системы автоматизированного проектирования,

направления 552800 Информатика и вычислительная техника

Форма обучения очная и заочная

Ижевск 2004

Кафедра "Автоматизированные системы обработки информации и управления".

Составитель: Кучина Татьяна Леонидовна, ст. преподаватель каф. АСОИУ.

Методические указания составлены на основании государственного образовательного стандарта высшего профессионального образования и утверждены на заседании кафедры

Протокол от "____" ________________ 200__ г. № ______.

Заведующий кафедрой ____________________ В.Н. Кучуганов

"____" ________________ 200__ г.

СОГЛАСОВАНО:

Председатель учебно-методической комиссии

по специальности ____________________ В.Н. Кучуганов

"____" ________________ 200__ г.

Методические указания предназначены для выполнения курсового проекта по дисциплинам:

- "Моделирование систем", "Моделирование и оптимизация" студентами специальности 220200 Автоматизированные системы обработки информации и управления очного и заочного отделения и студентами направления 552800 Информатика и вычислительная техника (бакалавриат);

- "Модели и методы анализа проектных решений", "Моделирование и оптимизация" студентами специальности 220300 Системы автоматизированного проектирования очного и заочного отделения;

Начальник учебно-инженерного отдела ____________________ А.М. Ефимова

"____" ________________ 200__ г.

СОДЕРЖАНИЕ

1. ЦЕЛЬ РАБОТЫ …………………………………………………………………….. 3

2. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ ………………………………………. 3

3. ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ …………………………………………….. 3

4. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ И ОФОРМЛЕНИЮ ОТЧЕТА ……………. 15

5. ЛИТЕРАТУРА ……………………………………………………………………… 15

ПРИЛОЖЕНИЕ 1. НАПРАВЛЕННЫЕ ГРАФЫ ……………………………….. 16

ПРИЛОЖЕНИЕ 2. ВЛОЖЕНИЕ ГРАФОВ ……………………………………… 18

ПРИЛОЖЕНИЕ 3. ПЛОСКАЯ УКЛАДКА ГРАФА В УЗЛЫ РЕШЕТКИ ……. 21

ПРИЛОЖЕНИЕ 4. РАСКРАСКА ГРАФОВ ……………………………………… 23

ПРИЛОЖЕНИЕ 5. ФОРМА ТИТУЛЬНОГО ЛИСТА …………………………... 29

1. Цель работы

Целью работы является закрепление теоретических знаний и проверка уровня усвоения теории по теме «Графы» путем выполнения практической работы.

2. Задание на выполнение работы

1. Задать произвольный ориентированный (направленный) граф десятого порядка

(с десятью вершинами).

2. По заданному графу построить нижний граф.

3. Для нижнего графа выполнить следующие операции:

   1. Построить матрицу инцидентности;

   2. Построить матрицу смежности;

   3. Найти цикломатическое число;

   4. Построить базисную цикломатическую матрицу;

   5. Построить цикломатическую матрицу;

   6. Определить толщину графа;

   7. Выделить планарные подграфы;

   8. Сделать плоскую укладку выделенных планарных подграфов в узлы прямоугольных решеток;

   9. Раскрасить вершины и ребра графа.

2.4. Определить диаметр ориентированного графа. Найти количество компонент сильной связности.