Понятие графа и его элементы

Теория игр.

Классификация игр

 

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

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

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

По характеру взаимодействия игры делятся на:

1) бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

2) коалиционные: (кооперативные) – могут вступать в коалиции.

В кооперативных играх коалиции наперёд определены.

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

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

Матричная игра- это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец- стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1,во второй матрице – выигрыш игрока 2.)

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

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

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

 

«Условия принятия теории игр»

Управление любым объектом экономически осуществляется путем принятия последовательности управленческих решений. Для принятия решения необходима некоторая информация (совокупность сведений о состоянии объекта управления и условиях работы). В тех случаях, когда отсутствует достаточно полная информация, возникает неопределенность в принятии решения. Причины этого могут быть различны: требующаяся информация не может быть получена принципиально (неустранимая неопределенность); информация не может быть получена своевременно, к моменту принятия решения; затраты, связанные с получением информации, слишком высоки. По мере совершенствования сбора, передачи и обработки информации неопределенность управленческих решений будет уменьшаться. К этому нужно стремиться.

Существование неустранимой неопределенности связано со случайным характером многих явлений в торговле. Например, случайный характер изменения спроса делает невозможным его точное программирование, а следовательно, и формирование идеально точного заказа на поставку товара.

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

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

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

 

Игра двух лиц.

Две стороны, участвующие в игре будем называть игрок 1 и игрок 2. Каждый из игроков располагает конечным набором действий (чистых стратегий), которые он может принять в процессе игры. Обозначим множество чистых стратегий игрока 1 через Х, а отдельные элементы этого множества х₁, х₂, … х_m, множество чистых стратегий игрока 2 – Y, а его элементы y₁,y₂,... y_n.

Игра имеет повторяющийся циклический характер. В каждом цикле игроки выбирают одну из своих стратегий, что однозначно определяет платеж а_ij = a (x_i,y_j). Интересы игроков противоположны. Игрок 1 старается вести игру так, чтобы платежи были как большими. Для игрока 2 желательно как можно меньшие значения платежей (с учетом знака). Причем в каждом цикла выигрыш одного из игроков в точности совпадает с проигрышем другого. Игры такого типа называются играми с нулевой суммой. Матрица А = (а_ij)_m*n называется платежной матрицей.

Пусть, например, игра заключается в том, что игроки одновременно, но тайно друг от друга, задумывают число 1 и 2. Если сумма задуманных игроками чисел четна, то выигрывает игрок 1, если нечетна – игрок 2. Размер выигрыша выражен в рублях и совпадает с суммой чисел. Перечисленные правила игры приводят к следующей платежной матрице:

2 -3 (*)

А = -3 4

 

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

Оптимальное поведение игрока инвариантно относительно изменения всех элементов платежной матрицы на некоторую величину. Действительно, если элементы матрицы (*) увеличены на 3, в, результате получена новая платежная матрица: 5 0

А = 0 7

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

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

 

-5 3 -2 1

1 5 -2 3

-6 6 7 -4

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

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

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

Нижней ценой V1(верхней ценой V2) называется наилучший из наихудших платежей игроку 1 (игроку 2) что можно записать так:

V₁ = max min a_ij

x_iÎx y_iÎy

V₂ = min max a_ij

y_iÎy x_iÎx

Для только что рассмотренной платежной матрицы V1=-2,V2=1. Определяя нижнюю цену игры, следует сначала определить минимальные значения платежей для каждой строки (это числа –5, -2, -6). Эти платежи соответствуют наиболее неблагоприятному (наихудшему) выбору столбца игроком 2, когда игрок 1 выбирает одну из строк. Наилучшим одним из этих трех платежей является –2.

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

Стратегии игроков, соответствующие нижней и верхней ценам игры, называются максиминной и минимаксной.

Если нижняя цена совпадает с верхней, то их общее значение V=V1=V2 называется ценой игры. Цену игры называют также седловой точкой платежной матрицы. Если существует цена игры, максиминная стратегия является оптимальной для игрока 1, а минимаксная – для игрока 2. Действительно, применение игроками указанных стратегий гарантирует игроку 1 платежи a_ij³V, а игроку 2 платежи a_ij£V.

Общее решение указанных двух неравенств a_ij=V.

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

Пусть дана платежная матрица:

4 5 9 3 3

