Тема курсовой работы: Курсовая работа по дисциплине: «Дискретная математика» на тему: «Ориентированные графы»

Задание...............................................................................................................................3

1. Ориентированный граф, его составляющие. Теорема Роббинса об ориентируемом
связном графе  ..................................................................................................................4

2. Понятие Эйлерова орграфа. Теорема Эйлера............................................................15

3. Понятие гамильтонова орграфа, турнира.....….........................................................18

4. Теория цепей Маркова ................................................................................................20

Заключение .......................................................................................................................25

Используемая литература................................................................................................26

Ориентированный
граф  G = (V, Е) состоит из множества
вершин V и множества дуг Е. Вершины также называют узлами, а дуги
— ориенти­рованными ребрами. Дуга представима в виде упорядоченной пары
вершин (v, w), где вершина v называется началом, a w
— концом дуги. Дугу (v, w) часто записывают как v → w и изображают в
виде

Говорят также, что
дуга v → w ведет от вершины v к вершине w, а вершина
w смежная с вершиной v.

         Представление
орграфа «списком смежности», по сути, сводится к перечислению всех элементов
множества вершин орграфа V и множества его дуг и петель
(упорядоченных пар вершин)E. Все пары, имеющие общий первый элемент,
объединяются в группы. Затем, построчно, выписывается первый элемент группы,
который отделяется, например, двоеточием и далее списком, через запятую, вторые
элементы пар группы. Это несложно сделать, если все вершины орграфа
пронумерованы. Понятно, что число строк в записи будет совпадать с числом
вершин. Если какая-то вершина не входит ни в какую пару, ни в качестве первого
элемента, ни в качестве второго, то мы в строке соответствующей этой вершине
после двоеточия не пишем ничего. Такие вершины являются частным случаем изолированных вершин
орграфа. Отметим, что представление орграфа списком однозначно при выбранной
нумерации вершин орграфа.

Представление орграфа рисунком более
наглядно. В этом случае различным вершинам орграфа, т.е. элементам
множества V, сопоставляются различные точки пространства или
некоторой поверхности, чаще всего плоскости. Упорядоченным парам вершин, т.е.
элементам множества Е, сопоставляются направленные отрезки прямых или
кривых, соединяющих эти пары вершин и «идущих» из первого элемента пары во
второй, что отмечается «наличием» стрелок на этих отрезках, указывающих
направление. Направленные отрезки (дуги) и придают наглядность связям в
орграфе. Запись орграфа рисунком, даже при выбранной нумерации вершин (кстати,
необязательной для представления орграфа рисунком) неоднозначна и зависит от про