Check if graph is a subgraph
Write a program(you can use any programming language)
- 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)
- 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)
- 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
- 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
- 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;
}
}