# Dense and Sparse Graphs

This topic is 4005 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm having the problem of determining what makes a spares (undirected) graph and what makes a dense (undirected) graph. For my personal learning experience I wanted to try and make a graph generator that makes sparse (undirected) and dense (undirected) graphs. The problem is I'm really unclear about the rules that makes a graph dense and what makes a graph sparse. Thank you for any, any, any help at all.

##### Share on other sites
It's my understanding that a graph is sparse if the number of connections is on the order of the number of nodes and dense if the number of connections is on the order or the number of nodes squared.

If a graph has n nodes and is expected to have something like 3n+2 connections then it would be sparse. If a graph has n nodes and is expected to have n*n/2-1 connections then it would be dense. This applies more to the sets of graphs that would be expected for an algorithm then it does to any individual graph. For example, this is the type of analysis I would do before deciding whether to use a connection list or an adjacency matrix.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 18
• 20
• 14
• 14
• 9
• ### Forum Statistics

• Total Topics
633374
• Total Posts
3011552
• ### Who's Online (See full list)

There are no registered users currently online

×