#include <stdio.h> typedef int bool; #define true 1 #define false 0 #define N 4 #define E 5 //Have to check for three condition to be met for Hamiltonian circuit //1.If has Verrtex >= 3 //2.Degree of every vertex is at least n/2 //3.deg u + deg v >= No of vertex void main () { _Bool G[N][N]; int d[N]; unsigned int i =0; unsigned int j=0; //Initialise all the content for(i=1;i<=N;i++){ for(j=1;j<=N;j++){ G[i][j] = false; } } G[1][2] = true; G[2][3] = true; G[4][1] = true; G[3][4] = true; G[2][4] = true; //Represent the graph Given //Initalise the degree of all possible combination for(i=1 ; i<= N ; i++) { d[i] = 0 ; } //Build the degree of each vertices for (i=1; i<=N ; i++) { for (j=1 ; j <=N ; j++) { //seprate out self looping positions if (i != j){ if (G[i][j] == true){ d[i] = d[i] + 1; d[j] = d[j] + 1; } } } } //Condition 1 : Graph has at least 3 Vertices _Bool C1; C1 = (N >= 3) ? 1 : 0; //Condition 2 : degree of every vertices at least N/2 _Bool C2 = true; for (i=1; i<=N ; i++) { if(d[i] >= N/2) { C2 = C2 && true ; } else { C2 = C2 && false ; } } //Condition 3 : if adject exist no prob //if both are non adjecent then deg u + degv >= N //If the Graph is hamiltonian we have to check adding any adjecent edge // Will stay that at hamiltonian if they are not adjecent we'll check for the //the degree addition is greater than or equal to N . _Bool C3 = true; for (i=1;i<= N;i++) { for(j=1;j<=N; j++){ if (i!=j){ if (G[i][j] == true) { C3 = C3 && true; } else { if( d[i] + d[j] >= N) { C3 = C3 && true; } else { C3 = C3 && false; break; } } } } } for (i=1;i<= N;i++) { for (j=1;j<= N;j++) { printf("\nThe value of G [%d] [%d] is : %d" , i, j, G[i][j]); } } printf("\nThe value of C1 is : %d" , C1); printf("\nThe value of C2 is : %d" , C2); printf("\nThe value of C3 is : %d" , C3); __CPROVER_assert( !(C1 && C2 && C3) , "Hamiltonian path exists"); }
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)