Каково максимальное количество ребер в ориентированном графе с n узлами?

Ответ 1

Если у вас есть N узлы, есть N - 1 направленные ребра, которые могут привести к нему (переход к любому другому node). Поэтому максимальное число ребер N * (N - 1).

Ответ 2

В неориентированном графе (за исключением мультиграфов) ответ n * (n-1)/2. В ориентированном графе ребро может встречаться в обоих направлениях между двумя узлами, тогда ответ будет n * (n-1).

Ответ 3

Направленный график:

Вопрос. Какое максимальное количество ребер в ориентированном графе с n вершинами?

• Предположим, что нет автопилот.
• Предположим, что существует не более одного ребра из заданной начальной вершины в заданную конечную вершину.

Каждый ребро задается начальной вершиной и конечной вершиной. Нет выбор для начальной вершины. Поскольку нет самообучений, есть n-1 для конечной вершины. Умножение их вместе учитывает все возможные варианты.

Ответ: n(n−1)

Неадресный график

Вопрос. Какое максимальное количество ребер в неориентированном графе с n вершинами?

• Предположим, что нет автопилот.
• Предположим, что существует не более одного ребра из заданной начальной вершины в заданную конечную вершину.

В неориентированном графе каждое ребро задается двумя его конечными точками и порядок не имеет значения. Следовательно, число ребер является числом подмножеств размера 2, выбранных из множества вершин. Поскольку множество вершины имеют размер n, число таких подмножеств задается формулой биномиальный коэффициент C (n, 2) (также известный как "n выбрать 2" ). Используя формула для биномиальных коэффициентов, C (n, 2) = n (n-1)/2.

Ответ: (n*(n-1))/2

Ответ 4

В дополнение к интуитивному объяснению, предоставленному Крисом Смитом, мы можем рассмотреть, почему это имеет место с другой точки зрения: рассмотрение неориентированных графов.

Чтобы понять, почему в столбце DIRECTED ответ равен n*(n-1), рассмотрите неориентированный граф (что просто означает, что если есть связь между двумя узлами (A и B), тогда вы можете пойти в обоих направлениях: от A до B и от B до A). Максимальное количество ребер в неориентированном графе n(n-1)/2 и, очевидно, в ориентированном графе в два раза больше.

Хорошо, спросите вы, но почему существует максимум n(n-1)/2 ребер в неориентированном графике? Для этого рассмотрим n точек (узлов) и спросим, ​​сколько ребер можно сделать из первой точки. Очевидно, n-1 ребра. Теперь, сколько ребер можно извлечь из второй точки, учитывая, что вы подключили первую точку? Поскольку первая и вторая точки связаны с уже, существует n-2 ребра, которые можно выполнить. И так далее. Таким образом, сумма всех ребер равна:

Sum = (n-1)+(n-2)+(n-3)+...+3+2+1 

Так как в сумме есть члены (n-1), а средний суммы в таком ряду - ((n-1)+1)/2 {(последний + первый)/2}, Sum = n(n-1)/2

Ответ 5

Если граф не является мультиграфом, то, очевидно, n * (n - 1), так как каждый node может иметь не все ребра для всех остальных node. Если это мультиграф, то максимальный предел отсутствует.

Ответ 6

Другими словами:

Полный граф - это неориентированный граф, где каждая отдельная пара вершин имеет единственное ребро, соединяющее их. Это интуитивно понятно в том смысле, что вы в основном выбираете 2 вершины из набора из n вершин.

nC2 = n!/(n-2)!*2! = n(n-1)/2

Это максимальное количество ребер, которое может иметь неориентированный граф. Теперь для ориентированного графа каждое ребро преобразуется в два направленных ребра. Поэтому просто умножьте предыдущий результат на два. Это дает вам результат: n (n-1)

Ответ 7

В ориентированном графе, имеющем N вершин, каждая вершина может подключаться к N-1 другим вершинам в графе (предположим, ни одна петля). Следовательно, общее число ребер может быть N (N-1).

Ответ 8

Правильный ответ: n * (n-1)/2. Каждый ребро подсчитывается дважды, следовательно, деление на 2. Полный граф имеет максимальное количество ребер, которое задается п, выбирает 2 = n * (n-1)/2.

Ответ 9

В графе может быть не более n(n-1)/2 ребер, если не разрешено многократное ребро.

И это достижимо, если мы помечаем вершины 1,2,...,n и там ребро от i до j iff i>j.

Смотрите здесь.

Ответ 10

Несправлено N ^ 2. Простой - каждый node имеет N опций ребер (включая себя), всего N узлов, таким образом, N * N

Ответ 11

В графе с циклом self

max edges= n*n

например, у нас есть 4 узла (вершина)

4 nodes = 16 edges= 4*4

Ответ 12

Что такое турнир?

Простой полный ориентированный граф - турнир.

Вы можете найти его в интернете...

Турнир имеет N * (N-1)/2 ребра... Таким образом, правильный ответ должен быть N * (N-1)/2.

Ответ 13

Можно также рассматривать как количество способов выбора пар узлов n выбрать 2 = n (n-1)/2. Истина, если только любая пара может иметь только одно ребро. Умножьте на 2 иначе