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

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

направленного графа:

вопрос: каково максимальное число ребер в ориентированном графе с 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

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

чтобы понять, почему в направлено график ответ 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

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

говоря по-другому:

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

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

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

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

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

и это достижимо, если мы называем вершины 1,2,...,n и края от i до j iff i>j.

посмотреть здесь.

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

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

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