# 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<>();

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);

}

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

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

if (v1 != v2) {

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

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

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

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

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

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

return true;

}

}

}

}

}

}

}

}

}

}

}

}

}

return false;

}

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

intvertexNum = vertices.length;

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

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);

}

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

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

if (v1 != v2) {

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

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

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

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

return true;

}

}

}

}

}

}

}

}

}

}

return false;

}

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

intvertexNum = vertices.length;

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

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);

}

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

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

if (v1 != v2) {

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

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

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

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

return true;

}

}

}

}

}

}

}

}

}

}

return false;

}

}