8 4 3 7 3

7 6 8 9 6

7 2 4 6 2

8 6 9 9

для которой V=6. Соответствующие этому элементу строка и столбец являются оптимальными для игроков. При упрощении платежной матрицы V₁, V₂ не изменяются. Итак, мы установили, что в случае существования цены игры оптимальное поведение игроков состоит в том, что каждый из них использует одну из чистых стратегий. Не исключено, конечно, что оптимальная стратегия не единственна. Например, если все элементы платежной матрицы одинаковы, любая стратегия оптимальна. Но игроку достаточно ограничиться использованием только одной из них.

 

 

Смешанная игра.

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

Дискретное распределение вероятностей на множестве чистых стратегий называется смешанной стратегией.

Обозначим через a_i = р (х_i) вероятность применения игроком I чистой стратегии х_i (i = 1, 2, …, m), а через b_j = р (у_j ) – вероятность применения игроком II чистой стратегии у_j (j = 1, 2, …, n).

Множество W смешанных стратегий игрока I можно описать следующими ограничениями:

m

S a_i = 1; (4.3)

i=1

 

a ³ 0, (4.4)

где a = (a₁, a₂, …,a_m).

Ограничения

n

S b_j = 1; (4.5)

_j=1

 

b ³ 0,

где b = (b₁, b₂, …,b_n), определяют множество смешанных стратегий игрока II, которое обозначим H.

В процессе игры платежи a_ij появляются с вероятностями

р_ij = a_ib_j (i = 1, 2, …, m; j = 1, 2, …, n).

Математическое ожидание платежа

 

 

m n

К (a, b) = S S а_ij р_ij

i=1 _j=1

 

называется платежной функцией смешанной игры.

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

Обозначим через К₁, К₂ соответственно нижнюю и верхнюю цены смешанной игры. Смысл указанных величин определяют следующие формулы:

К₁ = max min K (a, b);

aÎW bÎH

К₂ = min max K (a, b).

bÎH aÎW

 

Каждая из этих величин является наилучшим гарантированным платежом соответствующему игроку. Здесь под гарантированным платежом понимается наихудший из всех возможных.

Для нахождения К₁ определим сначала множество D_h всех стратегий игрока I, гарантирующих ему получение платежа не хуже некоторой величины h > 0. Без ограничения общности дальнейших рассуждений можем считать, что множество D_h не пустое. Для этого следует в случае необходимости все элементы платежной матрицы увеличить на достаточно большую величину, от чего оптимальное поведение игроков не зависит.

Пусть известно, что игрок II у_j. Среднее значение платежа при этом будет зависеть только от a:

 

m

К (a,у_j) = S а_ij а_i.

i=1

 

Поскольку игрок II может воспользоваться любой из своих чистых стратегий, необходимым условием принадлежности a множеству D_h является выполнение системы неравенств

 

m

S а_ij а_i ³ h (i =1, 2, …, n). (4.6)

i=1

 

Для доказательства достаточности умножим каждое из этих неравенств на соответствующее значение b_j и сложим. В результате будем иметь

 

m n n

S S а_ija_ib_j ³ h S b_j.

i=1 _j=1 i=1

 

С учетом ограничений (4.5) полученное неравенство запишем следующим образом:

 

К (a, b) ³ h.

 

Итак, если выполнены условия (4.6), то для любых значений bÎH выполняется условие (4.7). Иначе говоря, система ограничений (4.6) совместно с условиями (4.3) и (4.4) определяет множество D_h.

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

 

max h = K₁ (4.8)

aÎD_h

 

и ограничениями (4.3), (4.4), (4.6).

Преобразуем указанную задачу. Разделив на h каждое из неравенств (4.6), получим

 

m

S а_ijz_i ³ 1 (j = 1, 2, …,n), (4.9)

i=1

где z_i = a_i / h. Можно сказать, что мы произвели замену переменных

a_i = h z_i. (4.10)

Отсюда следует, что

 

z_i ³ 0 (i = 1, 2, …,m). (4.11)

Подставив соотношение (4.10) в (4.3), получим

m m

h S z_i = 1 или S z_i = 1/ h.

i=1 i=1

 

С учетом формулы (4.8) запишем целевую функцию для новых переменных:

m

min S z_i= 1/ K₁. (4.12)

i=1

