Файл: Ориентированные графы.docx

МИНИСТЕРСТВО НАУКИ И Высшего ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГАОУ ВО «СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Факультет математики и компьютерных наук имени профессора Н.И. Червякова

КАФЕДРА вычислительной математики и кибернетики


КУРСОВАЯ РАБОТА
по дисциплине

«Дискретная математика»

на тему:

«Ориентированные графы»
Выполнил:

Зебольд Даниил Александрович

студент 2 курса

группы ПМИ-б-о-21-1

направления 01.03.02 – Прикладная математика и информатика

Направленность (профиль) Вычислительная математика и математическое моделирование

очной формы обучения

________________________

(подпись)
Руководитель работы:

Самойленко В.В.

доцент кафедры Вычислительной математики и кибернетики

Работа допущена к защите _______________________ ______________

(подпись руководителя) (дата)
Работа выполнена и

защищена с оценкой _________________________ Дата защиты______________
Члены комиссии: ________________ __________ _______________

(должность) (подпись) (И.О. Фамилия)

________________ _______________ _______________

(должность) (подпись) (И.О. Фамилия)

________________ _______________ _______________

(должность) (подпись) (И.О. Фамилия)
Ставрополь, 2022 г.

Содержание
Введение 3

1. Ориентированные графы 4

1.1 Основные определения 4

1.2 Полустепени исхода и полустепени захода 8

1.3 Пути 11

2. Описание алгоритма 15

3. Описание программы 17

3.1. Общие сведения 17

3.2. Функциональное назначение 17

3.3. Описание логической структуры программы 17

3.4. Использование технических средств 18

3.5. Описание данных 18

3.6. Руководство пользователю 18

3.7. Структурная схема программы 19

Заключение 20

Список литературы 21

Введение

В настоящее время дискретная математика и смежные с ней разделы привлекают большое внимание специалистов различных областей науки и техники, являясь эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании, и т.д. Обширное применение теория графов находит в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ, баз данных, систем логического управления.

---

В приложениях часто приходится рассматривать гра­фы с ориентированными ребрами, т. е. ребрами, для ко­торых указаны начало и конец. Примерами таких графов являются сети автомобильных дорог с односторонним дви­жением или схемы программ для ЭВМ. Недостаточно простых (неориентированных) графов и для описания несимметричных отношений. Примерами подобных отно­шений могут служить порядок выполнения комплекса ра­бот, задаваемый с помощью сетевого графика, или тур­нирная ситуация в спортивных соревнованиях.

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

1. Ориентированные графы

1.1 Основные определения

Пусть V — конечное непустое множество, V² — его де­картов квадрат. Ориентированный граф (орграф)—это па­ра (V, А), где A  V². Элементы множества V называют­ся вершинами орграфа G=(V, А), а элементы множества А — его дугами. Таким образом, дуга — это упорядочен­ная пара вершин. Множества вершин и дуг орграфа G обозначаются через VG и AG соответственно. Число |VG| называется порядком орграфа G и обозначается через |G|.

Если х = (u, v) — дуга, то вершины u и v называются ее концевыми вершинами, причем u называется началом дуги х, а. v — концом. Говорят, что дуга инцидентна каж­дой из своих концевых вершин. Говорят также, что дуга исходит из своего начала и заходит в свой конец. Дуга с совпадающими началом и концом, т. е. дуга вида (v, v), называется петлей. Можно определить ориентированные графы с несколькими дугами, имеющими общее начало и общий конец (мультиграфы). Такие дуги называются параллельными.

На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Направление линии обозначается стрелкой. Например, для графа G, представленного на рис. 1, VG={v₁, v₂, v₃, v₄, v₅}, AG= {x₁, x₂, x₃, x₄, x₅, x₆, x₇}, причем x₁ и x₂ —параллель­ные дуги, a x₇ — петля.

Вершины орграфа называются смежными, если они являются концевыми для некоторой дуги. Дуги называ­ются смежными, если они имеют общую концевую вершину.

Пусть G— некоторый орграф. Ориентированным марш­рутом (или просто маршрутом) в графе G называется такая последовательность

---

S = (v₀, x₁, v₁, x₂, v₂, x₃, v₃, x₄,.., v_n, x_n,) (1)

его чередующихся вершин v_i и дуг х_j, что x_i = (v_i-1, v_i) (i = 1, n). Такой маршрут назо­вем (v₀, v_n) – маршрутом. Вер­шины v₀ и v_n назовем крайни­ми, а остальные вершины маршрута (1) — промежуточны­ми (внутренними). Длиной маршрута называется число входящих в пего дуг. Маршрут называется цепью, если все входящие в пего дуги различны, и путем, если все входящие в него вершины, кроме, возможно, крайних, различны.

Если в орграфе G нет параллельных дуг, то маршрут (1) может быть задан последовательностью входящих в него вершин: S=( v₀, v₁, v₂, v₃,.., v_n). В любом случае марш­рут можно задать последовательностью входящих в него дуг: S = (x₁, x₂, x₃, x₄,.., x_n,)

Рис. 1.
Маршрут называется циклическим, если его первая и последняя вершины совпадают. Циклический путь назы­вается контуром. Очевидно, что любой (u, v) – маршрут при u  v содержит (u, v)-путь, а при u = v — контур.

Последовательность (1) чередующихся вершин и дуг орграфа G, таких что x_i = (v_i-1, v_i) или x_i = (v_i, v_i-1), на­зывается полумаршрутом. Аналогично определяются по­луцепь, полупуть и полуконтур.

Если в орграфе существует (u, v) -маршрут, то гово­рят, что вершина v достижима из вершины u. Любая вер­шина считается достижимой из себя самой.

