Мінімальне доповнення до зв’язного графа
Мінімальне доповнення до зв'язного графа
Дано орієнтований граф. Кількість вершин близько десяти четвертої, кількість ребер порядку десяти п'ятої. Потрібно знайти мінімальну кількість ребер так, щоб граф став дуже зв'язковим. Як це зробити? Я розумію, що потрібно розділити граф на компоненти сильної зв'язності, потім підрахувати стільки компонентів немає вихідних ребер і скільки немає вхідних. Відповіддю буде максимум із цих чисел. Проблема в тому, що я не можу зрозуміти, як потім ці ребра збудувати.
Алгоритм вирішення цього завдання заснований на виділенні в конденсації графа витоків, стоків та ізольованих вершин та їх з'єднанні у визначеному порядку. Асимптотика O(n+m). Алгоритм докладно описаний у статті "A Note on Eswaran and Tarjan's Algorithm for Strong Connectivity augmentation problem" (S. Raghavan). В українськомовному сегменті мережі, напевно, нічого адекватного немає.
Мені здається, що можна збудувати таким чином.
Новий граф, представлений у вигляді компонента сильної зв'язності, буде орієнтованим і ациклічним. Проведемо топологічне сортування вершин у новому графі. Знайдемо всі вершини, з яких не можна перейти в іншу вершину, назвемо їх умовно листям. Знайдемо всі вершини, в які не можна перейти з інших вершин, назвемо їх умовно "корінням". Якщо пронумерувати компоненти зв'язності нового графа від 1 до N, то ребра, що шукаються, будуть виглядати таким чином:
"аркуш 1" - "аркуш 2" - . - "лист N" - "корінь N" - "корінь N - 1" - . - "корінь 1". Це дасть можливість дістатися з будь-якої вершини до будь-якої: спуститися до листя, пройти до "листа N", піднятися до "кореня N", пройти до потрібного "кореня", спуститися до вершини, що цікавить.
У вас виходить занадто велика відповідь. Наприклад, у такому графі:
Правильна відповідь - 2 (з'єднати 15 і 24). У вас вийде чотири ребра.
Якщо питання в асимптотиці, то вирішується він викиданням непотрібного, з усіх ребер, що входять в нижню компоненту, достатньо залишити одне, з усіх ребер, що виходять з верхньої компоненти, теж достатньо залишити одне, відповідь же від цього не змінюється. (За фактом, довикидати можна до стану набору кущів, що ростуть ввір, набору кущів, що ростуть вниз і окремих вершин, все це можна з'єднати конструктивно по циклу, а потім доповнивши листя; але вже не потрібно достатньо довикидати ребер до 2 * у вершин.) Далі, з'єднувати за циклом, оскільки ребер мало, то мердж компонент буде швидким.
Чесно кажучи, я не зрозумів про що мова
Нехай у нас є максимальні та мінімальні компоненти сильної зв'язаності, з деяких максимальних можна пройти до деяких мінімальних, тобто. фактично, у нас є дводольний граф, на якому треба вирішити завдання.
Крок 2: (який робити НЕ ПОТРІБНО) побудуємо на графі, що залишився, паросполучення (дуже швидко бо ребер максимум скільки вершин), вершини, які були з чимось з'єднані, а стали ні з чим не з'єднані з'єднаємо з чим-небудь. Тоді в нас вийде граф, що складався з об'єктів трьох видів: окрема вершина, кущ догори, кущ донизу (під кущем розуміється вершина однієї компоненти, з'єднана з кількома вершинами іншої компоненти).
Крок 3: (власне побудова) почнемо з якоїсь вершини меншої з двох компонентів дводольного графа (компонента 1), зберігатимемо список (S) вершин з (компоненти 2), в які ми можемо дійти з цієї вихідної вершини. Додаємо до списку (S) всі вершини, в які ми можемо потрапити з поточної, беремо будь-яку вершину із знову доданих (не зі всього списку S, а саме із знову доданих до списку) і проводимо в ребро вякоюсь із вершин, які з'єднані з якоюсь вершиною не зі списку S. Повторюємо операцію доти, поки список S не покриє всі вершини, у цьому випадку ми замикаємо шлях: з якоїсь знову доданої до S вершини проводимо ребро у вершину, звідки починали подорож. Після цього можна розкидати ребра вже абияк.