алгоритм графа, алгоритм аппроксимации

Question

После удаления листьев дерева dfs случайного графа предположим, что число оставшихся ребер равно | S |, мы можем доказать, что совпадение для этого графа будет | S |/2?

Answer 1

Вот доказательство.

Теорема: Пусть T быть любым деревом с i листьями. Существует (|T|-i)/2 совпадение в T.

Доказательство: по индукции. Если T является деревом с i листьями, пусть T' быть деревом, которое получается при удалении всех листьев с T. T' имеет j <= i листья. Аналогично, пусть T'' будет деревом, которое получается при удалении всех листьев от T'. T'' имеет k <= j листья.

Примените теорему по индукции к T'', поэтому существует соответствие размера (|T''|-k)/2 = (|T|-i-j-k)/2 в T''. Набор ребер T-T' содержит не менее j ребер, которые не падают ни к одному ребру в T'', либо друг к другу (выберите один инцидент для каждого листа в T'), поэтому добавьте эти края, чтобы сделать соответствие в T размера (|T|-i+j-k)/2. Начиная с j >= k, это не менее (|T|-i)/2 ребер. QED.

Я прояснил проблемы с полом/потолком с помощью/2, но я подозреваю, что доказательство все равно будет работать, если вы включили их.