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

     6.  Выявление маршрутов  с заданным количеством  ребер (дуг). 

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

     Теорема 3.  Для определения маршрутов, состоящих из k ребер (дуг), необходимо возвести в k-ю степень матрицу смежности вершин P. Тогда элемент матрицы даст количество маршрутов длины k (состоящих из k ребер) из вершины в вершину . 

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

v₂

v₃

v₁

v₄

e₁

e₂

e₃

e₆

e₅

e₄

 

     Решение.  Составим матрицу смежности вершин P и возведем ее в квадрат. Результат возведения:

      .

     Рассмотрим  первую строку. Например, элемент  . Это значит, что существует три маршрута из v₁ в v₁ длиной в два ребра. Действительно, это маршруты . Из v₁ в v₂ существует два маршрута: .

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

     Действительно, для данного примера имеем 
 

     

     ,

     Аналогично  обстоит дело с орграфом, хотя у  него матрица смежности вершин несимметрическая.

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

v₂

v₃

v₁

v₄

e₁

e₂

e₃

e₆

e₅

e₄

 

     Решение.  Матрица смежности P и результаты ее возведения в квадрат и куб имеют следующий вид:

      , 

      .

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

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

     7.  Упорядочивание вершин  и дуг орграфа. 

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

     1)  вершины первой группы не имеют  предшествующих вершин, а вершины  последней группы последующих;

     2)  вершины любой другой группы  не имеют предшествующих в следующей группе;

     3)  вершины одной и той же группы  дугами не соединяются. 

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

     Алгоритм  Фалкерсона для упорядочения вершин:

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

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

     Заключение

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

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

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

 

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

1. Уилсон Р. Введение в теорию графов

2. Бурков В.Н., Новиков Д.А. Элементы теории графов

3. Хемди А. Таха Введение в исследование операций

4. Берж К. Теория графов и ее применение

5. Семенов Ю.А Элементы теории графов 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Министерство  Образования и  науки Российской Федерации

Федеральное Агентство по образованию

Российский  Государственный  социальный университет

Филиал  РГСУ в г. Обнинске 
 
 
 
 
 
 
 
 
 
 
 

Контрольная работа  

По дисциплине: «Компьютерные модели в экономике» 

Тема: «Орграфы» 
 
 
 
 
 
 
 
 
 
 

Выполнила: студентка 3 курса

Заочного  отд.

Ф-та «финансы и кредит»

Смолич  А.Н.

                                                                                                 Проверила: преподаватель

Белозерцева Е.А. 
 
 
 
 
 

Обнинск-2011г. 

ПРАКТИЧЕСКАЯ  ЧАСТЬ

Решение двумерной задачи

Для решения  двумерной задачи воспользуемся  симплекс-методом.

Для начала придумаем  задачу оптимального объема выпуска  продукции.

Пекарня производит черный и белый хлеб. На производство 1 порции белого хлеба идет 7 кг. ржаной муки и 3 кг. муки высшего качества. На производство черного хлеба идет 12 кг. ржаной муки и 11 кг. муки высшего качества. В сутки выделяют ржаной муки 254 кг., а муки высшего качества 205 кг. Составить оптимальный план выпуска черного и белого хлеба, если прибыль с 1 порции черного хлеба 6 у.е, а с одной порции белого хлеба 8 у.е.

X1 – кол-во порций черного хлеба

X2 – кол-во порций белого хлеба.

Решение:

Целевая функция: 
6X₁+8X₂→max 
Условия: 
7X₁+12X₂≤254 
11X₁+3X₂≤205

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

7X₁+12X₂+s1=254 
11X₁+3X₂+s2=205

Переходим к  формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам  необходимо найти максимум целевой  функции, то в таблицу заносятся  коэффициенты с противоположным  знаком 
Из данных задачи составляем исходную симплекс таблицу. 
 

Так как в  столбце решений нет отрицательных  элементов, то найдено допустимое решение. В строке F имеются отрицательные  элементы, это означает что полученное решение не оптимально. Определим  ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный  элемент - это -8. Ведущей строкой  будет та, для которой отношение  решения  к соответствующему элементу ведущего столбца минимально. Ведущей  строкой является s1, а ведущий элемент: 12.

 

В строке F имеются  отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для  этого найдем в строке F максимальный по модулю отрицательный элемент - это -1.33 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей  строкой является s2, а ведущий элемент: 9.25.