Какое максимальное число ребер может быть в графе на 100 вершинах

В двудольном графе, который содержит n вершин в одной доле и m вершин в другой, наибольшее количество рёбер будет тогда, когда каждая вершина из одной доли будет соединена с каждой вершиной в другой доле.
В этом случае количество ребёр будет равно n*m
В нашей задаче известно, что граф содержит 100 вершин.
Пусть количество вершин в одной доле равно n. Тогда в другой доле будет 100 — n вершин.
Количество ребёр тогда равно n(100 — n)
n(100 — n) = -n² + 100n
График полученного выражения — парабола, ветви которой направлены вниз (т.к. коэффициент при n² меньше 0)
Какое наибольшее число рёбер может быть в двудольном графе на 100 вершинах?
В двудольном графе, который содержит n вершин в одной доле и m вершин в другой, наибольшее количество рёбер будет тогда, когда каждая вершина из одной доли будет соединена с каждой вершиной в другой доле.
В этом случае количество ребёр будет равно n*m
В нашей задаче известно, что граф содержит 100 вершин.
Пусть количество вершин в одной доле равно n. Тогда в другой доле будет 100 — n вершин.
Количество ребёр тогда равно n(100 — n)
n(100 — n) = -n² + 100n
График полученного выражения — парабола, ветви которой направлены вниз (т.к. коэффициент при n² меньше 0)
Каково максимальное количество ребер в ориентированном графе с n узлами?
Каково максимальное количество ребер в ориентированном графе с 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 ребра, которые можно выполнить. И так далее. Таким образом, сумма всех ребер равна:
Так как в сумме есть члены (n-1) , а средний суммы в таком ряду — ((n-1)+1)/2 <(последний + первый)/2>, Sum = n(n-1)/2
Ответ 5
Если граф не является мультиграфом, то, очевидно, n * (n — 1), так как каждый node может иметь не все ребра для всех остальных node. Если это мультиграф, то максимальный предел отсутствует.
Ответ 6
Полный граф — это неориентированный граф, где каждая отдельная пара вершин имеет единственное ребро, соединяющее их. Это интуитивно понятно в том смысле, что вы в основном выбираете 2 вершины из набора из n вершин.
Это максимальное количество ребер, которое может иметь неориентированный граф. Теперь для ориентированного графа каждое ребро преобразуется в два направленных ребра. Поэтому просто умножьте предыдущий результат на два. Это дает вам результат: 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
например, у нас есть 4 узла (вершина)
Ответ 12
Что такое турнир?
Простой полный ориентированный граф — турнир.
Вы можете найти его в интернете.
Турнир имеет N * (N-1)/2 ребра. Таким образом, правильный ответ должен быть N * (N-1)/2.
Ответ 13
Можно также рассматривать как количество способов выбора пар узлов n выбрать 2 = n (n-1)/2. Истина, если только любая пара может иметь только одно ребро. Умножьте на 2 иначе
Какое максимальное количество ребер в ориентированном графе с n узлами? [закрыто]
Какое максимальное количество ребер в ориентированном графе с n узлами? Есть ли верхняя граница?
задан 20 фев ’11, 13:02
@LiorKogan как насчет части «алгоритма»? — Loolooii
Извините, но я не вижу никакой части «алгоритма». Просто комбинаторный вопрос — Lior Kogan
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он не о программировании. — Brian Tompsett — 汤莱恩
Я голосую за закрытие этого вопроса, потому что это не проблема программирования. — Nick
12 ответы
Если у вас есть N узлов, есть N — 1 ребра, которые могут быть направлены от него (переходя к любому другому узлу). Следовательно, максимальное количество ребер равно N * (N — 1) .
Верный. Если ребрам разрешено переходить от узла к самому себе, то максимум равен N^2 . — гиперкубᵀᴹ
@MA вы правы, если говорите о неориентированном графе. Однако в ориентированном графе ребро (A, B) не совпадает с ребром (B, A) — Bob9630
N * (N-1) — количество ребер в ориентированном графе. Количество ребер в неориентированном графе (N * (N-1)) / 2 — Чарльз Чоу
то есть в предположении, что граф направлен — молдавский
То же, что и @ypercube, ответ правильный, но не учитывает петли в ориентированном графе. — Альгареку
Направленный график:
Вопрос: Какое максимальное количество ребер в ориентированном графе с 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) / 2. В ориентированном графе ребро может встречаться в обоих направлениях между двумя узлами, тогда ответ будет n * (n-1).
В дополнение к интуитивному объяснению, которое предоставил Крис Смит, мы можем рассмотреть, почему это так, с другой точки зрения: с учетом неориентированных графов.
Чтобы понять, почему в НАПРАВЛЕННЫЙ график ответ n*(n-1) , рассмотрите неориентированный граф (что просто означает, что если есть связь между двумя узлами (A и B), вы можете пойти обоими путями: от A к B и от B к A). Максимальное количество ребер в неориентированном графе равно n(n-1)/2 и, очевидно, в ориентированном графе есть в два раза больше.
Хорошовы можете спросить, но почему есть максимум n(n-1)/2 края в ненаправленный график? Для этого рассмотрим n точек (узлов) и спросим, сколько ребер можно сделать из первой точки. Очевидно, n-1 края. Теперь, сколько ребер можно вывести из второй точки, если вы соединили первую точку? Поскольку первая и вторая точки равны уже подключен, есть n-2 края, которые можно сделать. И так далее. Итак, сумма всех ребер равна:
Так как есть (n-1) в сумме, а в среднем суммы в таком ряду равно ((n-1)+1)/2 <(последний + первый) / 2>, Sum = n(n-1)/2
ответ дан 21 мар ’15, в 20:03

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

Полный граф — это неориентированный граф, в котором каждая пара вершин имеет уникальное ребро, соединяющее их. Это интуитивно понятно в том смысле, что вы в основном выбираете 2 вершины из набора n вершин.
Это максимальное количество ребер, которое может иметь неориентированный граф. Теперь для ориентированного графа каждое ребро превращается в два ориентированных ребра. Так что просто умножьте предыдущий результат на два. Это дает вам результат: п (п-1)
ответ дан 04 дек ’15, 08:12
В ориентированном графе, имеющем N вершин, каждая вершина может соединяться с N-1 другими вершинами в графе (при условии отсутствия петли). Следовательно, общее количество ребер может быть равно N (N-1).
ответ дан 10 авг.
Этот ответ не вносит ничего, чего еще не было в других ответах. Также, /2 для неориентированного графа. — типимм
На графике с петлей
например, у нас есть 4 узла (вершина)
ответ дан 11 мар ’19, в 07:03

Может быть до n(n-1)/2 ребра в графе, если не допускаются мультиреберные.
А это достижимо, если пометить вершины 1,2. n и есть преимущество от i в j тогда и только тогда i>j .
ответ дан 09 окт ’12, 01:10
Ненаправленный — это N ^ 2. Просто — каждый узел имеет N вариантов ребер (включая его самого), всего N узлов, таким образом, N * N
ответ дан 10 мар ’14, в 00:03
N ^ 2 включает повторение направлений, поэтому вы учитываете больше, чем фактические края. <1,2>то же самое, что и <2,1>в неориентированном. В неориентированный граф его n(n-1)/2 . — БагШотGG
Правильный ответ: n * (n-1) / 2. Каждое ребро было подсчитано дважды, отсюда деление на 2. Полный граф имеет максимальное количество ребер, которое равно n select 2 = n * (n-1) / 2.