Sign in to follow this  

Dense and Sparse Graphs

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this