Сколько ребер может быть в Даг?
В направленном ациклическом графе с n вершинами, каково максимально возможное число направленных ребер в нем?
1 ответ:
Предположим N вершин / узлов и рассмотрим построение DAG с максимальными ребрами. Рассмотрим любой данный узел, скажем N1. Максимальное число узлов, на которые он может указывать, или ребер, на этой ранней стадии равно N-1. Выберем второй узел N2: он может указывать на все узлы, кроме самого себя и N1-это N-2 дополнительных ребра. Продолжайте для остальных узлов, каждый из которых может указывать на одно ребро меньше, чем узел до этого. Последний узел может указывать на 0 других узлов.
Сумма всех ребер: (N-1) + (N-2)+.. + 1 + 0 == (N-1) (N)/2