Как доказать индукцией, что сильно связанный ориентированный граф имеет не более 2n -2 ребер? - PullRequest
Новая
       9

Как доказать индукцией, что сильно связанный ориентированный граф имеет не более 2n -2 ребер?

1 голос
/ 17 ноября 2011

У меня есть ориентированный граф, который сильно связан, но удаление любого ребра из него делает граф более не сильно связанным.

Как я могу доказать, что такой граф имеет не более 2n - 2 ребер?(где n ≥ 3)

Я искал литературу пару дней, но, похоже, такого доказательства никогда не было.Любые советы приветствуются.

Ответы [ 3 ]

2 голосов
/ 17 ноября 2011

Вот один набросок (детали опущены, чтобы полностью не испортить экзаменационный вопрос).

  1. Докажите, что граф G имеет простой цикл C.
  2. Докажите, что каждая дуга в Gчей хвост и голова принадлежат V (C), принадлежит C.
  3. Докажите, что G / C (граф, полученный из G путем сжатия каждой дуги в C) сильно связан и что для всех дуг e в G /C, подграф G / C - e не сильно связан.
  4. С помощью сильной индукции заключите, что G имеет не более 2 | V (G) |- 2 дуги.
0 голосов
/ 06 июня 2019

Насколько я понимаю, вы можете доказать это конструктивно, используя очень простой алгоритм, и, возможно, это поможет пролить некоторый свет на возможное доказательство по индукции.

  1. Сначала вы подбираетепроизвольный узел r и запустить BFS из него - то, что вы получите, является ориентированным деревом с ровно n-1 ребрами и n вершинами (все достижимы из r).

  2. Теперь получите транспонированный граф(G ^ T) из оригинала и снова запустите BFS из r - вы получите ориентированное дерево с ровно n-1 ребрами и n вершинами (все достижимы из r).

  3. Наконец, осмотрите каждое ребро в более позднем дереве и добавьте его (в обратном порядке) к первому дереву (только если его еще нет).Этот шаг гарантирует, что r достижима из каждой вершины графа, и так как каждая вершина достижима из r - вы получите сильно связанный остовный подграф.

    • Обратите внимание, что мы добавили вбольшинство n-1 ребер первого дерева с n-1 для начала - и, следовательно, в результирующем графе не более n-1 + n-1 = 2n-2 ребер.
0 голосов
/ 17 ноября 2011

Это неправда. Доказательство контрпримером. Граф имеет узлы A, B и C

  • A -> B
  • B -> A
  • A -> C
  • B -> C
  • C -> B

Это сильно связано.

Если я удалил C-> B, то C изолирован (от него ничего не получится) и не сильно связан. Таким образом, я представил график, который:

  1. Сильно связан
  2. Имеет более 2n-2 узлов
  3. Если я уберу один край, он больше не будет сильно связан
...