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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Каждый ребро определяется егоначало вершины и конец вершины.Есть 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

Answer 4

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

В графе с автопетлемой

max edges= n*n

таких как у нас 4 узла (вершина)

4 nodes = 16 edges= 4*4

Answer 9

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

Answer 10

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

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

См. здесь .