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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



Определение 2. Вершины xi и xj графа G = (X, U) называются смежными, если (i, j) ? U

Определение 3. Дуга (i, i) ? U - называется петлей.

Определение 4. Вершина xi ? X и дуга (i,j) ? U инцидентны, если xi есть конец ребра (i,j).

 

Определение 5. Степень вершины xi - это число инцидентных ей ребер.

 

 

 
 

 


- степень вершины i

 

 

Утверждение. В любом неориентирном графе G без петель с n вершинами и m ребрами имеет место

Следствие. Число вершин с нечетными степенями всегда четно.

Орграф.

           
 
   
- полустепень исхода
     
- полустепень захода
 
 

 

 


Утверждение. Если G- орграф без петель с n вершинами и m дугами, то:

 

Матричные представления графов.

Графы можно задавать не только аналитическим и графическим способом, но и с помощью матриц.

 

Определение. Матрицей смежности Ag = {aij) графа G = (X, U) называется квадратная матрица порядка n , элементы которой определяются зависимостью:

1, если в G существует дуга (i,j) (xi ,xj смежны)

0, если в G нет дуги (i,j) (xi ,xj не смежны)

Пример

u6
u4
u5
u3
u2

 

Матрица смежности полностью определяет структуру графа.

Например, сумма всех элементов строки Xi матрицы Ag дает полустепень исхода вершины Xi, a сумма элементов столбца Хk - дает полустепень захода вершины Хk - .

Определение. Матрица инциденций графа G = (X, U) (обозначается В = (bij) ) является матрица размерности m x n , элементы которой определяются следующим образом:

1, если Хi является начальной вершиной дуги Uj,

bij=
-1, если Xi является конечной вершиной дуги Uj,

0, если Хi не является вершиной дуги Uj,

2, если Uj является петлей.

 

U1 U2 U3 U4 U5 U6
Bg =
X1

-1
X2 -1
X3 -1 -1
X4 -1 -1

 

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

Если G является неориентированным графом, то его матрица инциденций определяется также как и выше за исключением того, что все элементы, равные - 1 заменяется на + 1.

 

Аналитическое задание графа – перечень всех его вершин и дуг:

Пути и маршруты

 

(1)   (2) (3) (1)-(3)-пути  
Путем(ориентированным маршрутом) орграфа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

 

 


Дуги Uk=(Xi,Xj) и Ul=(Xj,Xr), имеющие общие концевые вершины, называются смежными.

Две вершины Xi и Xj называются смежными, если какая-нибудь из двух дуг (Xi , Хj) и (или) (Xj , Xi) одновременно присутствуют в графе. Например, дуги U1,U10 и U3,U6; вершины Х35, смежны.

Дуги U1,U8 и вершины Х14 не являются смежными.

Орцепьюназывают такой путь, в котором каждая дуга используется не более одного раза. Например, (1) и (2) - орцепь; (3) - не орцень, т.к. U6, - дважды включена в путь.

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

Маршрутомназывают последовательность ребер U1, U2…Un, в которой каждое ребро Ui, за исключением первого и последнего ребер, связано с ребрами Ui-1 и Ui+1 своими двумя концевыми вершинами. Различают простые и элементарные маршруты

Маршруты:

Черта над символом означает.

что ориентацией пренебрегают

 

Пример 3.1. Записать граф G = (X,U) аналитически, построить матрицы смежности, инциденций, пропускных способностей дуг и достижимостей. Определить экстремальные значения путей и маршрутов.

 

 
 

 


Решение.

1. Запишем граф G = (U, X) аналитически X = (Xi, Х2, X3, X4, X5. X6)

U=( U1=(X1,X2);U2=(X2,X3);U3=(X2,X4);U4=(X3,X4);U5=(X5,X4);

U6 =(X4,X6);U7=(X6, X5);U8=(X1, X5);U9=(X5,X5)), где X - множество вершин, a U - множество дуг.

