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

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

Існує кілька способів перевірки зв’язності графу. По-перше, можна скористатися означенням, тобто перевірити, чи існує для будь-яких вершин 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. Як подати неорієнтований граф у вигляді бінарного відношення?

 

Задачі та вправи

І. Для графу G=({1,2,3,4,5},{(1,2),(1,3),(2,3),(3,4),(3,5),(4,5)}) визначити: а) чи існує маршрут (ланцюг, простий ланцюг) довжини k між вершинами u та v.

1) k=3, u=1, v=2; 2) k=3, u=4, v=5; 3) k=4, u=1, v=3;

4) k=4, u=2, v=4, 5) k=5, u=1, v=2; 6) k=7, u=1, v=4.

ІІ. Задано граф G=({1,2,3,4,5},{(1,2),(2,3),(2,4),(2,5),(3,4),(4,5)}). Знайти: а) усі упорядковані пари вершин v та u графу G такі, що v досяжна з u; б) усі прості ланцюги між вершинами 1 та 4; в) усі ланцюги між вершинами 5 та 1; г) усі прості цикли (з точністю до циклічного зсуву).

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

ІV. Для графу G=({1,2,3,4,5},{(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)}) визначити: а) кількість маршрутів довжини 4 між вершинами 1 та 5;

б) кількість маршрутів довжини не більше 4 між вершинами 2 та 3;

в) кількість маршрутів довжини 4 у графі G; г) кількість маршрутів довжини не більше 4 у графі G.

V. Перевірити, чи правильне твердження.

1) Якщо деякий ланцюг, що з’єднує вершину v з вершиною w, проходить через вершину u (u¹v та u¹w), то цей ланцюг містить простий ланцюг, що з’єднує v з w й проходить через u.

2) Якщо у графі G для деяких трьох різних вершин v, w та u існують прості ланцюги, один з яких з’єднує v з w, а другий – w з u, то у графі G є простий ланцюг, що з’єднує v з u й проходить через w?

VІ. Довести, що будь-який найкоротший ланцюг, що з’єднує вершини v та w (v¹w), є простим ланцюгом.

VІІ. Довести, що у графі, усі прості цикли якого мають парну довжину, немає жодного циклу непарної довжини.

VІІІ. Довести, що будь-який циклічний маршрут непарної довжини містить простий цикл. Чи правильне аналогічне твердження для циклічних маршрутів непарної довжини?

ІХ. Для графу G=({1,2,3,4,5},{(1,3),(2,3),(2,5),(3,4),(3,5),(4,5)}) знайти:

а) усі підграфи порядку 2; б) усі підграфи з двома ребрами; в) усі ациклічні підграфи порядку 3; г) усі зв’язні власні підграфи; д) усі незв’язні підграфи, що мають принаймні один цикл; е) усі зв’язні ациклічні підграфи; є) усі кістякові підграфи.

Х. Задано граф G=({1,2,3,4,5,6},{(1,2),(2,3),(1,4),(3,4),(2,4),(4,5),(4,6)}).

Скільки існує: а) ланцюгів між вершинами 2 та 6 графу G, б) кістякових підграфів графу G, що мають вершини степеня 3, в) простих циклів (з точністю до перестановки вершин) у графі G?

ХI. На заданій множині А побудувати відношення еквівалентності та подати його у вигляді графу. Побудований граф подати у вигляді диз’юнктивного об’єднання компонентів зв’язності.

1) А={1,2,3,4}; 2) A={a,b,c,d,e}; 3) A={,­,®,¯,Þ,Ü};

4) A=Z; 5) A={n| nÎN, n>10}; 6) A={x| x – птах};

7) A={x| x – зірка}; 8) А=С; 9) А={x| x – місто України}.

ХІI. Довести наслідок теореми 1: якщо G=(V,E) – граф порядку n, А_G – матриця суміжності G, то маршрут між i-ю та j-ю вершинами графу G існує тоді й тільки тоді, коли елемент c_ij матриці C= А_G¹ + …+ А_Gⁿ відмінний від нуля.

XІІІ. Довести твердження 4.

ХІV. Нехай G – граф, G¢ – його доповнення. Довести, що принаймні один з цих графів зв’язний.

ХV. Нехай граф G=(V,E) зв’язний, eÎE. Довести, що

а) граф G-e зв’язний, якщо ребро e належить циклу у графі G;

б) граф G-e незв’язний й має тільки два компонента зв’язності, якщо ребро e не входить у жодний цикл у графі G.

ХVІ. Нехай G=(V,E) – зв’язний граф без петель, який не є повним. Довести, що у G існують три такі вершини u, v та w, що (u,v)ÎE й (v,w)ÎE, однак (u,w)ÏE.

ХVІІ. Довести, що у зв’язному графі будь-які два прості ланцюги максимальної довжини мають принаймні одну спільну вершину. Чи правильно, що вони завжди мають спільне ребро?

ХVІІІ. Нехай у простому графі G порядку n степінь кожної вершини не менший від (n-1)/2. Довести, що граф G зв’язний.

ХІХ. Довести, що коли у простому графі G порядку n кількість ребер більша ніж (n-1)(n-2)/2, то граф G зв’язний.

 

ІЗОМОРФНІ ГРАФИ