Способи перевірки зв’язності графу

Існує кілька способів перевірки зв’язності графу. По-перше, можна скористатися означенням, тобто перевірити, чи існує для будь-яких вершин u та v даного графу маршрут між цими вершинами. По-друге, якщо маємо граф скінченного порядку, можна побудувати матрицю досяжності цього графу, користуючись операціями  та . По-третє, можна використати теорему 3, тобто перевірити, чи можна подати даний граф у вигляді диз’юнктивного об’єднання двох його підграфів. Якщо граф подано у вигляді діаграми, перевірити його зв’язність, очевидно, дуже легко.

Неорієнтовані графи та бінарні відношення

Твердження 6. Нехай V – непорожня множина. Тоді між множиною неорієнтованих графів з множиною вершин V та множиною бінарних симетричних відношень, заданих на множині V, існує взаємно однозначна відповідність.

Доведення. Нехай задано граф G=(V,E). Побудуємо на множині V бінарне відношення R_G таким чином: xR_Gy  x та y суміжні (тобто E містить ребро (x,y)). Відношення R_G симетричне, оскільки xR_Gy  x та y суміжні  y та x суміжні  yR_Gx.

Нехай на непорожній множині V задано бінарне симетричне відношення R. Побудуємо граф G_R таким чином: за множину вершин графу візьмемо множину V, а за множину ребер – множину {(u,v)| <u,v>R}.

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

Розглянемо приклади. Нехай задано граф G=({1,2,3,4},{(1,1),(1,3),(2,3), (3,4)}). Побудуємо відношення R_G на множині V. Для цього переглянемо ребра графу G й знайдемо усі пари суміжних вершин. Суміжними є вершини 1 та 1, 1 та 3, 3 та 1, 2 та 3, 3 та 2, 3 та 4, 4 та 3. Отже, відношення R_G має вигляд: R_G={<1,1>,<1,3>,<3,1>,<2,3>,<3,2>,<3,4>,<4,3>}. Нехай тепер на множині {1,2,3,4} задано бінарне відношення R={<3,2>,<1,4>,<4,2>,<4,1>,<2,3>,<2,4>}. Це відношення симетричне, отже, можна подати його у вигляді такого неорієн-тованого графу: G_R=({1,2,3,4},{(3,2),(1,4),(2,4)}). Ребро (3,2) (неупорядкована пара вершин 3 та 2) графу побудовано за допомогою упорядкованих взаємно обернених пар <3,2> та <2,3> відношення R. Ребра (1,4) та (2,4) побудовані аналогічним чином.

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

1. Що таке: а) маршрут (замкнутий маршрут, ланцюг, простий ланцюг) між парою вершин графу, б) цикл (простий цикл) у графі, в) зв’язний граф?

2. Які існують способи обчислення кількості маршрутів заданої довжини між парою вершин графу?

3. Що таке: а) підграф графу, б) кістяковий підграф графу, в) компонент зв’язності графу?

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

5. Яка є необхідна й достатня умова зв’язності графу?

6. Які є способи перевірки зв’язності графу?

7. Які є способи подання незв’язних графів?

8. Як подати бінарне симетричне відношення, задане на деякій непорожній множині, за допомогою неорієнтованого графу?

9. Як подати неорієнтований граф у вигляді бінарного відношення?