2.Строим матрицу смежности А.g.

 

    X1 X2 X3 X4 X5 X6      
  X1   2  
  X2    
A= X3   α+=9
  X4  
  X5    
  X6    
          α-=9

где α- и α+ полустепени исхода и полустепени захода вершин Хj соответственно.

3.Составляем матрицу инциденций В= { bik }. Матрица инциденций В

–это прямоугольная матрица размером m x n , где m – число вершин, n – количество дуг, элементы которой определяются:

 
 


1, если Xi является начальной вершиной дуги Uk

bik =, -1. если Xi является конечной вершиной дуги Uk

0, если Xi не является вершиной дуги Uk

2, если Uk является петлей.

 

    U1 U2 U3 U4 U5 U6 U7 U8 U9
  X1
  X2 -1
B= X3 -1
  X4 -1 -1 -1
  X5 -1 -1
  X6 -1

 

3. Составляем матрицу пропускных способностей дуг С={cik}, которая строится на основе матрицы смежности A, заменяя элементы равные 1 соответствующим значением пропускной способности дуги.

4.

    X1 X2 X3 X4 X5 X6
  X1
  X2
C= X3
  X4
  X5
  X6

 

5. Строим матрицу достижимостей D= {dik}, которая определяется следующим образом:

 

dik=
1, если вершина Хk достижимы из Xi,

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

 

    X1 X2 X3 X4 X5 X6
  X1
  X2
D= X3
  X4
  X5
  X6

 

6. Определяем пути их Х в Х , (без учета петли)

 

 

Сети

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

P(V)=P(W)=0

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

C ( ν) ≥ 0, называемое пропускной способностью дуги ν (рис 2.8)

Рис.2.8

Поток сети - это некоторая функция ϕ (ν), удовлетворяющая условиям:

1)φ(ν) ≥ 0, (ν 󠅳 V);

2)φ(ν) ≤ С (ν);

3)∑ φ (ν) - ∑ φ (ν) = 0

ν V ν V

 

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

∑ φ(ν) - ∑ φ (ν) = Ф

ν V ν V

где ϕ - величина суммарного потока через вершину .

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

1) A ≠B, A x и B x;

2) V A;

3) W B.

Следовательно, в подмножестве А содержится вход сети и некоторые промежуточные вершины. Подмножество В, содержит все остальные вершины и в том числе выход сети W.

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

С ( ) = ∑ C (ν), ν

Например, разрез Ӏ (рис. 2.8) определяется множеством верши

A = { }, B = { }, дуг = {( }

Пропускной способностью

C ( ) =

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

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

= С ( .

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

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

Пример 3.2. определить величину максимального потока и указать минимальный разрез для сети (рис. 3.4.)

Рис. 3.4

Решение.

1. Составим матрицу пропускных способностей дуг для сети (рис.3.4)

    X1 X2 X3 X4 X5 X6
  X1      
  X2        
= X3        
  X4          
  X5        
  X6            

Укажем один из путей из вершины в вершину . Например, , отмечаем значения соответствующих пропускных способностей дуг в матрице чертой над числами: . Определим минимальное из них, т.е. Величину вычитаем из чисел {6,5,10} в матрице , получим матрицу .

   
       
           
       
           
         
             
                 

Рассмотрим второй путь из в , т.е. , отмечаем значения соответствующих пропускных способностей дуг в матрице чертой над числами: . Определим минимальное из них, т.е. = 1. Величину вычитаем из чисел {1, 3, 12} в матрице , получим матрицу .

   
         
           
       
           
         
             

Аналогично получаем остальные матрицы.

   
           
           
       
           
         
             

   
           
           
         
           
         
             
                 

   
           
           
           
           
         
             

 

   
       
         
       
           
           
             

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

 

сеть с максимальным потоком.

Рис. 3.5.

Минимальным разрезом является величина (рис.3.4)

 

Равновесие узлов проверяем на сети с максимальным потоком:

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

 



Последнее изменение этой страницы: 2016-12-27; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.215.177.171 (0.013 с.)