Мы получили задачу линейного программирования (4.9), (4.11), (4.12), решение которой позволяет определить K₁ и соответствующие оптимальные значения z_i, постановка которых в соотношение (4.10) дает оптимальные значения a_i (i = 1, 2, …,m).

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

Вследствие существования допустимого плана и ограниченности снизу (нулевым значением) целевой функции задачи (4.9), (4.11), (4.12) ее решение существует. Согласно теории двойственности, в этом случае обязательно существует решение двойственной задачи и оптимальные значения целевых функций численно совпадают. Отсюда следует, что нижняя и верхняя цены смешанной игры всегда совпадают:

К₁ = К₂ = v.

Это равенство впервые доказано Дж. фон Нейманом в 1928 г. и известно под названием основной минимаксной теоремы теории игр.

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

При решении игры с заданной платежной матрицей А=(а_ij)_m*n целесообразно придерживаться следующей последовательности действий.

1. Проверяется существование решения игры в чистых стратегиях, для чего определяются нижняя v₁ = v₂, то оптимальными чистыми стратегиями являются максиминная (для игрока I) и минимаксная (для игрока II). На этом решение игры заканчивается.

2. В случае отсутствия седловой точки (v₁ ¹ v₂) производится упрощение платежной матрицы путем исключения из нее строк и столбцов, соответствующих доминируемым или дублирующим стратегиям.

3. Определяются оптимальные смешанные стратегии. Для этого решается двойственная пара задач линейного программирования:

 

 

Задача I Задача II

 

m n

min S z_i= 1/ K₁ = 1/v; max S q_j= 1/ K₂ = 1/v;

z i=1 q j=1

 

m n

S а_ij z_i³ 1 (i =1, 2, …, n; z_i ³ 0). S а_ij q_j³ 1 (i = 1, 2, …,m; q³ 0)

i=1 j=1

 

Без ограничения общности будем предполагать, что v > 0. В случае невыполнения этого условия все элементы платежной матрицы увеличиваются на достаточно большую величину. Тогда решение игры определяется по формулам:

 

m -1 n -1

v = S z_i* = S q_j*;

i=1 j=1

a* =vz*; b* vq*.

 

Действие 1 и 2 не являются обязательными. Решение игры можно начинать с действия 3.

 

 

Теорема об активных стратегиях. Следствие 1. Следствие 2.

 

Чистые стратегии, соответствующие ненулевым вероятностям, определяющим оптимальные смешанные стратегии, называются активными.

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

Пусть игрок I применяет оптимальную смешанную стратегию. Активной стратегии игрока II соответствует активное (выполняющееся как строгое равенство) ограничение задачи I, согласно второй основной теореме двойственности в линейном программировании, т.е.

 

m

S а_ik z_i = 1,

i=1

 

где k – номер активного ограничения. Умножив это равенство на v, получим

 

m

S а_ik a_i* = v.

i=1

Левая часть последнего равенства есть средний платеж, соответствующий условию теоремы, когда k-я стратегия игрока II является активной.

Следствиями доказанной теоремы являются следующие утверждения.

1. Любое чередование активных стратегий обеспечивает равновесие в игре, если другой игрок применяет оптимальную смешанную стратегию.

2. Если все чистые стратегии игроков активны, то наступает равновесие при оптимальной игре хотя бы одного из игроков.

 

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

 

 

ИГРА С ПРИРОДОЙ.

 

Хозяйственная деятельность человека может рассматриваться как игра с природой. Основной особенностью природы как игрока является ее незаинтересованность в выигрыше.

Условимся, что лицо, принимающее решение (ЛПР), является игроком I, который в процессе игры выбирает строки платежной матрицы. Игрок II – природа. Чистые стратегии природы соответствуют ее возможным состояниям. Природа меняет состояние стихийно, совершенно не заботясь о результате игры.

В антагонистической игре мы предполагали, что игроки пользуются оптимальными (в определенном смысле) смешанными стратегиями. Можно предположить, что природа применяет наверняка не оптимальную стратегию. Тогда какую? Если бы существовал ответ на этот вопрос, то принятие решения ЛПР сводилось бы к детерминированной задаче. Действительно, в этом случае ЛПР может подсчитать среднее значение платежа для каждой своей чистой стратегии по формуле

n

