Введение 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 описывается строение конденсации графа
отображения, ключевым в этом описании является понятие ориентированного дерева.
Купить