Code:
#include iostream
#include iomanip
using namespace std;
// A function to print the adjacency matrix.
void PrintMat(int mat[][20], int n)
{
int i, j;
cout<<"\n\n"<
for(i = 0; i < n; i++)
cout<
cout<<"\n\n";
// Print 1 if the corresponding vertexes are connected otherwise 0.
for(i = 0; i < n; i++)
{
cout<
for(j = 0; j < n; j++)
{
cout<
}
cout<<"\n\n";
}
}
int main()
{
int NOV, i, j, AdjMat[20][20] = {0};
cout<<"Enter the number of vertex in the graph: ";
cin>>NOV;
int degseq[NOV];
// Take input of the degree sequence.
for(i = 0; i < NOV; i++)
{
cout<<"Enter the degree of "<
cin>>degseq[i];
}
for(i = 0; i < NOV; i++)
{
for(j = i+1; j < NOV; j++)
{
// For each pair of vertex decrement the degree of both vertex.
if(degseq[i] > 0 && degseq[j] > 0)
{
degseq[i]--;
degseq[j]--;
AdjMat[i][j] = 1;
AdjMat[j][i] = 1;
}
}
}
PrintMat(AdjMat, NOV);
}
Output:
Case 1:
Enter the number of vertex in the graph: 7
Enter the degree of 1 vertex: 9
Enter the degree of 2 vertex: 7
Enter the degree of 3 vertex: 7
Enter the degree of 4 vertex: 5
Enter the degree of 5 vertex: 5
Enter the degree of 6 vertex: 3
Enter the degree of 7 vertex: 2
No valid graph can be generated from the given degree sequence.
Case 2:
Enter the number of vertex in the graph: 5
Enter the degree of 1 vertex: 7
Enter the degree of 2 vertex: 7
Enter the degree of 3 vertex: 6
Enter the degree of 4 vertex: 6
Enter the degree of 5 vertex: 5
The Graph cannot have edges more than 10 for 5 vertexes.
Case 3:
Enter the number of vertex in the graph: 7
Enter the degree of 1 vertex: 5
Enter the degree of 2 vertex: 3
Enter the degree of 3 vertex: 3
Enter the degree of 4 vertex: 2
Enter the degree of 5 vertex: 2
Enter the degree of 6 vertex: 1
Enter the degree of 7 vertex: 0
Valid graph from the given degree sequence is:
(1) (2) (3) (4) (5) (6) (7)
(1) 0 1 1 1 1 1 0
(2) 1 0 1 1 0 0 0
(3) 1 1 0 0 1 0 0
(4) 1 1 0 0 0 0 0
(5) 1 0 1 0 0 0 0
(6) 1 0 0 0 0 0 0
(7) 0 0 0 0 0 0 0
More C++ Programs:
