Тип работы:
Предмет:
Язык работы:


ГРАФЫ ОТОБРАЖЕНИЙ

Работа №86981
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы26
Год сдачи2017
Стоимость4760 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 7
Не подходит работа?

Узнай цену на написание

Введение 3
1. Ориентированные графы 5
2. Графы отображений 9
3. Связные ориентированные графы 15
4. Связные графы отображений 17
5. Ориентированное дерево 19
6. Конденсация 21
Заключение 25
Список литературы

Выпускная работа посвящена изучению ориентированных графов специального вида —
графов отображения конечного множества в себя.
Вершинами графа отображения f : N Ñ N являются элементы конечного множества N. Графом отображения f называется ориентированный граф, в котором дуга
i Ñ j существует тогда и только тогда, когда fpiq “ j. Графы отображений как частный
тип орграфов полностью характеризуется тем, что из каждой вершины такого графа
выходит ровно одна дуга. Эта особенность влечет за собой ряд интересных свойств, не
имеющих места для ориентированных графов общего вида. Эти свойства и описываются в работе.
Интерес к графам отображения объясняется, с другой стороны, тем, что они представляют собой способ задания отображения множеств, имеющий, в некоторых случаях,
преимущество наглядности сравнительно с другими способами, такими, как табличный
или формульный способы.
В литературе графы отображений встречаются преимущественно в частном виде,
как графы (цикловые структуры) перестановок [1]. Наиболее близкий к нашей теме
литературный источник — книга В.Н. Сачкова "Введение в комбинаторные методы
дискретной математики" см. [2]. В этой книге основным инструментом изучения графов отображений конечного множества в себя (автор называет их преобразованиями
множества), является следующее бинарное отношение: i „ j, если для некоторых показателей k и l имеет место равенство fkpiq “ flpjq: Как видно из определения, оно
пригодно лишь для графов отображений. В нашей работе для изучения графов отображений применяется другое бинарное отношение на множестве вершин — отношение
слабой достижимости и связанные с ним понятия связного ориентированного орграфа
и связной компоненты орграфа общего вида. Эти понятия применимы к любым орграфам и в этом смысле более универсальны. Результатом применения этих понятий к
графам отображений является независимое от книги [2] и более полное описание графов
отображений.
Материал работы расположен в следующем порядке. В §1 излагаются основные понятия, относящиеся к ориентированным графам. Они взяты из пособий Ю.А. Альпин,
С.Н. Ильин "Графы и автоматы"[3]; Ю.А. Альпин "Неотрицательные матрицы"[4] и
учебника [5]. Во §2 определяются графы отображений и доказываются некоторые их
свойства, в частности, описываются свойства матриц смежности графов отображений.
3Основное для нашей работы понятие слабой достижимости, а также определение линии в орграфе приводятся в §3. Здесь же описано понятие связного орграфа, которое
отличается от более распространенного понятия сильно связного орграфа и является
более общим. Центральным в работе является §4, в котором описана структура связного графа отображения. Значение этого описания заключается в том, что произвольный
граф отображения оказывается просто совокупностью связных графов отображений,
между которыми нет соединяющих дуг. Известной упрощенной моделью орграфа, отражающей взаимосвязи между его сильно связными компонентами, является конденсация орграфа. В заключительных §5 и §6 описывается строение конденсации графа
отображения, ключевым в этом описании является понятие ориентированного дерева.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


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


[1] Кострикин, А.И. Введение в алгебру. Основы алгебры. Часть1/ А.И. Кострикин. — М.: Физ.-Мат. лит., 2012. — 272 с.
[2] Сачков В.Н. Введение в комбинаторные методы дискретной математики/ В.Н. Сач¬ков. — 2-е изд., исп. и доп. — М.: МЦНМО, 2004. — 424 с.
[3] Альпин, Ю.А. Дискретная математика: графы и автоматы/ Ю.А. Альпин, С.Н. Ильин. — Казань: КГУ, 2007. — 78 с.
[4] Альпин, Ю.А. Неотрицательные матрицы/ Ю.А. Альпин. — Казань: Казан. ун-т, 2015. — 58 с.
[5] Гладков, Л.А. Дискретная математика/ Л.А. Гладков, В.В. Курейчик, В.М. Курей- чик. — М.: Физ.-Мат. лит., 2014. — 496 с.


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