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

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

Согласно Википедии,

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

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

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

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

Но затем я перейду к чтению определения простых графиков :

«Простой граф, в отличие от мультиграфа, - это неориентированный граф, в котором запрещены как множественные ребра, так и петли».

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

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

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

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

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

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


graph algorithm data-structures directed-graph cyclic-graph
person Trevor Hickey    schedule 30.11.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Ненаправленный означает, что кромка не имеет начальной или конечной точки. Это 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) ребер.

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

person Bastian J    schedule 30.11.2016
comment
Что касается мультиграфов, какова будет их плотность (как для направленных, так и для неориентированных)? Безопасно ли использовать приведенные выше формулы, упомянутые OP, и предполагать, что оно может быть больше 1? - person tonix; 11.03.2019