Check if graph is a subgraph

Check if graph is a subgraph

Write a program(you can use any programming language)

  1. Given an array of strings represents the edges of the Graph (for example, edges = {“12”,”23”,”34”,”45”,”51”} represents the edges of a C5)
  2. Given an array of strings represents the vertices of the Graph (for example, vertices = {“1”,”2”,”3”,”4”,”5”} represents a graph with 5 vertices)
  3. Write a function called CheckC5 that takes 2 parameters, edges and vertices. Then returns a Boolean. This function should check whether the given Graph contains a C5 as an induced sub graph
  4. Write a function called Check4K1 that takes 2 parameters, edges and vertices. Then returns a Boolean. This function should check whether the given Graph contains a 4K1 as an induced sub graph
  5. Write a function called CheckClaw that takes 2 parameters, edges and vertices. Then returns a Boolean. This function should check whether the given Graph contains a claw as an induced sub graph 

Solution

importjava.util.HashMap;

importjava.util.Map;

public class Graph {

public static void main(String[] args){

System.out.println(CheckC5(new Character[]{‘1′,’2′,’3′,’a’,’b’,’c’}, new String[]{“1a”,”1b”,”1c”,”2a”,”2b”,”2c”,”3a”,”3b”,”3c”}));

System.out.println(Check4K1(new Character[]{‘1′,’2′,’3′,’a’,’b’,’c’}, new String[]{“1a”,”1b”,”1c”,”2a”,”2b”,”2c”,”3a”,”3b”,”3c”}));

System.out.println(CheckClaw(new Character[]{‘1′,’2′,’3′,’a’,’b’,’c’}, new String[]{“1a”,”1b”,”1c”,”2a”,”2b”,”2c”,”3a”,”3b”,”3c”}));

}

private static boolean CheckC5(Character[] vertices, String[] edges) {

intvertexNum = vertices.length;

Map<Character, Integer>vertexMap = new HashMap<>();

int[][] adjacency = new int[vertexNum][vertexNum];

for (int i = 0; i<vertexNum; i++) {

vertexMap.put(vertices[i], i);

}

for (int i = 0; i<edges.length; i++) {

Character a = edges[i].charAt(0);

Character b = edges[i].charAt(1);

adjacency[vertexMap.get(a)][vertexMap.get(b)] = 1;

adjacency[vertexMap.get(b)][vertexMap.get(a)] = 1;

}

for (int v1 = 0; v1<vertexNum; v1++) {

for (int v2 = 0; v2<vertexNum; v2++) {

if (v1 != v2) {

if (adjacency[v1][v2] == 1) {

for (int v3 = 0; v3<vertexNum; v3++) {

if ((v1 != v3)&&(v2 != v3)) {

if ((adjacency[v2][v3] == 1)&&(adjacency[v1][v3] == 0)) {

for (int v4 = 0; v4<vertexNum; v4++) {

if ((v1 != v4)&&(v2 != v4)&&(v3 != v4)) {

if ((adjacency[v3][v4] == 1)&&(adjacency[v1][v4] == 0)&&(adjacency[v2][v4] == 0)) {

for (int v5 = 0; v5<vertexNum; v5++) {

if ((v1 != v5)&&(v2 != v5)&&(v3 != v5)&&(v4 != v5)) {

if ((adjacency[v4][v5] == 1)&&(adjacency[v2][v5] == 0)&&(adjacency[v3][v5] == 0)&&(adjacency[v4][v5] == 0)&&(adjacency[v1][v5] == 1)) {

return true;

}

}

}

}

}

}

}

}

}

}

}

}

}

return false;

}

private static boolean Check4K1(Character[] vertices, String[] edges) {

intvertexNum = vertices.length;

Map<Character, Integer>vertexMap = new HashMap<>();

int[][] adjacency = new int[vertexNum][vertexNum];

 

for (int i = 0; i<vertexNum; i++) {

vertexMap.put(vertices[i], i);

}

for (int i = 0; i<edges.length; i++) {

Character a = edges[i].charAt(0);

Character b = edges[i].charAt(1);

adjacency[vertexMap.get(a)][vertexMap.get(b)] = 1;

adjacency[vertexMap.get(b)][vertexMap.get(a)] = 1;

}

for (int v1 = 0; v1<vertexNum; v1++) {

for (int v2 = 0; v2<vertexNum; v2++) {

if (v1 != v2) {

if (adjacency[v1][v2] == 0) {

for (int v3 = 0; v3<vertexNum; v3++) {

if ((v1 != v3)&&(v2 != v3)) {

if ((adjacency[v2][v3] == 0)&&(adjacency[v1][v3] == 0)) {

for (int v4 = 0; v4<vertexNum; v4++) {

if ((v1 != v4)&&(v2 != v4)&&(v3 != v4)) {

if ((adjacency[v1][v4] == 0)&&(adjacency[v2][v4] == 0)&&(adjacency[v3][v4] == 0)) {

return true;

}

}

}

}

}

}

}

}

}

}

return false;

}

private static booleanCheckClaw(Character[] vertices, String[] edges) {

intvertexNum = vertices.length;

Map<Character, Integer>vertexMap = new HashMap<>();

int[][] adjacency = new int[vertexNum][vertexNum];

for (int i = 0; i<vertexNum; i++) {

vertexMap.put(vertices[i], i);

}

for (int i = 0; i<edges.length; i++) {

Character a = edges[i].charAt(0);

Character b = edges[i].charAt(1);

adjacency[vertexMap.get(a)][vertexMap.get(b)] = 1;

adjacency[vertexMap.get(b)][vertexMap.get(a)] = 1;

}

for (int v1 = 0; v1<vertexNum; v1++) {

for (int v2 = 0; v2<vertexNum; v2++) {

if (v1 != v2) {

if (adjacency[v1][v2] == 1) {

for (int v3 = 0; v3<vertexNum; v3++) {

if ((v1 != v3)&&(v2 != v3)) {

if ((adjacency[v1][v3] == 1)&&(adjacency[v2][v3] == 0)) {

for (int v4 = 0; v4<vertexNum; v4++) {

if ((v1 != v4)&&(v2 != v4)&&(v3 != v4)) {

if ((adjacency[v1][v4] == 1)&&(adjacency[v2][v4] == 0)&&(adjacency[v3][v4] == 0)) {

return true;

}

}

}

}

}

}

}

}

}

}

return false;

}

}