85565 (574872), страница 2

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

Текст из файла (страница 2)

Теорема 4. (теорема Эйлера). В любом конечном графе сумма степеней вершин равна удвоенному числу его ребер. В XIX в. Гамильтон придумал игру, состоящую в том, что на доске располагались города в виде додекаэдра (рис. 13).

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

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

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

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

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

1. Метод кратчайшего пути.

2. Проект оценки и пересмотра проекта.

Характерным для этих методов является изображение проекта в виде сети взаимосвязанных работ.

Хранение графов в ЭВМ

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

Известно несколько типов матриц, позволяющих задавать граф.

Матрицей смежности графа, содержащего n-вершин, называется квадратная матрица А_nxn, каждый элемент которой а_ij определяется следующим образом:

1, если вершины i и j соединены ребром или дугой;

a_ij=

0, в противном случае.

Для графа с кратными ребрами (дугами) вместо 1 записывается число ребер (дуг) между вершинами i и j.

Для неориентированного графа, матрица смежности имеет размерность (7 х 7) и записывается в виде

1 2 3 4 5 6 7

А=

Слева и сверху проставлены номера вершин.

Для ориентированного графа, матрица смежности имеет размерность (4 х 4) и записывается в виде

1 2 3 4

А=

Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности.

Матрицей инцидентности ориентированного графа с n вершинами и m ребрами называется матрица В с n строками и m столбцами, элемент которой b_ij определяется следующим образом:

1 , если вершина является началом ребра (i, j);

-1, если вершина является концом ребра (i, j);

b_ij= 2, если вершина и начало, и конец ребра (i, j);

0, если вершина и ребро не инцидентны.

Для ориентированного графа, матрица инцидентности В_4х5 имеет следующий вид:

1 2 3 4 5

В=

Взвешенный ориентированный граф без петель, в котором выделено k-вершин, называемых полюсами, является k-полюсной цепью. Среди сетей особо выделяется двухполюсная транспортная сеть (рис. 14) S=(N, U) с множеством вершин N и множеством дуг U, для которых выполняется следующее условие:

1) существует только одна вершина сети s є N, в которую не заходит ни одна дуга. Эта вершина называется входом, или истоком сети;

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

3) каждой дуге сети u є U поставлено в соответствие неотрицательное число с(u), называемое пропускной способностью дуги.

Рис. 14

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

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

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

Задача о максимальном потоке

Рассмотрим двухполюсную сеть S=(N, U) с одним входом (источником) s є N и выходом (стоком) t є N, дуги сети (i, j) є U имеют ограниченную пропускную способность с_ij. Задача о максимальном потоке заключается в поиске таких потоков _ij по дугам (i, j) если, что результирующий поток из источника в сток является максимальным.

Математическая модель задачи о максимальном потоке выглядит следующим образом:

найти такие значения _ij, при которых

V= _sj = _sj max;

j j

при ограничениях:

0 <= _ij <=c_ij

_ij -_ij =0 i є N is it.

j j

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

Построение максимального потока

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

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение. Дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

1 ) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), (u)

2) направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), (u)>0.

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, – уменьшающими.

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

Пример 1. Построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 15.

Над каждой дугой указана ее пропускная способность, в скобках – поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги – допустимые:

• дуга (s, 1) – увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности: 6 < 9;

• дуга (1,2) – также увеличивающая дуга: 3 < 6;

• дуга (2,4) – уменьшающая, так как она проходит против потока и поток по ней 2 > 0;

• дуга (4, t) – увеличивающая: 4 < 7.

Пример 2. Построим максимальный поток для сети, представленной на рис. 4.16.

Рис. 16

Начальное значение потока равно нулю V=0.

Увеличивающие цепи:

1. (s, 1, 2, t), = min (8, 4, 10) = 4;

2. (s, 1, 3, 4, t), = min (8–4, 3, 2, 9) = 2.

Больше увеличивающих цепей построить нельзя.

V_max = 6.

Построим теперь максимальный поток для неориентированной сети с той же структурой рис. 17.

Рис. 17

Увеличивающие цепи:

1. (s, 1, 2, t), = 4;

2. (s, 1, 3, 5, t), = 3;

3. (s, 3, 2, t), = 2;

4. (s, 3, 4, t), = 2.

Больше увеличивающих цепей не существует. Максимальный поток V_max = 7+4 = 9+2 = 11. Оптимальная ориентация показана на рис. 18.

Рис. 18

Литература

1. Гончарова Г.А., Молчалин А.А. «Элементы дискретной математики»: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2005. (Серия «профессиональное образование»).

2. Фомин Г.П. «Математические методы и модели в коммерческой деятельности»: Учебник. – М.: Финансы и статистика, 2007.

Характеристики

Список файлов ответов (шпаргалок)