Маршрути незамкнені (ланцюги, шляхи) і замкнені (цикли, контури). Повнота. Зв’язність. Сильна зв’язність
Коли задають або шукають певну послідовність ребер (дуг), то говорять про маршрути у графах..
Означення 2.1.13. Скінченну послідовність ребер (дуг) графа (не обов’язково різних) називають маршрутом довжини п, якщо існує послідовність вершин (не обов’язково різних), таких що .
Вершини і називають кінцевими або термінальними.
Означення 2.1.4. Маршрут називають відкритим або незамкненим, якщо і замкненим у протилежному випадку.
Означення 2.1.5. Незамкнений маршрут, у якого немає ребер (дуг), що повторюються, називають ланцюгом для неорієнтованого і шляхом для орієнтованого графа.
Означення 2.1.6. Замкнений маршрут, у якого немає ребер (дуг), що повторюються, називають циклом для неорієнтованого і контуром для орієнтованого графа.
Кажуть, що граф ациклічний або без контурний, якщо він не має циклів чи контурів.
Наприклад,
– незамкнений маршрут;
– замкнений маршрут;
– ланцюг;
– цикл.
Граф називають повним, якщо будь-які його дві вершини суміжні.
Орієнтований граф G=(Х,Г) називають повним, якщо з того, що слідує, що .
Означення 2.1.7. Неорієнтований граф G=(Х,Г) називають зв’язним, якщо в ньому існує ланцюг між кожною парою вершин.
Властивості зв’язних графів:
1) граф зв’язний тоді і тільки тоді, коли множину його вершин не можна розбити на дві непорожні підмножини та так, що дві граничні точки кожного ребра були в одній і тій самій множині;
2) у зв’язному графі довільні два шляхи максимальної довжини мають спільну вершину;
3) якщо граф G=(Х,Г) – зв’язний, то граф G’=(Х,Г-u), отриманий в результаті видалення циклічного ребра и, також зв’язний.
Означення 2.1.8. Орієнтований граф називають зв’язним, якщо зв’язним є неорієнтований граф, що лежить в його основі.
Означення 2.1.9. Орієнтований граф G=(Х,Г) називають сильно зв’язним, якщо для кожної пари різних вершин і існує шлях з до і навпаки – з до .
Дата добавления: 2014-12-22; просмотров: 1365;