Graphs and Hypergraphs

Graph :- A graph G is an 2-tuple (V,E) of a set of vertices V and a set of edges E, where {x,y} ∈ E  ⇒ x,y ∈ V.

Directed Graph :- A directed graph D is an 2-tuple (V,E) of a set of vertices V and a set of edges E, where (x,y) ∈ E  ⇒ x,y ∈ V.

Each of above, can be further classified into, labeled and unlabeled classes.
 

Labeled simple Graph of 6 vertices and 7 edges

An un-labeled Directed Graph

Graphs, can further be classified as edge or vertex or both weighted graphs. So, weighted graphs is represented by G(V,E,w(V),w(E)), where w resembles weight. 

Computer Representation of Graph :-
w(V) is an array of numbers w₀,w₁,...,w_n-1. 
w(E) is an 2-D array of numbers, called Adjacency Matrix A = ( w_(x,y) ) where w_(x,y) is the weight of edge (x,y) ∈ E. If edge is not present then w_(x,y) = 0.

We can also, represent w(E) by an Adjacency List, where we have an array A, One element of A is another array A(x), which contains, ordered pair (w_(x,y), y) sorted with respect to y.



This representation ease the search of edge as well as reduce the storage space in the sparse graph. 

Note, that Adjacency List search time is O(log(n)), space complexity O(|V| + |E|). In Adjacency Matrix search time is O(1) but space complexity is O(|V|²).

Adjacency List Representation of directed and undirected graphs

Again Hypergraph is a graph in which each edge is a k-tuple or set of k vertices, where k ≤ |V|. 

Uniform random number generation in Computer

Let's, have a generator, Ui(R_max+1), to generate uniform random integer r ∈ [0...R_max].
We can construct Ui(N) in following way,

Ui(N) =

1. Range = R_max - ( R_max )mod N
2. do
1. r = U(R_max+1);
3. while( r  ≥  Range );
4. Return(r);

Similarly, we can further construct a real random number generator Ur(N), which generates random real r ∈ [0,1]. using  Ui(N).

Ur(N) = (N-1)/Ui(N);

Ber(p) = ( Ur(N) ≤ p ) + (Ur(N) > p) ;
Binomial(n,p) =

1. y = 0
2. for(i = 0; i < n; i = i + 1)
1. y = y + Ber(p)
3. Return y 

Fermat's Last Theorem

Pierre de Fermat in 1637, had made a conjecture that there is no integer a,b,c,n if n > 2 s.t aⁿ + bⁿ = cⁿ
become true.

This was open problem to prove through centuries. At last  Andrew Wiles had proved it in 1995. 
For n = 2 we have infinite many such tuple. But for n = 3 no such tuple exist.