Talk:Dense graph
From Wikipedia, the free encyclopedia
 |
|||||||||||||||||||||||
| Mathematics rating: | Stub Class | Low Priority | Field: Discrete mathematics | ||||||||||||||||||||
|
|||||||||||||||||||||||
[edit] Definition of "sparse graph"
I removed the following from the article:
- "Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if |E| = O(|V|k) and 2 > k > 1. |E| is the number of edges, and |V| is the number of vertices."
Firstly, it is not clear what Bruno Preiss' definition is. Secondly, the definition is probably wrong; I guess that |E| = O(|V|k) should be |E| = O(|V|k), but I'm not sure. -- Jitse Niesen (talk) 16:27, 29 September 2005 (UTC)
A simple web search answered my question: the article was copied from the NIST website. The article really should include a reference to the original source to avoid charges of plagiarism, even when there are no copyright issues. -- Jitse Niesen (talk) 16:49, 29 September 2005 (UTC)
[edit] Sparse Matrix
One possible definition of a sparse graph is one which can be represented by a sparse matrix. The definition of a sparse graph is often application dependent. A rather simple one is that it has O(|V|) edges. Let's look again at the first example graph:
An edge is a self-loop if it is of the form (u,u). The sample graph contains no self-loops.
A graph is simple if it neither contains self-loops nor contains an edge that is repeated in E. A graph is called a multigraph if it contains a given edge more than once or contain self-loops. For our discussions, graphs are assumed to be simple. The example graph is a simple graph.
An edge (u,v) is incident to both vertex u and vertex v. For example, the edge (1,3) is incident to vertex 3.
The degree of a vertex is the number of edges which are incident to it. For example, vertex 3 has degree 3, while vertex 4 has degree 1.
Vertex u is adjacent to vertex v if there is some edge to which both are incident (that is, there is an edge between them). For example, vertex 2 is adjacent to vertex 5.
A graph is said to be sparse if the total number of edges is small compared to the total number possible ((N x (N-1))/2) and dense otherwise. For a given graph, whether it is dense or sparse is not well-defined by garin
[edit] definition correct?
Is the definition really correct? Applying the current definition means that it is impossible to have a graph density of 1. For full graphs, the limit of the density is 1 as the order approaches infinity, but that's a little different Citrus538 09:44, 20 July 2007 (UTC)
- I'm going to change the definition in a few days if nobody objects. Citrus538 04:06, 27 July 2007 (UTC)
- It's a good point you raise. The first paper I found which defines graph density has another definition which meets your concern, so I replace the unreferenced definition in the article with their definition. If you have a better references, for instance, a text book, then please put it in. -- Jitse Niesen (talk) 14:09, 28 July 2007 (UTC)
- Great! I was just gonna wing it without any references : ) Anyway, I added that the definition applies only for undirected graphs. 68.221.99.78 03:38, 4 August 2007 (UTC)
- Ooops, forgot to log in. That last comment is mine. Citrus538 03:39, 4 August 2007 (UTC)
- It's a good point you raise. The first paper I found which defines graph density has another definition which meets your concern, so I replace the unreferenced definition in the article with their definition. If you have a better references, for instance, a text book, then please put it in. -- Jitse Niesen (talk) 14:09, 28 July 2007 (UTC)
