Каково значение суммы минимальной степени и максимальной степени направленного ациклического графа?

Question

Каково значение суммы минимального и максимального выходного градуса Направленного ациклического графа?

a) Зависит от графика
b) Всегда будет нулевым
в) всегда будет больше нуля
г) может быть ноль или больше нуля

Answer 1

Мы можем разбить это на две части: минимальная степень и максимальная степень выхода.

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

Максимальный выходной градус графика может быть нулевым или любым другим положительным числом.

Два патологических примера DAG, которые иллюстрируют диапазон максимального выхода-степени:

1. отдельный узел (in-степень = out-степень = 0), поэтому мы знаем, что эта сумма может быть 0.

2. звезда с одним узлом, соединенным с N-1 другими узлами (минимальный входной градус = 0, максимальный выходной градус = N-1)

Таким образом, это предполагает, чтоа) или г) верны.