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

Вважається, що граф однозначно заданий, якщо задані множини його вершин та ребер і вказані всі зв'язки цих елементів графа, тобто відомо, які вершини і якими ребрами з'єднані.

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

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

Якщо матриця суміжності представляє неорієнтований незважений граф (мал. 17, а), то за наявності суміжності вершин і та j відповідні елементи матриці дорівнюють 1, тобто а[і, j] = а[j, і] = 1, а у разі відсутності ребра між вершинами і та j - 0, тобто а[і, j] = a[j, і] = 0 (мал. 17, б).

Які висновки можна зробити, проаналізувавши цю матрицю суміжності, зображену на малюнку 17, б? По-перше, для не - орієнтованого графа вона є симетричною. По-друге, значення діагональних елементів дорівнюють 0, оскільки у нашому графі відсутні петлі.

Якою ж буде матриця суміжності для інших графів? Якщо матриця суміжності описує зважений орграф, то можлива відсутність симетричності (мал. 19 а, б). У разі, коли в орграфі всі суміжні вершини мають двоорієнтовані ребра (мал. 18, а), то матриця суміжності такого графа (мал. 18, б) збігається з матрицею суміжності для графа, зображеного на малюнку 17, а.

Особливістю незваженого орграфа, у якому присутні ребра-петлі, є те, що для відповідних вершин діагональні елементи матриці суміжності не дорівнюють 0 (мал. 19, а, б). Аналогічною буде ситуація і для неорієнтованих графів.

Розглянемо тепер випадок зваженого графа. Елементи матриці суміжності аі, j, що відповідає такому графу, збігатимуться зі значеннями «ваги» ребер між вершинами і та j (мал. 20, а, б).

Другим способом представлення графа є списки суміжних вершин. У цьому разі для кожної вершини записується список суміжних вершин, який у довільному порядку містить усі суміжні з нею вершини. Графам, зображеним на малюнках 17, а; 18, а; 19, а; 20, а, відповідають списки суміжних вершин, зображені на малюнках 17, в; 18, в; 19, в; 20, в.

Яким способом представлення заданого графа краще за все користуватися? На це запитання можна відповісти тільки стосовно кожного конкретного алгоритму. Звичайно, що обробляти елементи матриці суміжності нам зрозуміліше і простіше. В ній ми одразу можемо дізнатися, чи є дві задані вершини суміжними, яку «вагу» має ребро, що з'єднує дві задані вершини, тощо.

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

Контрольні запитання

1. Який вигляд матиме матриця суміжності графу, який складається з трьох ізольованих вершин?

2. Чи можна задати у вигляді списку суміжних вершин граф, який складається з однієї ізольованої вершини?

3. Чи симетричною буде матриця суміжності орієнтованого графі?

4. У якому випадку матриця суміжності графа міститиме відмінні від нуля числа на діагоналі?