CODEWITHSUNDEEP
algorithmgraph
venkysmarty
venkysmarty

Reputation: 11431

maximum number of edges in a graph

I am reading about representing graphs at following location.

http://www.brpreiss.com/books/opus4/html/page532.html

Consider a directed graph G = (V,E). Since E is subet or equal to V x V, graph G contains at most V^2 edges. There are 2^(V^2) possible sets of edges for a given set of vertices . Therefore, the main concern when designing a graph representation scheme is to find a suitable way to represent the set of edges.

My question is what does author mean by "2^(V^2) possible sets of edges for a given set of vertices" ?

For example if we have 2 vertices then I can understand we can h ave 4 edges ie.e., {(a,a), (a,b), (b,a), (b,b) } But how do we get 16 possible sets of edges.

Thanks for your time.

Upvotes: 0

Views: 175

Answers (1)

Reto Koradi
Reto Koradi

Reputation: 54592

The way I read it, they are saying that there are 2^(V^2) ways of building a directed graph with V vertices. Since there are a total of V^2 possible edges, and each possible edge can either be present or not present in a given graph, this is the number of combinations.

In the example with 2 vertices, and using your notation, the sets of edges for the 16 possible graphs are:

{ (a,a), (a,b), (b,a), (b,b) }
{ (a,a), (a,b), (b,a) }
{ (a,a), (a,b), (b,b) }
{ (a,a), (a,b) }
{ (a,a), (b,a), (b,b) }
{ (a,a), (b,a) }
{ (a,a), (b,b) }
{ (a,a) }
{ (a,b), (b,a), (b,b) }
{ (a,b), (b,a) }
{ (a,b), (b,b) }
{ (a,b) }
{ (b,a), (b,b) }
{ (b,a) }
{ (b,b) }
{ }

Upvotes: 1

Related Questions