84:
74:
53:
22:
255:
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. --
213:
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.
206:
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:
330:
This definition does not make any sense at all. The big-O notation is defined on functions. However, for a single graph, the number of nodes and the number of edges are constants (costant functions). That means that, according to the definition,
235:
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
186:
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. --
226:
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
343:
of graphs, which makes more sense, but still the notation is awkward and non-standard. The NIST site refers to a web version of a book by Preiss. Both the NIST site and Preiss' book are not about graph theory.
166:"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 : -->
140:
172:
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|), but I'm not sure. --
339:(because any constant is bigger than any other constant by only a constant factor). The source where the definition seems to directly originate, the NIST site, talks about
223:
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.
372:
130:
367:
106:
220:
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.
270:
Great! I was just gonna wing it without any references : ) Anyway, I added that the definition applies only for undirected graphs.
97:
58:
33:
217:
An edge (u,v) is incident to both vertex u and vertex v. For example, the edge (1,3) is incident to vertex 3.
21:
261:
192:
177:
39:
271:
83:
349:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
345:
89:
73:
52:
326:| the number of vertices, and the letter O refers to the Big O notation (Preiss 1998, p. 534)."
257:
188:
173:
210:
An edge is a self-loop if it is of the form (u,u). The sample graph contains no self-loops.
280:
247:
237:
361:
102:
79:
246:
I'm going to change the definition in a few days if nobody objects.
353:
283:
274:
265:
250:
240:
196:
181:
168:
1. |E| is the number of edges, and |V| is the number of vertices."
15:
310:< 2 and to define a sparse graph to be a graph with |
279:
Ooops, forgot to log in. That last comment is mine.
101:, a collaborative effort to improve the coverage of
8:
19:
162:I removed the following from the article:
47:
302:"One possibility is to choose a number
49:
7:
95:This article is within the scope of
38:It is of interest to the following
14:
373:Low-priority mathematics articles
294:Preiss definition of sparse graph
115:Knowledge:WikiProject Mathematics
368:Start-Class mathematics articles
322:| denotes the number of edges, |
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
197:16:49, 29 September 2005 (UTC)
182:16:27, 29 September 2005 (UTC)
1:
109:and see a list of open tasks.
335:is sparse for any choice of
158:Definition of "sparse graph"
389:
354:15:44, 29 April 2011 (UTC)
284:03:39, 4 August 2007 (UTC)
275:03:38, 4 August 2007 (UTC)
266:14:09, 28 July 2007 (UTC)
251:04:06, 27 July 2007 (UTC)
241:09:44, 20 July 2007 (UTC)
134:
67:
46:
298:I removed the sentence:
141:project's priority scale
98:WikiProject Mathematics
28:This article is rated
121:mathematics articles
231:definition correct?
90:Mathematics portal
34:content assessment
155:
154:
151:
150:
147:
146:
380:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
388:
387:
383:
382:
381:
379:
378:
377:
358:
357:
296:
233:
204:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
386:
384:
376:
375:
370:
360:
359:
328:
327:
295:
292:
291:
290:
289:
288:
287:
286:
277:
232:
229:
203:
200:
170:
169:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
385:
374:
371:
369:
366:
365:
363:
356:
355:
351:
347:
342:
338:
334:
325:
321:
317:
313:
309:
305:
301:
300:
299:
293:
285:
282:
278:
276:
273:
269:
268:
267:
263:
259:
254:
253:
252:
249:
245:
244:
243:
242:
239:
230:
228:
224:
221:
218:
215:
211:
208:
202:Sparse Matrix
201:
199:
198:
194:
190:
184:
183:
179:
175:
165:
164:
163:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
340:
336:
332:
329:
323:
319:
315:
311:
307:
306:with 1 <
303:
297:
272:68.221.99.78
258:Jitse Niesen
234:
225:
222:
219:
216:
212:
209:
205:
189:Jitse Niesen
185:
174:Jitse Niesen
171:
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
318:|), where |
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
362:Categories
333:any graph
281:Citrus538
248:Citrus538
238:Citrus538
341:classes
314:| = O(|
167:k : -->
139:on the
346:Hoopje
36:scale.
350:talk
262:talk
193:talk
178:talk
131:Low
364::
352:)
264:)
195:)
180:)
348:(
337:k
324:V
320:E
316:V
312:E
308:k
304:k
260:(
191:(
176:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
