Що таке однозв’язний граф?

Орієнтований граф D однозв’язний якщо для кожної впорядкованої пари вершин (s,t) існує щонайбільше один шлях від s до t у D.3 червня 2023 р

Зокрема, ми говоримо, що орієнтований граф є однозв’язним якщо між кожною парою вершин існує щонайменше один простий шлях. Якщо є два різних простих шляху, що з’єднують будь-які дві вершини, граф не є одноз’єднаним.

Однозв’язним графом є орієнтований граф, який має щонайбільше 1 шлях від u до v ∀ u,v.

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

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

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