а_i = S а_ij b_j (i = 1, 2, …,m)

j=1

 

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

Свою оценку характера поведения природы будем характеризовать числом H Î [0;1], которое можно связывать со степенью активного «противодействия» природы как игрока. Значение H = 1 соответствует наиболее пессимистичному отношению ЛПР в смысле «содействия» природы в достижении им наилучших хозяйственных результатов. Значение H = 0 соответствует наибольшему оптимизму ЛПР. В хозяйственной деятельности указанные крайности очень опасны. Скорее всего, целесообразно исходить из некоторого промежуточного значения H. В этом случае используется критерий Гурвица, согласно которому наилучшим решением ЛПР является чистая стратегия х_i, соответствующая условию

 

G = max [H min а_ij + (1- H)max а_ij].

i j j

 

В случае крайнего пессимизма ЛПР (H= 1) указанный критерий называется критерием Вальда. Согласно этому критерию, наилучшей считается максиминная стратегия. Такой выбор соответствует наиболее робкому поведению ЛПР, когда он предполагает наиболее неблагоприятное поведение природы, боится больших потерь. Можно предположить, что он не получит больших выигрышей.

Согласно критерию Сэвиджа, следует выбирать чистую стратегию х_i, соответствующую условию

 

S = min max r_ij,

i j

где r_ij (max a_tj ) - а_ij.

_t

 

Недостатком критериев Вальда, Сэвиджа и Гурвица является субъективная оценка поведения природы. Хотя указанные критерии и дают некоторую логическую схему принятия решений, резонно все же задать вопрос: «А почему сразу не выбрать субъективное решение, вместо того чтобы иметь дело с разными критериями?» Несомненно, определение решения по различным критериям помогает ЛПР оценить принимаемое решение с различных позиций и избежать грубых ошибок в хозяйственной деятельности.

 

СТАТИСТИЧЕСКАЯ ИГРА.

 

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

Действия ЛПР по сбору информации, полезной в принятии решения (выборе чистой стратегии), назовем статистическим экспериментом. Результат статистического эксперимента обозначим u= (u₁, u₂, …,u_s). Причем эксперимент проводится на каждом цикле перед выбором решения.

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

Функция решений d = d(u) = х_i устанавливает соответствие между результатами статистического эксперимента и принимаемым решением. Принимаемое таким образом решение является случайным, так как зависит от случайного значения u.Тогда платеж а_ij, характеризующий эффективность принимаемого решения, так же будет случайным.

Математическое ожидание платежа обозначим R и назовем платежной функцией статистической игры. Ее значение зависит от функции решения и состояния природы (решения игрока II):

R = R[d(u); y_j].

Пусть имеется множество функций решений

 

D = {d₁, d₂, …,d_w }.

Обозначим b_ij= R[d_i; y_j]. Матрица В = (b_ij) _w*n называется платежной матрицей статистической игры.

Схема принятия решения игроком I (ЛПР) следующая:

1) проведение статистического эксперимента;

2) выбор функции решения;

3) определение х_i с использованием выбранных функции решения.

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

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

 

 

Основные понятия теории графов

Понятие графа и его элементы

Допустим, что участники торгово-экономических связей (A,B,C,D,E,F) заключили между собой договор о взаимных поставках.

При этом А обязался поставить свои товары B,C,D,E,F; B – соответственно A,D,E; C, в свою очередь – А И D; D наладил связи с A,B,C; a E-c A,B.

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

 

Схема такого вида называется графом. Математическое определение Г- рафа формулируется так:

 

 

граф G определяется непустым множеством вершин X(G), множеством рёбер V(G) и отношением инцидентности, которое каждому ребру сопоставляет одну или две вершины, называемые его концами.

Граф обозначается символом G(X, V). Элементы графа, изображённые точками на плоскости, называются вершинами графа.

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

 

Линии, соединяющие любые пары вершин, называются дугами графа или рёбрами графа. Дуги графа должны иметь направления, обозначаемые стрелкой от начала дуги к её концу. Такие графы называются ориентированными. Рёбра не имеют направления. Дуги показывают связь субъектов, последовательность работ, например, при создании супермаркета: проектные, строительные, монтажные, пусконаладочные и другие работы или отношения участников в торговых операциях.

Например, А осуществил поставку товаров B(A→B), В рассчитался с А (А←В).

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

 

