Personal notes for programming

• To find if a connected graph is cyclic simple do a bfs and check if the number of visited adjacent nodes for ant node are greater than 2 then the graph contains cycle.

• Some important values-2^10 approx 10^3 ,2^20 approx 10^6

• Important modular arithmetic formulas- 

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
p = prime, b^(-1) mod p = b^(p - 2) mod p

• Combinatorics imp points:-

consider the set {1, 2, 3}$\{1,2,3\}$. There are 23=8$2^3=8$ total subsets (of all sizes), which are

{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}$$\left\{\mathrm{\varnothing },\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\right\}$$$$$$
$$$$Combinations count the subsets of a particular size (n$n$ choose r$r$ counts the number of r$r$-element subsets of an n$n$-element set). In our running example consider how many subsets of size 2$2$ there are:

{{1, 2}, {1, 3}, {2, 3}}

(Imp see that only {1,2} is there not {2,1})

To count undirected loopless graphs with no repeated edges, first count possible edges. As Andre counts, there are (n2) such edges. One by one, each edge is either included or excluded. So this gives2(n2) possible graphs.

If loopless graphs with no repeated edges are directed, each pair of vertices a<b$a<b$ provides 3 possibilities for a (potentially absent) edge. So we have 3 choices (a,b) (b,a) and not present.