Question

Goal Design and implement an algorithm to input the data representation of two graphs, determine if the graphs are complements of each other and, if so, outputs a message that the graphs are complements then outputs the degrees of the vertices of each graph, otherwise outputs a message to the contrary and immediately terminates. Details Input to your program consists of the representation of two graphs and will be in the following format: an integer m representing the number of vertices of the first graph Gi . an adjacency matrix for Gi of m rows, each with, m entries. Each entry of the m xm adjacency matrix, will contain a 1 if there is an edge between the corresponding vertices or a 0 if there is no edge an integer n representing the number of vertices of the second graph G .an adjacency matrix for Gi of n rows, each with, n entries. Each entry of the n x n adjacency matrix, will contain a 1 if there is an edge between the corresponding vertices or a 0 if there is no edge There is a space following each number in the adjacency matrix, including the last number in each row. There is NOT a space in the first line indicating the size of the array Output is required to be formatted as in the examples below It is up to you to determine the best algorithm to accomplish this task. You MUST, however, use a 2-D array to represent the adjacency matrix in your program. It is very important that a 2-D array is used as it will be necessary in future labs. In addition, the elements of the 2-D array should be referenced at most once and if the graphs are not complementary the algorithm should terminate as soon as that is determined

Answer 1

import java.util.Scanner;

public class lab1 {

public static void main(String[] args) {

int m,n,flag;

Scanner sc = new Scanner(System.in);

System.out.println("Input (Adjacency Matrix Representation)");

m = sc.nextInt();

int[][] adj_mat1 = new int[m][m];

int[] deg1 = new int[m];

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

adj_mat1[i][j] = sc.nextInt();

System.out.print(" ");

}

System.out.println();

}

n = sc.nextInt();

int[][] adj_mat2 = new int[n][n];

int[] deg2 = new int[n];

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

adj_mat2[i][j] = sc.nextInt();

System.out.print(" ");

}

System.out.println();

}

if(m!=n)

{

System.out.println("Output: ");

System.out.println();

System.out.println("The graphs are not complementary.");

System.out.println("The graphs have different number of vertices.");

return;

}

else

{

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

if(adj_mat1[i][j]==adj_mat2[i][j])

{

System.out.println();

System.out.println("Output: ");

System.out.println("The graphs are not complementary.");

System.out.println("The graphs have the same number of vertices but don't have complementary edges");

return;

}

}

}

}

System.out.println();

System.out.println("Output: ");

System.out.println("The graphs are complementary.");

System.out.println("");

for(int i=0;i<m;i++)

{

for(int j=0;j<m;j++)

{

int count=0;

if(adj_mat1[i][j]==1)

{

count++;

deg1[i] = count;

}

}

}

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

int count=0;

if(adj_mat2[i][j]==1)

{

count++;

deg2[i] = count;

}

}

}

System.out.println("Vertex G1 Degree G2 Degree");

for(int i=0;i<m;i++)

{

System.out.println(i+" "+deg1[i]+" "+deg2[i]);

}

}

}

OUTPUT:

Input (Adjacency Matrix Representation)

3

0 1 1

0 1 0

1 1 0

3

1 0 0

1 0 1

0 0 1

Output:

The graphs are complementary.

Vertex G1 Degree G2 Degree

0 2 1

1 1 2

2 2 1