Posts

Showing posts with the label Algorithm

Havel-Hakimi Illustrated

Image
Havel-Hakimi algorithm is an algorithm which can verify whether there exists a simple graph for given degree sequence. Before we dive into the actual algorithm lets revisit some of the key terms: simple graph and degree sequences.  1. What is Simple Graph? A simple graph is an undirected, unweighted graph with no self loops and no multi-edges. 2. Degree Sequences A degree of a vertex i, is number of edges incident on i with self loops counted twice. Degree sequences is the arrangement of degree in non-ascending or non-descending order. Figure 1:- Degree Sequences: Graph with degree sequence (4, 3, 2, 2,1)  3. Havel-Hakimi Algorithm  Put degree sequence in non-ascending order  Remove highest degree, k  Subtract 1 from next k entries in degree sequence  Repeat step 1, 2, 3 & stop until  If we get all zero entries -> simple graph exist  If we get at least one negative entry -> simple graph does not exist  If no enough entries -> simple graph doe