Анализ дерева, сгенерированного BFS

Question

Я думал о том, чтобы задать этот вопрос в Mathexchange, но речь идет не о вычислениях и да / нет, а об алгоритме, связанном с информатикой, поэтому я задаю его здесь.

В алгоритме BFS каждый уровень обхода можно пометить как слои. Например, если s является начальной версией, все вершины в любом отдельном слое должны иметь одинаковое расстояние до s. Это одна из основных характеристик алгоритма поиска BFS.

Предположим, что есть i слоев и дерево, сгенерированное алгоритмом BFS, которое будет называться T, и граф, который будет называться G. Это означает, что максимальное расстояние между любыми 2 узлами в T будет i. (вероятно один из начального слоя и один из нижнего слоя)

Используя это свойство, как мне доказать, что существует вершина a в G такая, что ее степень будет не более 6*|V|/i?

Я думал, что поскольку у любой вершины u в Слой L_j есть ребра, связанные с вершинами в слоях L_j-1 и L_j+1, показывая существование 3 последовательных слоев с общим количеством не более 6|V|/i вершин. помог бы.

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

Answer 1

Подход, вероятно, должен быть следующим: взять тройки слоев (например, [1,2,3], [4,5,6] ...).Их i/3, и они не пересекаются.Вместе они имеют V вершин, что означает, что должен быть триплет с <= V/(i/3) из них (в противном случае ... считайте это).Тем не менее, этот подход приводит к максимальному 3V/i градусу.

Может быть, i должен быть диаметром (я назову его m как Максимальное расстояние между двумя вершинами. Меня смущает вашаоператор

максимальное расстояние между любыми двумя узлами в T было бы i.

, что неверно - для некоторых вершин вы должны идти вверх, а затем вниз).Тогда m будет <= 2*i, что приведет к вершинам со степенью не более 6V/m.