Блог пользователя Famor100

Автор Famor100, 7 лет назад, По-русски

Как достроить ориентированный граф минимальным количеством рёбер, чтобы с любой вершины можно было добраться до любой другой вершины?

 
 
 
 
  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

По идее так:

1) Найдем компоненты сильной связности.

2) Возьмем какую-то одну компоненту и будем из какой-то ее вершины строить по 2 ребра в вершину каждой другой компоненты(одно ребро из компоненты, другое- в компоненту).

Благодаря этому из каждой компоненты можно будет добраться в каждую(через ту, что мы выбрали на шаге 2), а так как внутри компонент можно попасть в любую вершину, граф действительно станет связным.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    В каждую не нужно, достаточно в одну.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Почему?

      Допустим у нас есть несколько компонент, между которыми нет ни одного ребра. И что нам даст опускание в одну из них?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Извиняюсь, неправильно понял сначала. Но все равно таким образом оптимально не получится.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Это не всегда правильно, допустим у нас есть пустой граф из 5 вершин, тогда выгоднее сделать цикл из 5 вершин и рёбер, а по этому алгоритму у нас получится точно не 5 :)

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Не, глупость сморозила. Не работает в общем случае.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А, если граф не обязательно связный, можно зациклить не связанные компоненты, и этот цикл со всем содержимым сам станет 1 компонентой.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      С циклом также не всё просто, я не придумал как делать оптимально

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    C пустым графом не прокатит)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Пусть у нас есть граф из 2n вершин, что ребро из i-той вершины в j-тую в нём есть тогда и только тогда, когда i принадлежит отрезку [1, n], а j отрезку [n + 1, 2n]. Очевидно, что достаточно n рёбер из (i + n)-той вершины в i-тую при i из отрезка [1, n]. Вашему алгоритму, если я не ошибаюсь, нужно 2n - 1 рёбер (в графе n стоков и n истоков).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, то что описано выше работает только для слабо связного графа. Коммент выше тоже не поможет без доработки.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Какая-то непростая задача, а откуда она?

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

А такой вариант может подойдет? 1) Найдем компоненты сильной связности 2) Сделаем цикл из этих компонент, т.е. по очереди из первой в N-ую компоненту проведем ребра. Возьмем в каждой компоненте любую вершину в которую будет входить ребро из i — 1 компоненты и выходить в i + 1 компоненту. Поправьте, если что не так)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Вот как сделать цикл и есть вопрос, там просто уже расставлены ребра, которые могут помочь, нашему будущему циклу

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Известная задача. Как-то хотел перевод сюда запилить, но руки не дошли

http://www.springer.com/cda/content/document/cda_downloaddocument/9780387235288-c2.pdf

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Вроде бы ответ — это максимум из кол-ва компонент, в которые ничто не входит и из которых ничего не выходит. Ну и понятно, ка строить ответ тогда

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

Эта задачу я в первый раз увидел на тренировке к IOI от KOTEHOK. Тогда её решил только PavelKunyavskiy и это был первый случай решения этой задачи на контесте (о котором знал ставивший нам тренировку). Этой осенью мы дали её на дистанционный тур кандидатам в сборную России, и там её решил только zemen, да и то не успел за время контеста написать полное решение — только на 60 баллов.

Теперь, собственно, решение (пока за "очень долго"). Насколько я понял, оно же в статье выше и описано.

  1. Сконденсировали граф.
  2. Назовём истоками компоненты сильной связности, в которые не входят рёбря, стоками — из которых не выходят рёбра.
  3. Предположили, что ответ — это максимум из количества стоков и истоков (за исключением случая, когда всё и так хорошо). Понятно, что бессмысленно проводить рёбра не из какого-нибудь стока в какой-нибудь исток (потому что если проверили, то давайте каждый из концов опустим/поднимем — станет не хуже).
  4. Построим двудольный граф: одна доля из истоков, другая — из стоков, ребро из A в B, если есть путь из A в B в исходном графе.
  5. Что можно делать с двудольным графом? Конечно же, искать максимальное паросочетание. Нашли.
  6. Пусть нашлось A1 → B1, A2 → B2, .... Если это паросочетание полное, то у нас есть ответ: добавили рёбра B1 → A2, B2 → A3, ....
  7. Теперь пусть неполное. Всё равно добавим рёбра, как в предыдущем пункте и сожмём получившуюся компоненту. Теперь граф имеет вид A1 → X, A2 → X, ..., X → B1, X → B2, .... В таком графе понятно как провести рёбра: провели жадно min(|A|, |B|) рёбер так, чтобы исходящая степень стока/входящая истока не превысила единицы, а затем оставшиеся — как-нибудь.
  8. Вроде всё хорошо, но получился куб. Последнее замечание: мы пользовались несколько менее слабым фактом, чем то, что паросочетание максимально. Нам важно то, что нельзя провести никакой путь из истока в сток, не "задевающий" наши пути-рёбра из паросочетания в скондесированном графе. Если это так, то граф действительно принимает нужный вид после добавления рёбер.
  9. А такое паросочетание найти просто, даже явно строить двудольный граф не надо — просто запустили dfs из всех истоков. Каждый dfs либо нашёл путь в сток (тогда запомнили их как ребро "паросочетания") или не нашёл. Метки снимать не надо. Итого линия.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно делать примерно то же самое, но добавлять по одному ребру, идеологически проще придумать и доказать, что будет работать

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    would you please explain 7,8,9 point in a better way.unable to get that stuff.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

проверить можно тут: http://acm.mipt.ru/judge/problems.pl?problem=098

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain this in English, please?