reset password
Author Message
G190852562
Posts: 162
Posted 03:20 Dec 07, 2014 |

1. Given a graph with n vertices and m edges, in most (but not all) applications, m is O(n) and O(n^2).
 

2. In a “sparse” graph, m is or is close to O(n)

In a “dense” graph, m is closer to Theta(n^2)

The video slides go through these briefly. Can someone explain what they mean? Thanks.

yxu22
Posts: 25
Posted 09:12 Dec 07, 2014 |

sparse graph means number of edges m is less than or equal to number of vertices n. 

dense graph means number of edges m is greater than number of vertices n and less then or equal to n^2.

They are definitions.

G190852562
Posts: 162
Posted 12:45 Dec 07, 2014 |

Understood. :)