Тема 10. Матричне завдання графа, суміжність і інцидентність. Ізоморфізм.

Питання теми

1. Поняття суміжності.

2. Поняття інцидентності.

3. Поняття ізоморфізму.

Основні терміни теми : суміжність, інцидентність, ізоморфізм.

1. Поняття суміжності

Дві вершини v та v  V графа G=(V,E) називають суміжними, якщо вони є кордонними вершинами ребра  . Відношення суміжності на множині вершин графа можна визначити, представив кожне ребро як пару суміжних вершин, таким чином e =(v , v ), k=1,2,...,q. Для неорієнтованих графів такі пари неупорядковані, так що  , а для орграфів - упорядковані, причому v  та v  означають початкову та кінцеву вершини дуги  . Петля при вершині представляється неупорядкованою парою  . Ясно що множина  вершин V разом з означеним на ній відношенням суміжності повністю визначає граф.

   

а)  б)

Рис 1. Графи.

Граф можна представити також матрицею суміжності.  Строки та стовпці цієї матриці відповідають вершинам графа, а її (ij) - елемент дорівнює числу кратних ребер, які зв’язують вершини  та  (чи направлені від вершини  до вершини  для орграфа). Наприклад, для графів, наведених на рис. 1, а) та б), маємо відповідно наступні матриці суміжності:

а)

          1          2          3          4

1        0          1          1          1

2        1          0          1          1

3        1          1          0          1

4        1          1          1          0

б)

          1          2          3

1        2          1          1

2        1          0          1

3        1          1          2

Матриця суміжності неорієнтованого графа завжди симетрична, а орграфа в загальному випадку несиметрична. Неорієнтованим ребрам відповідають пари ненульових елементів, симетричних відносно головної діагоналі матриці, дугам - ненульові елементи матриці, а петлям - ненульові елементи головної діагоналі. У стовпцях та строках, які відповідають ізольованим вершинам, всі елементи рівні нулю. Елементи матриці простого графа рівні 0 або 1, до того ж всі елементи головної діагоналі нульові.

Для зваженого графа, який не має кратних ребер, можливо узагальнити матрицю суміжності таким чином, що кожний її ненульовий елемент дорівнює ваги відповідного ребра чи дуги. Обернено, люба квадратна матриця n-го порядку може бути представлена орграфом з n вершинами, дуги якого об’єднують суміжні вершини і мають ваги, рівні відповідно елементам матриці. Якщо матриця симетрична, то вона може бути представлена неорієнтованим графом.

2. Поняття інцидентності

Якщо вершина  є кінцем ребра  , тоді говорять, що вони інцидентні: вершина  інцидентна ребру  та ребро  інцидентне вершині  . В той час коли суміжність представляє собою відношення  між однорідними об’єктами (вершинами), інцидентність - це відношення між різнорідними об’єктами (вершинами та ребрами). При розгляданні орграфов розрізняють позитивну інцидентність (дуга виходить з вершини)  та негативну інцидентність (дуга заходить в вершину).

 

Рис. 2. Граф.

Розглядаючи інцидентність вершин та ребер (p,q)-графа, можна представити його матрицею інцидентності розміру p на q, рядки якої відповідають вершинам, а стовпці - ребрам. Для неорієнтованого графа елементи цієї матриці визначаються по такому правилу: ij-елемент дорівнює 1, якщо вершина  інцидентна ребру  і дорівнює нулю, якщо  та  не інцидентні. У випадку орграфа ненульовий ij-елемент дорівнює 1, якщо  початкова вершина дуги  , та дорівнює - 1, якщо  - кінцева вершина дуги  . Наприклад, матриця інцидентності графа, наведеного на рис. 2, а має вигляд:

          a          b          c          d          e

1                    1                                 

2        1                      1          1         

3        1          1                                  1

4                               1                      1

5                                           1         

Кожний стовпець матриці інцидентності містить обов’язково два одиничних елемента (для орграфа ці елементи завжди мають різні знаки та рівні відповідно 1 і -1). Кількість одиниць в рядку дорівнюється ступені відповідної вершини (для орграфа кількість позитивних одиниць визначає позитивну ступінь, а кількість негативних одиниць - негативну ступінь). Нульовий рядок відповідає ізольованій вершині, а нульовий стовпець - петлі.

 

3. Поняття ізоморфізму.

На рис. 4 відображені три графа, які з геометричної точки зору цілком різні. Але вони відрізняються тільки накресленням, а відношення інцидентоності для них однакові.

Графи, для яких зберігаються  відношення інцидентності, називають ізоморфними. Матриця інцидентності визначає граф без петель з точністю до ізоморфизма. На її основі можна відобразити різні в геометричному відношенні, але ізоморфні між собою графи, кожний з яких називають геометричною реалізацією.

Графи, які мають однакові креслення та відрізняються лише нумерацією вершин та ребер, не будучи тотожними, являються ізоморфними. Ізоморфні графи,  як правило не відрізняють між собою.

 

Рис. 4. Ізоморфні графи