Как вычислить плотность циклического графа?

Question

Я ищу, чтобы найти плотность направленного циклического графа.

Согласно Wikipedia,

Для неориентированного простые графы, плотность графа определяется как:

2 * | E |/(| V | * (| V | - 1))

Для направленные простые графы, плотность графа определяется как:

| E |/(| V | * (| V | - 1))

Но тогда я продолжу читать определение simple graphs:

«Простой граф, в отличие от multigraph, является неориентированным графиком в , который запрещен как несколькими краями, так и .. "

Я смущен, потому что в другой статье упоминаются «направленные» и «неориентированные» простые графики. Теперь простые графики могут быть только ненаправленными? Он также утверждает, что простые графики не могут иметь циклы, поэтому я не был уверен, смогу ли я использовать любую из этих формул на моем циклическом графике.

Далее я расскажу о мультиграфах, но нет упоминания об их плотности.
Плотность ли не что-то, что могло бы быть связано с графиками с циклами?

В первой статье говорится:

«максимальная плотность 1 (для полных графов)»

И, похоже, полных графов является специализированной версией мультиграфов, поэтому я считаю, что расчет плотности должен иметь смысл.

Какую формулу я использую?

Answer 1

Я понимаю ваше замешательство, но это действительно не сложно. Юо просто выбрал непоследовательные определения из разных источников.

Понятие простых графиков для меня не имеет (или немного) действий с направленными или неориентированными графами (и я сделал свою кандидатуру в поле).

Undirected означает, что край не имеет начальной или конечной точки. Это 2-множество (или мультимножество) вершин {a, b} (неотличимых от ребра {b, a}, возможно содержащих одну и ту же вершину дважды {a, a}, которая называется петлей .

Направленный означает, что ребро (также иногда называемое дугой в этом случае) имеет исходную вершину и целевую вершину. Это означает, что это 2-кортеж (a, b), и есть разница между (a, b) и (b, a). Опять же, (a, a) будет петлей.

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

Забудем на данный момент утверждают, что простые графики должны быть неориентированы.

Обратите внимание, что 2. означает, что если в неориентированном графе есть ребро {a, b}, он может не содержать ребра {b, a}, потому что это то же самое ребро. В ориентированном простом графе все еще возможно иметь (a, b) и (b, a).

В настоящее время плотность - это количество ребер, деленное на максимальное количество ребер. В мультиграфе нет максимального количества ребер, и, следовательно, определение, которое вы нашли, работает только для простых графиков.

Простые неориентированные графики имеют не более | V | (| V | -1)/2 ребра, простые направленные графы имеют не более | V | (| V | -1).

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