Новые виды достижимости и математические модели многопродуктовых потоков в мультисетях

• Автор: Петросян, Артем Георгиевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ростов-на-Дону
• Количество страниц: 148 с. : ил.

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

Глава 1. Ориентированные графы с барьерной достижимостью

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

1.2 .Достижимость на графах с условием барьерного перехода.

ГЗ.Случайные процессы на графах с барьерной достижимостью

1.3.1. Случайные процессы, классическая постановка.

1.3.2. Случайные процессы на графах с барьерной достижимостью.

1.4. Потоковая задача в сетях с барьерной достижимостью

1.4.1. Основные понятия, определения и утверждения.

1.4.2. Потоки в сетях с барьерной достижимостью
Глава 2. Ориентированные графы с биполярной магнитностью.
2.1. Достижимость на графах с условием биполярной магнитности
2.2. Случайные процессы на графах с биполярной магнитностью
2.3. Потоковая задача в сетях с биполярной магнитностью
Глава 3. Многопродуктовые потоки мультисетях.
3.1. Постановка задачи.
3.2. Алгоритм построения максимального потока в многопродуктовой мультисети.
3.3 Теорема ФордаФалкерсона для мнопродуктовых мультисетей
Приложение.
Литература


Помимо понятия связанных дуг вводится понятие связанных сетей. Предложен алгоритм построения набора связанных сетей по исходному графу, сводящий задачу о построении многопродуктового потока к задаче о последовательном построении однопродуктовых потоков на каждой из сетей набора. Показано, что порядок выбора продуктов из набора не оказывает влияния на величину суммарного потока. Также приведена задача о максимальном потоке в многопродуктовой сети с дополнительным условием: величина потока каждого продукта должна быть не меньше некоторой заданной величины. Показано, что в данном случае порядок выбора продукта играет существенную роль. Глава 1. В данной главе рассматриваются ориентированные графы с условием барьерной достижимости. Вводится понятие барьерной достижимости, приводится алгоритм построения вспомогательного графа для сведения данной задачи к классической задаче о достижимости на графах. Доказываются теоремы о взаимной связи между барьерной достижимостью на исходном графе и обычной достижимостью на вспомогательном графе. Это позволяет рассмотреть задачи о достижимости и кратчайших путях, о случайном блуждании в ориентированных графах с барьерной достижимостью, приводятся формулы переопределения вероятностей перехода для вспомогательного графа с целью сведения данного процесса блуждания к Марковскому. Рассматривается задача о построении максимального потока в сети с барьерной достижимостью. Приводится алгоритм построения максимального потока на вспомогательном графе и доказывается аналог теоремы Форда-Фалкерсона для сетей с барьерной достижимостью. Основные понятия и определения. Приведем необходимые понятия и определения, требующиеся для дальнейшего изложения ([7]). Определение 1. Ориентированным графом (орграфом) будем называть тройку С(Х, ? Х(*0) - множество, называемое множеством вершин графа, С/ - множество (возможно и пустое), называемое множеством дуг, / - отображение, действующее из и в X х X, называемое отображением инцидентности. В ведем стандартные отображения Р • X х X —> X и р2ХхХ > X по следующим правилам: Р (*, у) = х, р2 (х, у) = у. А ° /Xм) будем называть начальной вершиной дуги и, а вершину У = (р2° /Xм) • концевой вершиной дуги и . Если (Р[ ° /)(и) = (р2 ° /)(и), дуга и называется петлей. Определение 1. А°/оА0(0 = (Ло/°;' + 1), / = 1,л-1. Если (р2 0 / 0 /*)(м) = (А ° / 0 /^)0) (начальная вершина пути совпадает с концевой вершиной этого пути), такой путь называется циклом. Если отображение р инъективно, то путь (цикл) называется простым. Определение 1. Вершина у является достижимой из вершины х, если существует путь р, начальной вершиной которого является х, а концевой - У . Определение 1. Вершина дуги /7(1), не являющаяся общей с дугой 7/(2), называется началом цепи, а вершина дуги ^{р) р(Х), не являющаяся общей с дугой Т](п -1), называется концом цепи. Если отображение 7 инъективно, то цепь называется простой. Определение 1. Орграф Є(Х,и,/) называется связным, если Ух, у Є X существует цепь, ведущая из х в У. С(Х,,/) называется сильно связным, если Ух, у є X х и У - взаимно достижимы. Здесь и далее ориентированный граф будем называть просто графом, при этом всегда полагаем, что граф является связным. Ц | (/? Определение 1. Пусть С(Х,и,/) - граф, Х'(^0) с X. С(Х',иг, ДДгде их, = ГХХ'). Определение 1. С, порожденным множеством С/', называется граф С{Х,и Д. Здесь 4, - ограничение отображения /:? Д,. Ум є г/’). Достижимость на графах с условием барьерного перехода. Пусть имеем орграф С(Х, , /). Множество 1} = Ыи и ? Б попарно непересекающиеся. Множество ? Множество - множество дуг барьерного перехода. Для удобства дальнейшего описания ограничений, накладываемых на рассматриваемые пути, будем считать, что по дугам графа движется частица, перемещаясь между вершинами графа. Лм(і>Л = ? При этом в указанной сумме каждая дуга считается столько раз, сколько раз она встречается на рассматриваемом отрезке пути. ЛД/^) = //([и]я)п? Характери стику Л^О'эУ) будем называть величиной барьерного показателя отрезка [і,у’]я пути //. Ц через / шагов от начала пути.