Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• 1. Ориентированный граф. Путь и длина пути в графе
• 2. Элементарный путь и контур
• 3. Полустепень исхода и полустепень захода вершины
• 4. Матрица смежности графа. Матрица инциденций
• 5. Двухполюсная транспортная сеть, условия ее существования
• СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Ориентированный граф. Путь и длина пути в графе

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

Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.

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

Граф- это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными. Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом (орграф) (см.рис.1) Мельников А.В., Попова Н.В., Скорнякова В.С. Математические методы финансового анализа. - М.: Анкил, 2006.- 440с..

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

Таблица №1. Примеры ориентированных графов

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

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

На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Направление линии обозначается стрелкой. Например, для графа G, представленного на рис. 2, VG={v1, v2, v3, v4, v5}, AG= {x1, x2, x3, x4, x5, x6, x7}, причем x1 и x2 - параллельные дуги, a x7 - петля.

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

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

S = (v0, x1, v1, x2, v2, x3, v3, x4,.., vn, xn,) 1)

его чередующихся вершин vi и дуг хj, что xi = (vi-1, vi) (i = 1, n). Такой маршрут назовем (v0, vn) - маршрутом. Вершины v0 и vn назовем крайними, а остальные вершины маршрута - промежуточными (внутренними). Длиной маршрута называется число входящих в пего дуг. Маршрут называется цепью, если все входящие в пего дуги различны, и путем, если все входящие в него вершины, кроме, возможно, крайних, различны.

Если в орграфе G нет параллельных дуг, то маршрут (1) может быть задан последовательностью входящих в него вершин: S=( v0, v1, v2, v3,.., vn). В любом случае маршрут можно задать последовательностью входящих в него дуг: S = (x1, x2, x3, x4,.., xn,)

Рис. 2.

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

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

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

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

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

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

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

Рис. 3.

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

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

Необходимость. Пусть G - сильный орграф и T = (v0, x1, v1, x2, v2,.., xn, v0) - его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G - сильный орграф, то существуют маршруты

T1 = (v0, y1, .., v), T2 = (v0, z1, .., v0)

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

T' = (v0, x1, v1, .., xn, v0, y1, .., v, .., z1, v0)

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

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

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

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

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

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

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

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

Рис. 4

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

Орграф G, изображенный на рис. 4, имеет четыре сильные компоненты с множествами вершин {v1, v2, v3, v4}, {v5, v6, v8}, {v7} и {v9}.

Пусть {S1, S2, ..., Sm} - множество всех сильных компонент ориентированного графа G. Конденсацией орграфа G называется орграф G*, вершины s1, s2, ..., sm которого соответствуют сильным компонентам орграфа G, и пара (si, sj) является дугой в G* тогда и только тогда, когда в G есть дуга, начало которой принадлежит компоненте Si а конец - Sj.

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

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

Проведем доказательство от противного. Пусть Т = (s0, x1, s1, …, s0) - контур в G*. Тогда каждая вершина, входящая в компоненту Si, достижима из любой вершины, входящей в компоненту Sj. Но это противоречит максимальности сильных компонент.

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

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

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

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

2. Элементарный путь и контур

ориентировочный граф матрица транспортная сеть

Пусть G - ориентированнный граф.

Путь в G - это такая чередующаяся последовательность дуг и вершин, что любая дуга в ней исходит из предшествующей ей вершины и заходит в последующую вершину.

Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы) Бурков В.Н., Коргин Н.А., Новиков Д.А.  Введение в теорию управления организационными системами.- М.: Либроком, 2009. -- 264 с.  .

Иначе говоря, замкнутый путь называется контуром. Контур, в котором все дуги разные, называется простым контуром.

Путь называется простым, если все дуги в нем - разные, и элементарным, если все вершины в пути - разные.

Для ориентированного графа можно вводить как неориентированные маршруты, цепи и простые цепи, не принимая во внимание ориентации ребер, так и ориентированные маршруты (цепи, простые цепи), в которых все ребра находятся в направлении их ориентации. Ориентированные цепи также называют путями.

3. Полустепень исхода и полустепень захода вершины

