What is dense graph and sparse graph?

Answer 1

Sparse vs. Dense GraphsInformally, a graph with relatively few edges is sparse, and a graph with many edges is dense. The following definition defines precisely what we mean when we say that a graph ``has relatively few edges'':

Definition (Sparse Graph) A sparse graph is a graph in which .

For example, consider a graph with n nodes. Suppose that the out-degree of each vertex in G is some fixed constant k. Graph G is a sparse graph because .

A graph that is not sparse is said to be dense:

Definition (Dense Graph) A dense graph is a graph in which .

For example, consider a graph with n nodes. Suppose that the out-degree of each vertex in G is some fraction fof n, . E.g., if n=16 and f=0.25, the out-degree of each node is 4. Graph G is a dense graph because .