Основы дискретной математики

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ УКРАЇНИ

ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ТЕХНІЧНОЇ КІБЕРНЕТИКИ

 

 

 

 

 

Курсова робота

з дисципліни «Основи дискретної математики»

 

 

Варіант № 2

 

 

 

 

 

 

 

Виконав

студент групи 2СУ  _______________  Борохович И.И.

Керівник

Проф.    _______________  Марасанов В.В.

 

 

 

Херсон 2011

 

РЕФЕРАТ

Курсовая  работа содержит __ страниц, __ рисунков, __ таблиц.

В работе выполнены:

1) формализованное  описание графа с помощью таблицы,  фактор – множества, матриц  инциденции, смежности вершин, циклов, разрезов и путей; 

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

3) решена задача  на самый короткий путь;

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

5) анализ функции  на принадлежность к классам; 

6) минимизация  логической функции методом Квайна-МакКласски  или с помощью карт Карно;

7) синтез логической  схемы методом каскадов и реализация  её в базисе и-или-не с использованием  двухвходовых элементов.

НЕОРИЕНТИРОВАНЫЙ  ГРАФ, ИНЦИДЕНТНОСТЬ, ФАКТОР МНОЖЕСТВА,  ФУНКЦИЯ АЛГЕБРЫ ЛОГИКИ, ТАБЛИЦА  ИСТИННОСТИ,  МИНИМИЗАЦИЯ,  МЕТОД  КАСКАДОВ.

 

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ  И СОКРАЩЕНИЙ

ДМ – дискретная математика

CДНФ – совершенная дизъюнктивная нормальная форма

CКНФ – совершенная конъюнктивная нормальная форма

МДНФ – минимальная дизъюнктивная нормальная форма

ФАЛ – функция  алгебры логики

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

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

Дискретная  математика – самостоятельное направление  современной математики. Она изучает  математические модели объектов, процессов, зависимостей, существующих в реальном мире, с которыми имеют дело в  технике, информатике и других областях знаний.

Сегодня ДМ является важным звеном математического образования. Знание дискретной математики необходимо для создания и эксплуатации интегрированных  систем обработки информации и их компонент (математического обеспечения, пакетов прикладных программ, распределенных банков данных, сетей передачи данных, систем с разделением ресурсов и  распределенной обработкой информации).

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

Еще в доньютоновский период появились простейшие понятия  комбинаторики (П.Ферма, Б.Паскаль, Франция, XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр.

Л.Эйлер в  середине XVIII века закладывает основы теории графов; в середине XIХ века Дж.Буль, опираясь на некоторые идеи Г.Лейбница, придумывает свою «универсальную алгебру» в продолжение наметившегося еще в середине века стремления к формализации Аристотелевой логики. Конец XIХ века дает толчок к созданию и быстрому расцвету математической логики.

Основным  поставщиком задач и идей для  ДМ в ХХ веке становится кибернетика, а универсальным вычислительным средством – ЭВМ. Задачи анализа  и конструирования сложных систем послужили стимулом для разработки теории графов; задачи хранения, обработки  и передачи информации привели к  теории кодирования; задачи оптимизации  вызвали появление дискретного  программирования; исследование основных понятий вычислительной математики – вычислимости и алгоритма –  стимулировало появление теории алгоритмов и теории сложности.

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

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

 

1. ЗАДАЧИ ТЕОРИИ ГРАФОВ

 

Графами называют геометрические схемы, представляющие собой системы точек и соединительных линий. Учение о графах соединяет  исключительную геометрическую наглядность, математическую содержательность и  возможность обходиться без громоздкого  аппарата. [1]

Геометрический  граф в пространстве jⁿ (Евклидово пространство) – это множество V={v_i} точек  пространства jⁿ и множество Е={e_k} простых кривых удовлетворяющих следующим условиям.

1)Каждая  замкнутая  прямая из множества Е содержит  только одну точку v множества V;

2)Каждая незамкнутая  прямая из множества Е содержит  только 2 точки v из множества V, которые являются ее границами.

3)Кривые Е  не имеют общих точек за  исключением точек из множества  V

Граф –  это совокупность не пустого множества  V, изолированного от него множества Е и отображения f: Е~V&V.

Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным [2].

1.1.   Формализованное  задание графа

Граф задается на множестве вершин V и множестве ребер Е. Наиболее простое описание графа – составление таблицы соответствия ребер и вершин.

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

 

Рис. 1.1 – Исходный граф G для варианта №2

1.1.1 Описание графа с помощью таблицы

Данное описание графа представлено таблицей 1.1 соответствия множества вершин и множества  ребер графа

Табл.1.1

E	e1	e2	e3	e4	e5	e6	e7	e8	e9
V	v1, v2	v1, v3	v3, v2	v2, v4	v3, v4	v3, v5	v5, v4	v4, v6	v5, v6

1.1.2  Описание графа с помощью фактор – множества

1.1.3  Описание графа с помощью матриц

Матрица инциденций для графа G, имеющего n вершин и m ребер  имеет размерность n x m. Строки этой матрицы соответствуют вершинам, а столбцы – ребрам графа. Элемент  а_ij=1, если j-ое ребро инцидентно i-ой вершине и а_ij=0 в противном случае.

