Question

DISCRETE STRUCTURES AND ITS APPLICATIONS. MATH (DISCRETE MATHEMATICS)

(ONLY ANSWER IF YOU KNOW THE ANSWER PLEASE DON'T GUESS)

PLEASE WRITE A FULL C++  PROGRAM. A PROGRAM THAT TAKES IN USER INPUT AND CAN BE DEBUGGED AND PRODUCES THE OUTPUT(DISPLAY).. (Please use comments to explain if you can)

1. WRITE A FUNCTION WHICH TAKES A DEGREE SEQUENCE AND CHECKS THAT THE SUM OF THE DEGREES IS EVEN AND ALSO THAT THERE IS AN EVEN NUMBER OF VERTICES OF ODD DEGREE. IF THE DEGREE SEQUENCE IS NOT A VALID GRAPH, RETURN FALSE. IF THERE IS A 'POSSIBILITY' IT IS VALID GRAPH RETURN TRUE. (NOTE: IN THIS CASE TRUE JUST MEANS 'MAYBE')

Answer 1

Following is a C++ program which takes n(number of vertices in the graph) and degree sequence of length n as input and outputs the result according to the possibility of validity of the sequence.

the function is_valid() return FALSE if the given degree sequence is not a valid graph and TRUE if there is a possibility of the given sequence to be a valid graph.

1.SUM OF ALL DEGREES OF VERTICES IS EVEN

2,NUMBER OF ODD DEGREE VERTICES IS EVEN

BOTH CONDITION 1 AND 2 ARE SAME THING, JUST A DIFFERENT WAY OF SAYING SAME THINGS, AS IF NUMBER OF ODD DEGREE VERTICES ARE NOT EVEN THEN THE SUM WILL ALWAYS BE ODD AND VICE-VERSA.

please see the code below:

//code begins............

#include <iostream>
using namespace std;
//function to check validity of the degree sequence.
bool is_valid(int degree_sequence[],int n){
int sum=0;//sum stores the sum of all degrees of vertices of given graph.
int odd_degree_vertices=0;//odd_degree_vertices stores the number of vertices having odd degree.
for(int i=0;i<n;i++){
if(degree_sequence[i]%2!=0){//check for odd degree vertex.
odd_degree_vertices+=1;
}
sum=sum+degree_sequence[i];//adding to sum variable.
}
//these two conditions mentioned in the if condition below will occur
// simultaneously as these are one and the same thing but due to the problem statement
// which tells us to check both conditions so i checked it for the sake of the problem statement.
if(sum%2!=0 || odd_degree_vertices%2!=0){
return false;
}
else{
return true;
}
}
int main(){
// n is the number of vertices in the graph(size of degree sequence)
cout<<"Enter number of vertices in the graph or the size of given degree sequence."<<"\n";
   int n;
   cin>>n;
   //dynamic allocation of array.
   int *degree_sequence=new int[n];
   cout<<"Enter the degree sequence."<<"\n";
   for(int i=0;i<n;i++){
   int d;
   //input degree sequence one by one and storing it in array.
   cin>>d;
   degree_sequence[i]=d;
   }
   //boolean returned by function to check validity.
   bool check_validity=is_valid(degree_sequence,n);
   if(check_validity){
   cout<<"There is a possibility that the given degree sequence represent a valid graph."<<"\n";
   }
   else{
   cout<<"The degree sequence is not a valid graph as the sum of all degrees is not even."<<"\n";
   }
   return 0;
}

//code ends.

Below is the attachment of the snapshot of the code in the editor and the output corresponding to a particular input.

INPUT :

6

5 5 4 3 2 1

As the sum of given degree sequence is 20 which is even and the number of odd degree vertex is 4(which is even) so there is a possibility that the given degree sequence is a valid graph.

You can read about havel-hakimi theorem for more understanding of concept of checking if a degree sequence is a valid graph or not..

SO ABOVE IS THE SOLUTION TO THE PROBLEM , I HAVE GIVEN MY BEST EFFORT TO MAKE YOU UNDERSTAND THE CODE SNIPPET WITH SUITABLE COMMENTS AND EXAMPLE INPUT AND PLEASE COMMENT IF YOU HAVE ANY QUERY . SO IF IT HELPED(MAY IT BE VERY LITTLE) YOU IN ANY WAY, PLEASE UPVOTE MY SOLUTION.ALWAYS IN YOUR SERVICE.

THANK YOU.