cs215 »

Lesson 2: Big-Theta, Graphs

All of the code used in Lesson 2 can be found here: Code


In this lesson, we were introduced to the various types of graphs and the big theta notation. We studied chains, rings, grids, trees, hypercubes, planar graphs and then analysed the time taken in their creation with big theta notation.

Chain Networks


A chain network consists of an edge connecting every node except the starting node and the ending node. All chain networks have one edge less than the number of nodes, i.e., m = n - 1 where m is the number of edges and n is the number of nodes.

Ring Networks


A ring network has each node connected to two other nodes, forming a ring. A chain network with the beginning and ending nodes connected would give you a ring network. All ring networks have the same number of edges and nodes, i.e., m = n where m is the number of edges and n is the number of nodes.

Grid Networks


A grid network has nodes arranged in a rectangular grid. An a x b grid would have a*b nodes, where a is the number of columns and b are the number of rows (or vice versa). To calculate the number of edges, we see that there are (a-1) edges on the first row and (b) such rows. Similarly, there are (b-1) edges on the first column and (a) such columns. Therefore, the number of edges (m) in a grid network is b*(a-1) + a*(b-1) or 2*a*b - (a + b). In the above image,

a = 4
b = 5  
n = a*b = 20  
m = b*(a-1) + a*(b-1)
  = 5*3 + 4*4
  = 15 + 16
  = 31


For a square grid, a = b, which therefore equals n^(1/2).

Randomized Graphs

Erdős–Rényi model

According to the Erdős–Rényi model, we first select a number of nodes (n). Then, we consider _each possible pair_ of nodes and connect them with a certain probability (p).

For example, if we have a graph with five nodes (n=5), let's say the nodes are a, b, c, d and e. If the probability we decide on is 0.5, then, we connect 'a' to 'b' with probability 0.5, 'a' to 'c' with probability 0.5 and so on till we connect 'a' to 'e' (with probability 0.5). Then, we move on to connecting 'b' with the remaining nodes (not 'a'), i.e., 'c', 'd', and 'e'.

Of course, when all nodes are connected (with probability 1) then we get a complete graph. You can decrease the probability to connect a lower number of edges and thus, obtain a randomly generated graph based on the probability (value of p).