Pontryagin-Kuratovsky theorem. A graph is planar if and only if it does not contain subgraphs homeomorphic to K5 or K3,3

In this context, homeomorphism means an equivalence relation.

The task is as follows, to implement a program that will check the graph for planarity, referring to this theorem (not Gamma - algorithm). The question is: is there an algorithm for enumerating subgraphs in a graph and how to check them for homeomerism with K5 and K3,3. enter image description here

public Vertex[] getCycleLen5() { Vertex[] adjList = graph.getAdjList(); boolean[][] aMatrix = createAdjMatrix(adjList); //Const for max len of cycles; final int n = 5; Vertex[]subGraph = new Vertex[n]; for (int i = 0 ; i < n ; i++) subGraph[i] = new Vertex(); for (int a = 0 ; a < graph.getVertices() ; a++) for (int b = a + 1 ; b < graph.getVertices() ; b++) { if (!aMatrix[a][b]) continue; for (int c = b + 1; c < graph.getVertices() ; c++) { if (!aMatrix[b][c]) continue; for (int d = c + 1; d < graph.getVertices() ; d++) { if (!aMatrix[c][d]) continue; for (int e = d + 1; e < graph.getVertices() ; e++) if (aMatrix[d][e] && aMatrix[e][a]) { subGraph[0] = adjList[a]; subGraph[1] = adjList[b]; subGraph[2] = adjList[c]; subGraph[3] = adjList[d]; subGraph[4] = adjList[e]; } } } } return subGraph; }
  • Try to look for cycles of length 5 and 6 and check their edges are not included in the cycle. And to search for cycles, the algorithm to google, and to think up, is not difficult. - rdorn
  • @rdorn search cycles - search in depth, but "check their edges, not included in the cycle" did not understand a bit, please explain - Ladence
  • @rdorn "check that the vertex edges not included in the cycle do not form graph K5", in fact this is my question :) - Ladence
  • @rdorn can you give pseudocode? - Ladence
  • a little later, now I have to run, I can write on sharpe. it is not much different, I think you can translate without problems - rdorn

1 answer 1

Ok, since the search for cycles in the graph of problems does not cause and suits the answer to C # (see the comments to the question), I will give a simple solution to the forehead. LiNQ is not used to simplify porting to Java, although it would be more compact with it.

We define a simple vertex class of an un-oriented graph (the necessary minimum):

 class Vertex { public List<Vertex> Adges = new List<Vertex>(); public bool HasAdgeToVertex(Vertex vertex) { foreach(var adge in Adges) { if (adge == vertex) return true; } return false; } }

Now we need two functions to check that the vertices of the found cycle are the graph K5 or K3,3

Check for K5:

 bool IsK5graph(Vertex[] subgraph) { bool result = false; int n = 5; if (subgraph.Length == n) { result = true; for (var i = 0; i < n - 1; i++) { for (var j = i + 1; j < n; j++) { result &= subgraph[i].HasAdgeToVertex(subgraph[j]); } } } return result; }

Simply check that for this set of vertices there are all 10 necessary edges.

Similarly for K3.3, but taking into account its features, we will slightly change the internal verification cycle:

 bool IsK33graph(Vertex[] subgraph) { bool result = false; int n = 6; if (subgraph.Length == n) { result = true; for (var i = 0; i < n - 1; i++) { for (var j = i + 1; j < n; j += 2) { result &= subgraph[i].HasAdgeToVertex(subgraph[j]); } } } return result; }

Both checks are processed in N iterations, where N is the number of edges of the graph K5 and K3.3, respectively. Given the small N, optimizing the verification by reducing the number of iterations and complicating the verification code may not give any or even negative effect on the total time of the graph verification. But you can optimize the check for the presence of an edge at a vertex, for example, replacing a List for storing adjacent vertices, with a HashSet if the original graph does not contain parallel edges.

If we specify the edges through the adjacency matrix, then the matrix for K5 will look like this for an undirected graph:

  1 2 3 4 5 --------- 1 | 0 1 1 1 1 | 2 | 1 0 1 1 1 | 3 | 1 1 0 1 1 | 4 | 1 1 1 0 1 | 5 | 1 1 1 1 0 |

Then the solution can be reduced to constructing an adjacency matrix for the vertices of the found cycle and checking that it does not coincide with the given one. In order to speed up the process, it is possible to combine the construction and verification of adjacency matrices for coincidence. If the main graph is specified via the adjacency matrix, then this option may be convenient.

For K3,3 the matrix is ​​as follows:

  1 2 3 4 5 6 ----------- 1 | 0 1 0 1 0 1 | 2 | 1 0 1 0 1 0 | 3 | 0 1 0 1 0 1 | 4 | 1 0 1 0 1 0 | 5 | 0 1 0 1 0 1 | 6 | 1 0 1 0 1 0 |
  • Thank you so much for the detailed explanation and the code is very useful. - Ladence
  • @ K.Zakhar use, and thank you here they say a tick usually or mark "the answer is useful" next to the rating. A tick "answer" can be rearranged if someone writes a more appropriate answer =) - rdorn
  • But judging by your code, you need to look not for cycles of length 5, but subgraphs on five vertices. More formally: the cycles are a "contour" on the graph - Ladence
  • uh ... doesn't the outline form a subgraph? This is something new - rdorn
  • one
    @ K.Zakhar unfortunately, it seems that the problem is not in the algorithm, but in understanding how to build adjacency matrices and take off work further. Have a separate question labeled Algorithm, without specifying a language. Or try all the same to use the proposed option with the explicit creation of a class to describe the vertices of the graph. Regarding your last question - you do not need to overestimate the vertices, you have indices of the array of vertices, and which vertices in it does not matter for the algorithm - rdorn