Лабораторная работа №2

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ

ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АНАЛИЗ ГРАФОВ НА ЭВМ

 

Методические указания к выполнению лабораторных работ по курсу "Дискретная математика"

 

 

ПЕНЗА 2004

УДК 519.17

А 64

Приведены сведения об основных понятиях и терминологии теории графов, необходимые для выполнения цикла лабораторных работ. Темы лабораторных работ связаны с исследованием унарных и бинарных операция над графами, анализом метрических свойств, связности, независимости, паросочетаний, покрытий и циклов неориентированных и ориентированных графов с применением ЭВМ. Указан порядок выполнения лабораторных работ, даны темы заданий и ссылки на известные алгоритмы анализа графов, изложены требования к содержанию отчета.

Методические указания "подготовлены на кафедре "Вычислительная техника" и предназначены для студентов специальности 22.01.00, изучающих курс "Дискретная математика".

Ил. 11, табл. 2, библиогр. 14 назв.

Составители: П.П. Макарычев, Д.В. Пащенко

Под ред. д-ра техн.наук, профессора Н.П. Вашкевича

Р е ц е н з е н т: С.А. Зинкин, канд. техн. наук

Введение

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

На практике, при проектировании сложных технических систем, важно уметь построить модели этих систем в виде графов, а затем вычислить их характеристики, такие, как наибольшее паросочетание, наибольшее независимое множество вершин и ребер, остовное дерево и т, д. Таким образом, для решения практических задач проектирования и исследования технических систем надо иметь соответствующие алгоритмы, в конечном счете, программы для ЭВМ.

Основной задачей проведения лабораторных работ по курсу "Дискретная математика" является закрепление знаний по основам теории графов, приобретение практических навыков решения прикладных задач и построение эффективных алгоритмов для автоматизации математических расчетов.

В данных лабораторных работах в качестве инструмента для таких вычислений студентам предлагается система MathCAD, которая содержит текстовый редактор, мощный вычислитель и графический процессор. Язык общения с пользователем в системе MathCAD идеально приближен к обычному математическому языку. Поэтому центр тяжести расчетов перемещается с вопросов программирования на естественное математическое описание алгоритмов. Сведения по расширению функциональных возможностей MathCAD с использованием динамически подключаемых библиотек, приведены в приложении.

Лабораторная работа № 1

МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ И ХАРАКТЕРИСТИКИ ГРАФОВ

Цель работы - изучение форм представления графов на основе матриц и вычисление их характеристик на ЭВМ.

Основные понятия и определения

Пусть G - связный помеченный граф, содержащий непустое множество вершин V и множество ребер U

.

Вершинам графа присвоены метки из подмножества натуральных чисел {1,2,…}. Выделим в графе G две несовпадающие вершины v_i; и v_j . Длина кратчайшего маршрута (простой цепи) между v_i; и v_j называется расстоянием между вершинами и обозначается через l ( v_i ; v_j ). Для фиксированной вершины v_i; величина

называется эксцентриситетом вершины v_i.

Максимальный среди всех эксцентриситетов эксцентриситет вершины называется диаметром графа G и обозначается через D ( G ).

Следовательно, вершина v_i называется периферийной, если e ( v_i ) = d ( G ). Простая цепь длины d ( G ) называется диаметральной цепью.

Минимальный из эксцентриситетов вершин связного графа G называется его радиусом и обозначается через r ( G ). Вычисление значения радиуса осуществляется по формуле

Вершина v_i называется центральной, если e ( v_i ) = r ( G ). Множество всех центральных вершин графа называется его центром. Граф G может иметь единственную центральную вершину или несколько центральных вершин.

Степенью вершины графа G называется число инцидентных ей ребер. Степень вершины v_i: обозначается через deg ( v_i ). Максимальная и минимальная степени вершиy графа G обозначаются символами Δ( G ), δ( G ) соответственно:

 

.

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

Лабораторное задание

1. Осуществите генерацию матрицы смежности M( G) неориентированного графа G,

 

 

где n - порядок помеченного графа.

2. Определите радиус и диаметр графа G, используя матрицу смежности графа M( G) и алгоритм вычисления эксцентриситета вершины.

3. Определите подмножества периферийных и центральных вершин графа G, используя матрицу смежности M( G)

4. Определите список степеней вершин графа, изолированные, концевые и доминирующие вершины.

5. Постройте для графа G матрицу инцидентности A( G). Выполните п.4, используя представление графа и форме матрицы инцидентности.

6. Постройте для графа G матрицу Кирхгофа B( G).

Содержание отчета

Протокол решения задач по всем пунктам лабораторного задания средствами системы MathCAD.

Контрольные вопросы

1. Чему равна сумма степеней всех вершин графа?

2. Докажите, что матрица смежности и матрица Кирхгофа для графа без петель связаны соотношением

3. B_i,j = I_i,j^.M²_i,j(G) - M_i,j(G)

4. где I — единичная матрица.

5. Покажите на примерах, что расстояние между вершинами l( v_i, v_j) удовлетворяет следующим аксиомам метрики:

a) l(v_i,v_j) >= 0;

б) l ( v_i , v_j ) = 0, тогда и только тогда, когда v_i = v_j ;

в) l ( v_i , v_j ) = l ( v_j , v_i )

г) l ( v_i , v_k ) + l ( v_k , v_j ) >= l ( v_i , v_j ) (неравенство треугольника).

7. Пусть G — граф, множество вершин которого совпадает с отрезком натурального ряда {1,2,...5}, а множество ребер определяется следующим условием: несовпадающие вершины v_i, и v_j смежны тогда, когда числа i и j взаимно просты. Какой вид имеют:

— матрица смежности графа G;

— матрица инциденций G ;

— матрица Кирхгофа графа G.

Лабораторная работа №2