P(A)=5, P(B)=3, P(C)=2, P(D)=3, P(E)=2, P(F)=1.

Вершина, степень которой P(x) > 2, называется узлом, а вершина, степень которой P(x) ≤ 2, - антиузлом.

Таким образом, вершины A,B,D – узлы, а вершины C,F,E – антиузлы.

Имеются понятия: полустепень – захода вершины x – количество дуг, заходящих в данную вершину, P - (x) и полустепень исхода вершины x- количество дуг, исходящих из вершины x, P+(x).

В нашем примере степень каждой вершины графа, приведенного на рисунке 1,1, показывает количество партнёров, с которыми заключены договоры. Выделим из всех вершин “нестандартную”, такую, в которую дуга только входит или выходит и причём только одна. Такая вершина называется висячей. В нашем примере ею является вершина F.

Такой же “нестандартной” дугой является петля. Это такая дуга, которая выходит из вершины x и входит в неё же, т.е. связывает точку x саму с собой. Пример петли дан на рис. 1.2.

 

 

 

 

 

 

Смысловое значение такой дуги можно представить в случае, если отрасль производит какой-то продукт и сама же его потребляет на собственные нужды. Тогда степень вершины x можно определять как P(x)=1, когда рассматривается вопрос только

производства, и P(x)= 2,когда учитывается производство и потребление, т.е. степень вершины с петлей учитывается в зависимости от условий поставленной задачи.

С точки зрения ориентации дуг различают: ориентированные графы, в которых вершины соединяются стрелками (дугами), указывающими направления; неориентированные графы, в которых вершины соединяются линиями (рёбрами); смешанные графы, состоящие из дуг и рёбер.

Ориентированные графы наиболее информативны. С их помощью можно показать не только взаимосвязь торговых партнёров, но и характер сделки (купли, продажи, расчётов с поставщиком и т.п.). А если каждой дуге присвоить определённое число, то можно отразить количественную или стоимостную характеристику торговой операции. Например, граф A→20→B говорит о том, что A поставил B товаров на 20тыс.руб.

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

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

Конечный путь, начинающийся и заканчивающийся в одной и той же вершине, называется контуром. Так же, как и путь, контур может быть простым, если в нём ни одна дуга не встречается дважды, и сложным – в противном случае.

Следует иметь ввиду, что в неориентированных графах вместо пути принято употреблять слово цепь, а вместо контура – цикл.

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

Остановимся на двух задачах, вошедших в классику теории графов. В первой задаче используется понятие простого пути. Её сформулировал известный математик Леонард Эйлер (1707-1783) в первой работе о графах. Он рассмотрел “задачу о кёнигсбергских мостах” (части города были соединены семью мостами). Задача состояла в том, что чтобы выйдя из дома вернуться обратно, пройдя только один раз по каждому мосту. Решение этой задачи привело к формулировке общей проблемы теории графов: “ На каких графах можно найти цикл, содержащий все рёбра графа, причём каждое ребро в точности по одному разу?”. Такой цикл получил название эйлеровой линии, а граф, обладающий эйлеровой линией, - эйлеровым графом. Признаком наличия эйлеровой линии является честность степеней всех вершин графа. На рисунке 1.3 приведён исходный граф а на рисунке а на рисунке 1.4 - преобразованный граф задачи Эйлера.

 

 

 

Вторую задачу поставил ирландский математик У.Гамильтон. Его именем назван Граф, содержащий цикл, включающий каждую вершину этого графа 1 раз. Такой цикл назвали гамильтоновым. Это понятие применяется в задаче о коммивояжере. Район, который должен посетить бродячий торговец, содержит какое-то количество городов расстояния между ними известны, и нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходное положение. К этой формулировке сводятся задачи о лучшем использовании транспортных средств.

Признаки наличия гамильтоновского цикла ещё не сформулированы строго.

 

Разновидности графов

 

Граф G(X,V), состоящий только из изолированных вершин, называется нуль-графом.

Для него справедливо P+(xi)= P-(xi) = 0 для всех xi ϵ X.

Однородный граф – это граф, в котором степени всех вершин одинаковы.

Симметрический граф – граф, в котором любые две смежные вершины соединены двумя противоположно ориентированными дугами.

Здесь справедливо: если (x1,x2)ϵV, то и (x2,x1)ϵV.

