ИЖЕВСК 2007

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

НОУ «КАМСКИЙ ИНСТИТУТ ГУМАНИТАРНЫХ И ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ»

КАФЕДРА «ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ И ЗАЩИТА ИНОФОРМАЦИИ»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ДЛЯ ВЫПОЛНЕНИЯ КОНТРОЛЬНЫХ РАБОТ

ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»

ИЖЕВСК 2007

УДК 519.1.075

Рецензент: к.ф.-м.н., доцент кафедры Математического анализа УдГУ, Ирисов А.Е.

Рассмотрено на заседании кафедры и рекомендовано к изданию

Протокол №______ от ______________________

Зав. кафедрой ___________________________________

Составитель: к.т.н. А.В. Коробейников

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

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

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

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

Предназначены для студентов специальности 230105 – «Программное обеспечение ВТ и АС», изучающих дисциплину «Дискретная математика».

Ил. 6. Табл. 31. Библиограф.: 2 назв.

©Коробейников А. В.

©НОУ «Камский институт гуманитарных и инженерных технологий»

ВВЕДЕНИЕ

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

Дискретная математика изучает дискретные или конечные множества и различные структуры на них. Это значит что понятия бесконечности, предела и непрерывности не являются её предметом изучения.

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

Дискретная математика стала активно развиваться с начала ХХ века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Это результаты Поста, Клини, Гёделя. Тесно связаны с математической логикой исследования начала ХХ века в области теории алгоритмов Тьюринга, Поста и Чёрча. Информатизация и компьютеризация во второй половине ХХ века в значительной степени стимулировали развитие дискретной математики.

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

1. КОНТРОЛЬНАЯ РАБОТА «ИССЛЕДОВАНИЕ ГРАФОВ»

1.1. ЦЕЛЬ РАБОТЫ

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

1.2. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

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

а) построить диаграмму графа;

б) определить является ли граф мульти-графом или псевдо-графом;

в) построить матрицу инцидентности;

г) построить матрицу смежности;

д) определить максимальную и минимальную степени вершин;

е) определить диаметр и радиус графа;

ж) найти множество центральных вершин;

з) определить число компонент связности графа;

и) определить наличие точек сочленения и мостов в графе;

к) определить вершинную и реберную связность графа;

л) найти цикломатическое число;

м) построить базисную цикломатическую матрицу;

н) построить цикломатическую матрицу (15-20 циклов);

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

п) выделить планарные подграфы;

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

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

а) построить диаграмму графа;

б) построить матрицу инцидентности;

в) построить матрицу смежности;

г) определить максимальную и минимальную полу-степени вершин;

д) определить является ли граф сильно-, односторонне- или слабо- связным;

е) найти компоненты сильной связности графа;

ж) построить конденсацию графа.

1.3. ВАРИАНТЫ ЗАДАНИЙ

Задан ориентированный (направленный) граф, состоящий из 10 вершин и 17…20 ребер. Для каждого варианта приведена таблица, содержащая функции инцидентности ребер.

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

Вариант 23. Задан ориентированный граф G .

Вершины V={V1, V2, … , Vn}, n=10 (табл. 1).

Ребра E={E1, E2, … , Em}, m=17 (табл. 2, V- – вершина начальная, V+ – вершина конечная).

Таблица 1.

Таблица 2.

1) Исследование неориентированного графа.

Ребра Ei без учета направлений (табл. 3).

Таблица 3.

а) Диаграмма неорграфа приведена на рис. 1.

Рис. 1. Диаграмма неорграфа.

б) Граф является мульти-графом: Одинаковые ребра. Граф является псевдо-графом: есть ребра инцидентные только одной вершине.

в) (табл. 4).

Таблица 4.

г) Матрица смежности вершин (табл. 5).

Таблица 5.

д) Матрица степеней вершин (сумма столбцов матрицы смежности) s(Vi) (табл. 6).

max(s(Vi))=s(V7)=6; min(s(Vi))=s(V10)=1.

Таблица 6.

е) Диаметр и радиус графа.

Матрица расстояний между вершинами d(Vi,Vj) (табл. 7).

Диаметр D(G)=max(d(Vi,Vj))=3.

Матрица эксцентриситетов e(Vi)=max(d(Vi,Vj) при фиксированном i (табл. 8).

Радиус R(G)=min(e(Vi))=2.

Таблица 7.

Таблица 8.

ж) Множество центральных вершин: {V1, V2, V5, V7}, т.к. для них выполняется равенство e(Vi)=R(G).

з) Число компонент связности (число связных подграфов):

k(G)=1.

и) Точки сочленения: {V7}. Мосты: {E4}. При их удалении увеличивается число компонент связности графа.

к) Вершинная связность графа равна 1. Реберная связность графа равна 1. Т.к. при удалении одной вершины (V7) или ребра (E4) увеличивается число компонент связности графа.

Рис. 2. Остов графа.

л) Цикломатическое число ν(G) равно числу хорд любого остова (рис. 2) графа G, если связный граф имеет n вершин и m ребер: v(G)=m–n+1. Если граф G содержит k компонент связности, то его цикломатическое число: ν(G)=m–n+k.

Данный граф содержит одну компоненту связности, ν(G)=17–10+1=8, т.е. в графе содержится 8 базисных циклов.

Таблица 9.

Таблица 10.

м) Базисная цикломатическая матрица (табл. 9). R1…R8 – базисные циклы.

н) Цикломатическая матрица (R1…R8 – базисные циклы) (табл. 10). И так далее, всего циклов (2^ν–ν–1)=(2⁸–8–1)=247 (комбинаций базисных циклов). Каждый цикл получен выполнением операции XOR (сложение по модулю 2) между ребрами базисных циклов.

о) Толщиной графа G называется наименьшее число планарных графов, объединение которых дает граф G. Толщина пл