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

     Пример  4.  Дан неориентированный помеченный граф G₁(V₁; E₁). Построить изоморфные ему графы. 

v₃

v₄

v₆

v₁

v₂

v₅

G₁(V₁; E₁) - граф

 

     Решение.

u₁

u₂

u₃

u₄

u₅

u₆

x₁

x₂

x₃

x₄

x₅

x₆

G₂(V₂; E₂) – граф

Изоморфизм f : G₁®G₂

   f (v₁)=u₁          f (v₄)=u₄       f (v₁; v₂)®(u₁; u₂)

   f (v₂)=u₂          f (v₅)=u₅             и т.д.

   f (v₃)=u₃          f (v₆)=u₆

G₃(V₃; E₃) – граф

Изоморфизм g : G₁®G₃

   g (v₁)=x₁          g (v₄)=x₄       g (v₁; v₂)®(x₁; x₂)

   g (v₂)=x₂          g (v₅)=x₅           и т.д.

   g (v₃)=x₃          g (v₆)=x₆

     , 

     Теорема 1.  Изоморфизм графов есть отношение эквивалентности.

     Доказательство.  Действительно, изоморфизм обладает всеми  необходимыми свойствами отношения  эквивалентности:

     [Рефлексивность.]  G ~ G, где требуемая биекция есть тождественная функция;

     [Симметричность.]  Если G₁ ~ G₂ с биекцией h, то G₂ ~ G₁ с биекцией h^{- 1};

     [Транзитивность.]  Если G₁ ~ G₂ с биекцией h и G₂ ~ G₃ с биекцией g, то G₁ ~ G₃ с биекцией g o h.

     4.  Степень вершин. 

     Определение 10.  Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей. 

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

     Теорема 2. (Теорема Эйлера)  Сумма степеней вершин графа равна удвоенному количеству ребер:

      .

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

     Следствие 1.  Число вершин нечетной степени четно.

     Доказательство.  По теореме Эйлера сумма степеней всех вершин – четное число. Сумма  степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.

     Следствие 2.  Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

      .

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

     Пример  5.  Определить степени вершин данного графа.

v₁

v₂

v₃

v₄

v₅

e₁

e₂

e₃

e₄

e₅

e₅

G(V, E) – граф 

d(v₁)=4          d(v₄)=1

d(v₂)=3          d(v₅)=2

d(v₃)=2 

вершина v₄ - висячая

     ,

     Пример  6.  Определить полустепени исхода и захода данного орграфа.

v₁

v₂

v₃

v₄

v₅

d ^-(v₁)=1        d ^-(v₃)=1         d ^-(v₅)=0

d ⁺(v₁)=1        d ⁺(v₃)=2         d ⁺(v₅)=2 

d ^-(v₂)=2        d ^-(v₄)=2

d ⁺(v₂)=1        d ⁺(v₄)=0 

вершина v₄ – исток

вершина v₅ – сток

 
 
 

     5.  Представление графов в компьютере. 

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

     Определение 12.  Матрица смежности вершин орграфа G, содержащего n вершин-- это квадратная матрица A=[a_ij] n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам орграфа. Элементы a_ij матрицы A равны числу дуг, направленных из i-й вершины в j-ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.

     Матрицей  смежности вершин неориентированного графа G, содержащего n вершин, называют квадратную матрицу A=[a_ij] n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа. Элементы a_ij матрицы A равны числу ребер, направленных из i-й вершины в j-ю. В случае неориентированного графа G ему вместе с ребром (v_i, v_j) принадлежит и ребро (v_j, v_i), поэтому матрица смежности вершин A=[a_ij] будет симметрична относительно главной диагонали. 

     Определение 13.  Матрица смежности дуг орграфа -- это квадратная матрица B=[b_ij] m-го порядка, у которой строки и столбцы матрицы соответствуют дугам орграфа. Элементы b_ij матрицы B равны 1, если дуга e_i непосредственно предшествует дуге e_j и 0 в остальных случаях.

     Матрицей  смежности ребер  неориентированного графа является матрица B=[b_ij] m-го порядка, у которой строки и столбцы матрицы соответствуют ребрам графа. Элементы b_ij матрицы B равны 1, если ребра e_i и e_j имеют общую вершину, и 0 в остальных случаях. 

     Определение 14. Матрицей инциденций (инцидентности) неориентирован-ного помеченного графа с вершинами и ребрами называется матрица размерности , строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы инциденций неориентированного графа равны 1, если вершина инцидентна ребру , и 0 в противном случае.

     Матрицей  инциденций (инцидентности) орграфа с вершинами и дугами называется матрица размерности n´m, строки которой соответствуют вершинам, а столбцы --дугам орграфа. Элементы c_ij равны 1, если дуга e_j исходит из i-й вершины; -1, если дуга e_j заходит в i-ю вершину; 0, если дуга не инцидентна i-й вершине:

     

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

     Пример  7.  1)  Для заданного неориентированного графа построить матрицы смежностей и матрицы инциденций.

v₁

v₂

v₃

v₄

e₁

e₂

e₃

e₄

e₅

     2)  Для заданного ориентированного  графа построить матрицы смежностей  и матрицы инциденций.

v₁

v₂

v₃

v₄

e₁

e₂

e₃

e₄

e₅

 

     Решение.  1)  Строим матрицу смежности вершин, которая будет размерности 4´4. Строим матрицу смежности ребер, которая будет размерности 5´5. 

      ,       .

     Строим  матрицу инциденций, которая будет размерности 4´5. 

      . 

     2)  Строим матрицу смежности вершин, которая будет размерности 4´4. Строим матрицу смежности ребер, которая будет размерности 5´5.

      ,        

     Строим  матрицу инциденций, которая будет размерности 4´5.

      .