Для графа  на рис.1.1 матрица инциденций имеет  вид:

 

 

Матрица смежности  вершин для графа G, имеющего n вершин имеет размерность n x n. Элемент v_ij этой матрицы равен числу ребер, инцидентных одновременно i-ой и j-ой вершинам графа.

Для графа  на рис.1.1 матрица смежности вершин имеет вид:

 

Матрица циклов для графа G, имеющего n вершин и m ребер, имеет размерность к x m, где к – число циклов в графе. Элемент этой матрицы с_ij=1, если j-ое ребро входит в i-ый цикл и с_ij=0 в противном случае. Циклы в заданном графе представлены на рисунке 1.2.

Рис. 1.2 – Циклы графа G.

Для графа на рис.1.2 матрица циклов имеет  вид:

 

 

Если  задан связный граф G=(V, E) и множество его вершин разбито на два непустых подмножества W и W^/, то множество ребер, соединяющих W с W^/ называют разрезом. Простым называют разрез, разбивающий связный граф только на две компоненты связности.

С использованием простых разрезов можно построить  матрицу разрезов графа. Для графа  G, имеющего n вершин и m ребер, матрица разрезов имеет размерность l x m, где l – число разрезов на графе. Элемент этой матрицы к_ij=1, если j-ое ребро входит в i-ый разрез и к_ij=0 в противном случае. Простые разрезы для графа G изображены на рисунке 1.3.

Рис. 1.3 – Разрезы графа G

Для графа на рис.1.3 матрица разрезов имеет вид:

 

 

Выбрав в  связном графе начальную (v₁) и конечную (v₂) вершину, для него можно составить матрицу путей (матрицу цепей). Строки этой матрицы соответствуют цепям между вершинами v₁ и v₂, а столбцы соответствуют ребрам графа. Элемент матрицы р_ij=1, если j-ое ребро принадлежит i-ой цепи и р_ij=0 в противном случае.

Для графа  на рис.1.1 матрица путей из вершины 1 в вершину 6 имеет вид:

1.2.   Числовые характеристики графа

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

1.2.1 Степени всех вершин графа

Число ребер  неориентированного графа инцидентных  вершине v, называется степенью вершины v и обозначается d(v).

Степени всех вершин графа, изображенного на рис.1.1:

;

;

;

;

;

.

Минимальная степень вершины 

1.2.2 Вершинная  и реберная связность графа

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

Вершинная и  реберная связность графа на рис.1.1:

 (вершины v₃, v₄ или v₂, v₃ или v₅, и v₄).

 (ребра e₁, e₂, или e₈, e₉).

1.2.3 Цикломатическое число графа

Пусть G=(V, E) – неориентированный граф, имеющий n вершин, m ребер и r компонент связности. Цикломатическим числом графа G называют число n(G)=m – n + r. Цикломатическое число равно наибольшему числу независимых циклов в графе.

Цикломатическое число графа на рис.1.1:

(из 10 контуров 4 независимые).

1.2.4 Хроматическое число

Пусть p – натуральное число. Граф G = (V, E) называют p-хроматическим, если его вершины можно раскрасить p разными цветами, так, чтобы никакие две смежные вершины не были раскрашены в тот же цвет. Наименьшее число p, при котором граф является р – хроматическим, называют хроматическим числом графа (обозначается . Если , граф называют бихроматическим. Необходимым и достаточным условием бихроматичности графа является отсутствие в нем циклов непарной длины (теорема Кенига).

(, т.к. цикл охватывает 3 ребра (3 вершины)).

1.2.5 Вершинное и реберное числа независимости

Множество S V графа G = (V, Г) называют внутренне устойчивым, если никакие две вершины из S не смежные, т.е. для любого х S имеет место Гх S¹Æ.

Множество внутренней устойчивости, содержащее наибольшее число элементов, называют наибольшим внутренне устойчивым множеством, а число элементов этого множества – числом внутренней устойчивости e₀(G) графа G (это число называют также вершинным числом независимости графа).

Два ребра  графа называют смежными, если они  инцидентны одной и той же вершине. Максимальное число попарно несмежных  ребер графа называется его реберным числом независимости e₁(G).

Вершинное и  реберное числа независимости графа  на рис.1.1:

(вершины v₁ и v₅; v₁ и v₄; v₂ и v₆; v₂ и v₅; v₁ и v₆).

(ребра e₁, e₆, e₈ или e₂, e₄, e₉ или e₁, e₅, e₉).

1.2.6 Числа вершинного и реберного покрытий графа

Если ребро  графа инцидентно его вершине, то говорят, что они покрывают друг друга. Множество вершин, покрывающих  все ребра графа, называют вершинным  покрытием графа G, а минимальную мощность этого множества - числом вершинного покрытия графа p₀(G).

Аналогично, множество ребер, покрывающих все  вершины графа, называют реберным покрытием  графа G, а минимальную мощность этого множества – числом реберного покрытия графа p₁(G).