Способи подання графів
Загальним способом подання графу є подання його у вигляді упорядкованої пари множин. Таким способом подаються як скінченні, так й нескінченні графи. Для подання скінченних графів користуються матрицями суміжності, матрицями інцидентності та діаграмами. Нехай G=(V,E) – граф порядку n. Матрицею суміжності графу G називається матриця AG порядку n над множиною {0,1}, елемент aij (1£i£n, 1£j£n) якої визначається таким чином: Розглянемо приклад. Нехай G=({a,b,c},{(a,c),(a,b)}). Нехай вершини графу пронумеровані таким чином: v1=a, v2=b, v3=c. Отже, суміжними є перша та третя вершини (тобто a та c), а також перша та друга вершини (тобто a та b). Тоді AG(1,3)=1, AG(3,1)=1, AG(1,2)=1, AG(2,1)=1 й AG={<<1,1>,0>,<<1,2>,1>, <<1,3>,1>,<<2,1>,1>,<<2,2>,0>,<<2,3>,0>,<<3,1>,1>,<<3,2>,0>,<<3,3>,0>}. За-звичай матриця суміжності графу порядку n подається у вигляді таблиці, що має n рядків та n стовпчиків, i-й рядок та i-й стовпчик можуть бути позначені і-ю вершиною (vi), а на перетині i-го рядка та j-го стовпчика ста-виться 1, якщо i-а та j-а вершини суміжні, й 0, якщо ці вершини не суміжні (1£i£n, 1£j£n). Нехай, наприклад, G=({a,b,c,d},{(a,d),(b,b),(b,a),(c,d),(d,b)}). Будемо вважати, що вершини графу пронумеровані таким чином: v1=a, v2=b, v3=c, v4=d. Тоді матриця суміжності AG графу G може бути подана таблицею, зображеною на рис.1,а, або на рис.1,б, або на рис.1,в.
Нехай G=(V,E) – граф порядку n, |E|=m. Матрицею інцидентності графу G називається матриця BG розмірності n´m над множиною {0,1}, елемент bij (1£i£n, 1£j£m) якої визначається таким чином: Розглянемо приклад. Нехай G=({a,b,c,d},{(a,d),(b,a),(b,c),(c,a),(d,c)}). Пронумеруємо вершини та ребра графу: v1=a, v2=b, v3=c, v4=d, e1=(a,d), e2=(b,a), e3=(b,c), e4=(c,a), e5=(d,c). Ребро e1 інцидентне першій та четвертій вершинам, e2 – другій та першій, e3 – другій та третій, e4 – третій та першій, e5 – четвертій та третій. Отже, BG(1,1)=1, BG(4,1)=1, BG(2,2)=1, BG(1,2)=1, BG(2,3)=1, BG(3,3)=1, BG(3,4)=1, BG(1,4)=1, BG(4,5)=1, BG(3,5)=1. Побудуємо матрицю інцидентності BG графу G: BG={<<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-й рядок може бути позначений і-ю вершиною (vi), j-й стовпчик – j-м ребром (ej), а на перетині i-го рядка та j-го стовпчика ставиться 1, якщо j-те ребро інцидентне i-й вершині графу G, й 0 у протилежному випадку (1£i£n, 1£j£m). Побудована матриця інцидентності BG графу G може бути подана однією з таблиць, зображених на рис.2,а та 2,б.
Граф порядку n можна подавати у вигляді діаграми, або рисунку. Для цього треба для кожної вершини графу вибрати точку площини й позначити цю точку вершиною графу, для кожного ребра (vi,vj) графу провести відрізок лінії (прямої чи ні) так, щоб він з’єднав точки, що означають вершини vi та vj. Зображення вершин та ребер графу на площині будемо надалі називати вершинами та ребрами. Зазвичай ребра діаграми графу є відрізками жорданових ліній, тобто ліній, що не мають самоперетинів. Діаграми графів G1=({a,b,c,d},{(a,a),(a,c),(b,d),(d,c)}) та G2=({a,b,c,d},{(a,b),(b,c),(c,a),(c,d)}) подані на рис.3,а та 3,б.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|