Пусть 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 - матрицы А вектор cA = (c1, c2, …, cm), i-я координата сi, которого равна числу единиц в i-й строке этой матрицы, называется вектором строчных сумм. Аналогично определяется вектор столбцовых сумм dA = (d1, d2, …, dn): координата di равна числу единиц в i-м столбце. Очевидно, что

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

4. Матрица смежности графа. Матрица инциденций

Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)=aij порядка n (n - число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.

На рис. 5 показан ориентированный граф G(X, E) и справа - матрица смежностей его вершин. Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода +(xi), а по i-му столбцу - полустепени захода -(xi). По-прежнему элементы этой матрицы - целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях.

Как и в случае неориентированных графов, каждый орграф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная матрица, элементы которой - целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма ориентированный граф.

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много «пустых мест» (нулей).

Матрицей инцидентности орграфа G с p вершинами и q ребрами называется матрица B(G) = [bij] размером (p q), элементы которой определяются следующим образом:

1, если вершина xi является началом дуги ej

bij =-1, если вершина xi является концом дуги ej;

0, если вершина xi не инцидентна дугу ej .

Ниже приведена матрица инцидентности графа, изображенного на рис. 5:

Матрица инцидентности орграфа G обладает следующими свойствами.

Сумма строк матрицы B(G) является нулевой строкой.

Любая строка матрицы B(G) является линейной комбинацией остальных строк.

5. Двухполюсная транспортная сеть, условия ее существования

Двухполюсной транспортной сетью S называется произвольный орграф без петель с множеством вершин X и с множеством дуг U, для которых выполняются следующие условия:

1 .Существует одна и только одна вершина s Є X ,в которую не заходит ни одной дуги. Эта вершина называется источником или входом сети.

2.Существует одна и только одна вершина t Є X , из которой не исходит ни одной дуги. Эта вершина называется стоком или выходом сети.

З.На множестве дуг сети U определена неотрицательная функция

С:U -->R+ U 0, ставящая в соответствие каждой дуге u Є U неотрицательное число с(u), называемое пропускной способностью сети.

Потоком в сети S=(X,U) от входа к выходу (или от источника в сток) называется произвольная неотрицательная вещественная функция, определенная на множестве дуг сети ц:U --> R+ U 0, для которой выполняются следующие условия:

1. 0 ? ц (u) ? с{u) для любой дуги

Это условие означает, что количество потока, входящего в каждую вершину сети (кроме входа и выхода) равно количеству потока, выходящего из этой вершины. Следовательно, количество потока, выходящего из входа s равно количеству потока, входящего в выход t . Эта величина называется величиной потока и обозначается цs.

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

Поток не может исчезать и накапливаться в промежуточных вершинах сети, поэтому модель будет соответствовать ситуации с отсутствием брака и незавершенного производства. Пропускная способность дуг сети в этом случае должна учитывать способность транспортной системы и производительность станков.

Интересна задача нахождения максимального потока в сети (например, максимальное число деталей, которое может обработать в единицу времени производственная система).

Разрезом сети S=(X,U), заданным на множестве вершин А C X, А ? 0,А ? X, s Є A, t Є Х\А называется множество дуг (Xi, Xj) Є U таких,

что Xi Є А, Xj Є X\A. Разрез обозначается Р(А).

Иными словами, разрезом сети является множество дуг сети, обладающих следующим свойством: любой путь от входа к выходу сети пройдет хотя бы по одной дуге разреза. При удалении разреза вход сети отделяется от выхода, т.е. сеть как бы разрезается.

Пропускной способностью разреза или величиной разреза С(А) называется сумма пропускных способностей входящих в него дуг: С(А) = У c (u).

Минимальным разрезом, разделяющим вход s и выход t сети, называется произвольный разрез Р(А), s Є A, t Є X\A с минимальной пропускной способностью.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с.

2. Бурков В.Н., Коргин Н.А., Новиков Д.А. Введение в теорию управления организационными системами.- М.: Либроком, 2009. - 264 с.

3. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука, Физматлит, 2000.- 544 с.

4. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.- 496 с.

5. Мельников А.В., Попова Н.В., Скорнякова В.С. Математические методы финансового анализа. - М.: Анкил, 2006.- 440с.

Размещено на Allbest.ru