Орграф называется сильным (или силъносвязным), если любые две его вершины достижимы друг из друга. Орграф называется односторонним (или односторонне-связным), если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется сла­бым (слабосвязным, связным), если любые две его вер­шины соединены полупутем.

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

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

На рис. 2, а изображен сильный орграф, на рис. 2, б — односторонний, а на рис. 2, в — слабый.

Рис. 2.
Маршрут, содержащий все вершины орграфа G, на­зывается остовным.

Утверждение 1. Орграф является сильным тогда и только тогда, когда в нем есть остовный цикличе­ский маршрут.

 Необходимость. Пусть G — сильный орграф и T = (v₀, x₁, v₁, x₂, v₂,.., x_n,

---

v₀)—его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G — сильный орграф, то сущест­вуют маршруты

T₁ = (v₀, y₁, .., v), T₂ = (v₀, z₁, .., v₀)

Но тогда циклический маршрут

T’ = (v₀, x₁, v₁, .., x_n, v₀, y₁, .., v, .., z₁, v₀)

содержит большее, чем Т, число вершин, что противоре­чит выбору маршрута Т. Следовательно, Т — остовный маршрут.

Достаточность. Пусть u и v — две произвольные вершины орграфа G, а

T = (v₀, x, .., v, y, .., v, .., z,.., v₀)

— циклический маршрут. Тогда u достижима из v с по­мощью маршрута (v, у, ..., u)—части маршрута Т, — а v из u — с помощью маршрута (u, z, ..., v₀, х, ..., v).

Аналогично доказывается

Утверждение 2. Орграф является односторон­ним тогда и только тогда, когда в нем есть остовный маршрут. Орграф является слабым тогда и только тогда, когда в нем есть остовный полумаршрут.

Подграфы и порожденные подграфы ориентированного графа определяются так же, как и для неориентиро­ванного. Так же определяются и операции над оргра­фами.

Введем важное понятие сильной компоненты орграфа. Сильной (или силъносвязной) компонентой ориентирован­ного графа называется любой его максимальный относи­тельно включения сильный подграф.

Очевидно, что отношение взаимной достижимости вер­шин ориентированного графа G рефлексивно, симметрич­но и транзитивно. Следовательно, мы получим разбиение множества VG на классы, объединив в один класс все вершины, достижимые друг из друга. Подграфы, порож­денные классами этого разбиения, и только они, служат сильными компонентами орграфа G.


Рис. 3.
В орграфе могут быть дуги, не входящие ни в одну из его сильных компонент.

Орграф G, изображенный на рис. 3, имеет четыре сильные компоненты с множествами вершин {v₁, v₂, v₃, v₄}, {v₅, v₆, v₈}, {v₇} и {v₉}.

Пусть {S₁, S₂, ..., S_m} — множество всех сильных ком­понент ориентированного графа G. Конденсацией орграфа G называется орграф G*, вершины s₁, s₂, ..., s_m которого соответствуют сильным компонентам орграфа G, и пара (s_i, s_j) является дугой в G* тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте S_i а конец — S_j.

На рис. 3 представлены орграф G и его конденса­ция G*.

Утверждение 3. Конденсация G* любого оргра­фа G не имеет контуров.

---

 Проведем доказательство от противного. Пусть Т = (s₀, x₁, s₁, …, s₀) — контур в G*. Тогда каждая вер­шина, входящая в компоненту S_i, достижима из любой вершины, входящей в компоненту S_j. Но это противоречит максимальности сильных компонент.

Неориентированный мультиграф, получающийся в ре­зультате снятия ориентации с дуг орграфа G, называется основанием орграфа G и обозначается через G_b.

Очевидно, что орграф является слабым тогда и только тогда, когда его основание — связный мультиграф.

Орграф называется несвязным, если его основание — несвязный мультиграф.

Ориентированный граф называется турниром, если его основание является полным графом. Этот класс графов получил свое название в связи со спортивными турнира­ми без ничьих, проводимыми по круговой системе. Резуль­таты встреч можно описать ориентированным графом, вершины которого соответствуют участникам соревнова­ний, а дуга (u, v) есть в орграфе, если участник u побе­дил участника v.

1.2 Полустепени исхода и полустепени захода

Пусть G — ориентированный граф и v  VG. Множе­ство концов всех дуг, исходящих из вершины v, обозна­чается через Г(v), а множество начал всех дуг, заходя­щих в v — Г^-1(v).

.Полустепенью исхода d⁺(v) вершины v называется число дуг, исходящих из v, т. е. d⁺(v) = |Г(v)|. Анало­гично определяется полустепень захода d^-(v) вершины v:

d^-(v) = |Г^-l(v)|.

Степень deg v вершины v орграфа — это число инци­дентных ей дуг:

deg v = d⁺(v) +d^-(v)

Для произвольной бинарной m*n – матрицы А вектор c_A = (c₁, c₂, …, c_m), i-я координата с_i, которого равна чис­лу единиц в i-й строке этой матрицы, называется векто­ром строчных сумм. Аналогично определяется вектор столбцовых сумм d_A = (d₁, d₂, …, d_n): координата d_i равна числу единиц в i-м столбце. Очевидно, что

(2)

поскольку каждая из этих сумм равна числу всех единиц матрицы А.

Если А = А(G) — матрица смежности орграфа G, то



т. е. число единиц в i - й строке матрицы A(G) равно по­лустепени исхода i- й вершины, а число единиц в j - м столбце равно полустепени захода j-й вершины. Таким образом, для A =A(G) имеем

c_A

---