Главная | Обратная связь

Способи подання орієнтованих графів

Нехай G=(V,E) – орграф порядку n. Перенумеруємо вершини орграфу G цілими числами від 1 до n й позначимо v_i вершину з номером i. Матрицею суміжності орграфу G називається матриця A_G порядку n над множиною {0,1}, елемент a_ij (1£i£n, 1£j£n) якої визначається таким чином:

Розглянемо приклад. Нехай G=({a,b,c},{(a,c),(a,b)}). Нехай вершини орграфу пронумеровані таким чином: v₁=a, v₂=b, v₃=c. Оскільки (a,c) – дуга G, то A_G(1,3)=1. Оскільки (a,b) – дуга G, то A_G(1,2)=1. Інших дуг у орграфі G немає, отже, маємо: A_G={<<1,1>,0>,<<1,2>,1>,<<1,3>,1>,<<2,1>,0>, <<2,2>,0>,<<2,3>,0>,<<3,1>,0>,<<3,2>,0>,<<3,3>,0>}.

Зазвичай матриця суміжності орграфу порядку n подається у вигляді таблиці, що має n рядків та n стовпчиків, i-й рядок та i-й стовпчик можуть бути позначені і-ю вершиною (v_i), а на перетині i-го рядка та j-го стовпчика ставиться 1, якщо даний орграф має дугу (v_i,v_j), й 0, якщо дуги (v_i,v_j) у даному орграфі немає (1£i£n, 1£j£n). Нехай, наприклад, G=({a,b,c,d}, {(a,d),(b,b),(b,a),(c,d),(d,b)}). Будемо вважати, що вершини орграфу G пронумеровані таким чином: v₁=a, v₂=b, v₃=c, v₄=d. Тоді матриця суміж-ності A_G орграфу G може бути подана таблицею, зображеною на рис.15,а, або на рис.15,б, або на рис.15,в.

а)	б)	в)
	Рис. 15

Нехай G=(V,E) – орграф порядку n, |E|=m. Матрицею інцидентності орграфу G називається матриця B_G розмірності n´m над множиною {-1,0,1}, елемент b_ij (1£i£n, 1£j£m) якої визначається таким чином:

Розглянемо приклад. Нехай G=({a,b,c,d},{(a,d),(b,a),(b,c),(c,a),(d,c)}). Пронумеруємо вершини та дуги орграфу: v₁=a, v₂=b, v₃=c, v₄=d, e₁=(a,d), e₂=(b,a), e₃=(b,c), e₄=(c,a), e₅=(d,c). Перша вершина (а) є початком першої дуги (тобто дуги (a,d)), а також кінцем (але не початком) другої та четвертої дуг, отже, B_G(1,1)=1, B_G(1,2)=-1, B_G(1,4)=-1. Друга вершина (b) є початком другої та третьої дуг, отже, B_G(2,2)=1, B_G(2,3)=1. Третя вершина (с) є початком четвертої дуги, а також кінцем (але не початком) третьої та п’ятої дуг, отже, B_G(3,4)=1, B_G(3,3)=-1, B_G(3,5)=-1. Четверта вершина (d) є початком п’ятої дуги та кінцем (але не початком) першої дуги, отже, B_G(4,5)=1, B_G(4,1)=-1. Побудуємо матрицю інцидентності B_G орграфу G: B_G={<<1,1>,1>,<<1,2>,-1>,<<1,3>,0>,<<1,4>,-1>,<<1,5>,0>,<<2,1>,0>, <<2,2>,1>,<<2,3>,1>,<<2,4>,0>,<<2,5>,0>,<<3,1>,0>,<<3,2>,0>,<<3,3,>,-1>, <<3,4>,1>,<<3,5>,-1>,<<4,1>,-1>,<<4,2>,0>,<<4,3>,0>,<<4,4>,0>, <<4,5>,1>}.

Зручно подавати матрицю інцидентності графу порядку n з m дугами у вигляді прямокутної таблиці, що має n рядків та m стовпчиків, i-й рядок може бути позначений і-ю вершиною (v_i), j-й стовпчик – j-ю дугою (e_j), а на перетині i-го рядка та j-го стовпчика ставиться 1, якщо i-а вершина є початком j-ї дуги, -1, якщо i-а вершина є кінцем, але не початком j-ї дуги, й 0, якщо i-а вершина та j-а дуга не інцидентні (1£i£n, 1£j£m). Побудована матриця інцидентності B_G орграфу G може бути подана однією з таблиць, зображених на рис.16,а,б,в.

а)	б)	в)
	Рис. 16

Орграф порядку n можна подавати у вигляді діаграми, або рисунку. Для цього треба для кожної вершини орграфу вибрати точку площини й позначити цю точку вершиною орграфу, для кожної дуги (v_i,v_j) орграфу провести відрізок лінії (прямої чи ні), що завершується стрілочкою, так, щоб він з’єднав точки, що означають вершини v_i та v_j, а стрілочка вказувала на точку, що означає вершину v_j, (тобто кінець дуги (v_i,v_j)). Зображення вершин та дуг орграфу на площині будемо надалі називати вершинами та дугами (орієнтованими ребрами). Зазвичай дуги діаграми орграфу є відрізками жорданових ліній, тобто ліній, що не мають самоперетинів. Діаграми орграфів G₁=({a,b,c,d},{(a,a),(a,c),(b,d),(d,c)}) та G₂=({a,b,c,d},{(a,b),(b,c),(c,a),(c,d)}) подані на рис.17,а,б.

а)	б)
Рис. 17