What is the formula for the density of a multigraph (both undirected and directed)?
$begingroup$
in the following answer https://math.stackexchange.com/a/1526421/28816 there are two formulas for computing the density of, respectively, simple undirected and simple directed graphs.
Simple undirected graphs:
$$D = frac{2|E|}{|V|(|V| - 1)}$$
Simple directed graphs:
$$D = frac{|E|}{|V|(|V| - 1)}$$
Now, I was thinking about multigraphs. How is the density of such graphs computed? What would be the formula for the density of, respectively, an undirected and directed multigraph which has multiple edges and possibly loops?
Thank you for the attention.
graph-theory
asked Mar 11 at 7:44
user3019105user3019105
324111
$endgroup$
add a comment |
$begingroup$
in the following answer https://math.stackexchange.com/a/1526421/28816 there are two formulas for computing the density of, respectively, simple undirected and simple directed graphs.
Simple undirected graphs:
$$D = frac{2|E|}{|V|(|V| - 1)}$$
Simple directed graphs:
$$D = frac{|E|}{|V|(|V| - 1)}$$
Now, I was thinking about multigraphs. How is the density of such graphs computed? What would be the formula for the density of, respectively, an undirected and directed multigraph which has multiple edges and possibly loops?
Thank you for the attention.
graph-theory
asked Mar 11 at 7:44
user3019105user3019105
324111
$endgroup$
add a comment |
$begingroup$
in the following answer https://math.stackexchange.com/a/1526421/28816 there are two formulas for computing the density of, respectively, simple undirected and simple directed graphs.
Simple undirected graphs:
$$D = frac{2|E|}{|V|(|V| - 1)}$$
Simple directed graphs:
$$D = frac{|E|}{|V|(|V| - 1)}$$
Now, I was thinking about multigraphs. How is the density of such graphs computed? What would be the formula for the density of, respectively, an undirected and directed multigraph which has multiple edges and possibly loops?
Thank you for the attention.
graph-theory
asked Mar 11 at 7:44
user3019105user3019105
324111
$endgroup$
in the following answer https://math.stackexchange.com/a/1526421/28816 there are two formulas for computing the density of, respectively, simple undirected and simple directed graphs.
Simple undirected graphs:
$$D = frac{2|E|}{|V|(|V| - 1)}$$
Simple directed graphs:
$$D = frac{|E|}{|V|(|V| - 1)}$$
Now, I was thinking about multigraphs. How is the density of such graphs computed? What would be the formula for the density of, respectively, an undirected and directed multigraph which has multiple edges and possibly loops?
Thank you for the attention.
graph-theory
graph-theory
asked Mar 11 at 7:44
user3019105user3019105
324111
asked Mar 11 at 7:44
user3019105user3019105
324111
asked Mar 11 at 7:44
user3019105user3019105
324111
asked Mar 11 at 7:44
user3019105user3019105
324111
asked Mar 11 at 7:44
user3019105user3019105
324111
324111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$frac{|E|}{f(|V|)}$$
There are $binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$frac{|E|}{sum_{k=2}^n binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$frac{|E|}{sum_{k=2}^n k cdot binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3143407%2fwhat-is-the-formula-for-the-density-of-a-multigraph-both-undirected-and-directe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$frac{|E|}{f(|V|)}$$
There are $binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$frac{|E|}{sum_{k=2}^n binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$frac{|E|}{sum_{k=2}^n k cdot binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
$endgroup$
add a comment |
$begingroup$
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$frac{|E|}{f(|V|)}$$
There are $binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$frac{|E|}{sum_{k=2}^n binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$frac{|E|}{sum_{k=2}^n k cdot binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
$endgroup$
add a comment |
$begingroup$
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$frac{|E|}{f(|V|)}$$
There are $binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$frac{|E|}{sum_{k=2}^n binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$frac{|E|}{sum_{k=2}^n k cdot binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
$endgroup$
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$frac{|E|}{f(|V|)}$$
There are $binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$frac{|E|}{sum_{k=2}^n binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$frac{|E|}{sum_{k=2}^n k cdot binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
edited Mar 11 at 8:25
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
answered Mar 11 at 8:13
Zachary HunterZachary Hunter
1,017313
1,017313
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3143407%2fwhat-is-the-formula-for-the-density-of-a-multigraph-both-undirected-and-directe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