Антисимметрический граф – это граф без петель, в котором каждая парасмежных вершин соединена только в одном направлении. Для него справедливо: если (x1,x2)ϵ V, то (x1,x2)ϵ.

 

 

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

Имея некоторый граф (рис 1.5), можно всегда превратить его в полный с теме же вершинами, добавлением недостающих дуг и петель. Это новый граф будем называть дополнением графа G (рис. 1.6) и обозначать его G. Объединение графов G и G даёт полный граф с теми же вершинами.

 

 

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

Изоморфные графы. Любой граф G(X, V) можно изображать по-разному: не обязательно изображать его рёбра (дуги) прямыми линиями, можно произвольно располагать вершины на плоскости. Говорят, что графы изоморфны, если: они имеют одно и тоже число вершин: две любые вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены.

Термин ”изоморфный“ иос - равный, одинаковый и морфии-вид, форма часто используется в математике. В одном случае это графы, равные по форме, на рис.1.7 изображены изоморфные графы.

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

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

 

Двудольный граф – граф, представленный двумя множествами M и P,вершины которых внутри каждого множества не соединены между собой ребрами (рис. 1.9).

R

1 2 3 r

 

1 2 3 m

M

Рис.1.9

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

 

Операции над графами

Подграфом графа G (X,V) называется граф G(A, ),определяемый следующим образом.

1. Вершины А подграфа G(A, ) являются некоторым подмножеством ершин графа G (X,V), т.е. А есть подмножество X (A ⊂ X).

2. Дугами (ребрами) подграфа G(A, ) являются те же дуги (ребра) графа G (X,V), которые инцидентны вершинам А. Например, приведем граф G (X,V) с вершинами X={a,b,c,d,e}.

Подграф G(A, ) с вершинами A={d,e} имеет следующий вид (рис. 1. 11,б).

а)Граф G(X,V) б)подграф G(A, ) в) V+(A)=<B, >

Рис.1.11

 

Подграфы эффективно применяются в многошаговых задачах, которые имеют сложный разветвленный так называемый сетевой граф. Верхним сечением V+(A) некоторого подмножества А вершин графа < X, V > называется подграф <B, >, вершины которого являются непосредственными предшественницами вершин А. Например, на рис. 1. 11 для графа <X, V> (а) и множества А(б) верхним сечением является подграф < > (в).

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

Добавление ребра – если вершины и графа не смежны, то можно определить граф G+L, где L ). Он получается из графа G добавлением ребра L.

Объединение – граф H будет объединением (или наложением) графов G и F, если VH=VG VF и XH= XG XF, т.е. H= G F (рис. 1.12).

 

 

Рис.1.12

Произведение есть граф, для которого VG= (рис. 1.13).

 

Рис.1.13

Отождествление (слияние) вершин. Пусть и - вершины графа G. Тогда H = G - - . К графу H присоединяем новую вершину , соединив ее с каждой из вершин, входящих в объединение окружений вершин и , т.е. получаем граф их графа G отождествлением вершин и .

 

 

Стягивание ребра означает отождествление смежных вершин (рис. 1.14)

 

Рис.1.14

Расцепление вершин – операция, двойственная стягиванию ребра (рис. 1.15)

2 2

 

1 3 1 3

4 5

 

Рис.1.15

Древовидные графы и сети

Понятие связности графа

В общем случае граф может быть представлен отдельными графами, не имеющими общих дуг. Например, граф G(X,V) может быть задан в виде трех графов: , в которых ⊂ X, ⊂ X, ⊂ X, и ⊂ V, ⊂ V, ⊂ V. В этом случае граф G(X, V) называется несвязным, а каждый из составляющих его графов - компонентами связности. Другими словами, компонента связности графа G(X, V) – это граф, состоящий из вершин x X и всех тех вершин, которые соединены с ней (компонентой) некоторой цепью. Компоненты связности образуют разбиение множества вершин x графа G(X, V) на отдельные, не связанные друг другом подмножества.

Граф связан в том и только в том случае, если он состоит из единственной компоненты связности.

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

Рис.2.1

Несвязный граф, состоящий из четырех связных компонент, одна из которой – изолированная вершина 5.

 

 

 

X2 X6

 

X1 X3 X5

 

X4

 

Рис.2.2