Студенческий портал

admin@studynote.ru
/ Регистрация
X
Помощь студенту > Готовые работы > Курсовые работы > Курсовые работы по высшей математике > Курсовая работа по дисциплине: «Дискретная математика» на тему: «Ориентированные графы»

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

250 рублей
Купить

или

Заказать новую работу

Более 20 способов оплатить! После оплаты вы получаете ссылку на скачивание. Гарантия на - 3 дня. Исключительно в ознакомительных целях! Все вопросы admin@studynote.ru

  • Общая информация
  • Описание работы
  • Дополнительная информация

    (фрагменты работы)

Учебное заведение: Другие города > Вузы города Пермь > Пермский государственный технический университет
Тип работы: Курсовые работы
Категория: Высшая математика
Год сдачи: 2015
Количество страниц: 26
Оценка: 4
Рейтинг работы:

Задание...............................................................................................................................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, сопоставляются различные точки пространства или
некоторой поверхности, чаще всего плоскости. Упорядоченным парам вершин, т.е.
элементам множества Е, сопоставляются направленные отрезки прямых или
кривых, соединяющих эти пары вершин и «идущих» из первого элемента пары во
второй, что отмечается «наличием» стрелок на этих отрезках, указывающих
направление. Направленные отрезки (дуги) и придают наглядность связям в
орграфе. Запись орграфа рисунком, даже при выбранной нумерации вершин (кстати,
необязательной для представления орграфа рисунком) неоднозначна и зависит от про