Hey Guys I have a small question about the Hopcroft and Karp Algorithm.

I have a task to solve where I have to calculate the perfect matching. My professor told me I should use the Hopcroft Algorithm. With that I can calculate the maximal matching and then valited with (number of edges/2 = number of matching) if there is a perfect matching

Some background: Currently the Graphs will be representated as followed.

|(0,0) (1,0) (2,0) (3,0) (4,0) (5,0)|

|(0,1) (1,1) (2,1) (3,1) (4,1) (5,1)|

|(0,2) (1,2) (2,2) (3,2) (4,2) (5,2)|

|(0,3) (1,3) (2,3) (3,3) (4,3) (5,3)|

The 2-Tupel representing node coordinates in a room and the big one are actual nodes for this example

We dont count the diagonal ones as neighbors, so (2,1) has just (3,1) and (2,2) as neighbors

Also this example has 2 Graphs (it could be more or less, the points are random) but its cleary not bipartite.

Now is the problem I dont know how to apply this algorithm. Actually I know that if you just consider the diagonal values of a graph you could form a bipartite graph.

Lets say Graph 1. is with the points (1,2) (2,1) (3,1) (4,1), the graph could be bipartite if we imgagine that each diagonal is a subset of the Graph.

For example the bipartite parts are for Graph 1. { (1,2) (2,1)}, { (3,1), (2,2)} and {(4,1}) but I dont know if this helps me, I just think it makes it harder to programm.

So the question is how could I use the Hopcraft Algorithm for a single graph which is representated as above(lets say for Graph 1)

  • $\begingroup$ If the problem is you don't know how to apply the algorithm, then maybe that's exactly why you were given this exercise - to prod you to learn how! If you understand the algorithm, you should be able to write pseudocode for it. If you can write pseudocode, you should be able to execute it by hand. If you can't write pseudocode, there must be something specific you don't understand; ask about that. $\endgroup$ – D.W. Jun 19 '18 at 20:32
  • $\begingroup$ As it stands all we have to go with is that you don't understand the algorithm, but you don't say why or what you do understand, and you don't articulate a specific question. That makes it hard for us to give a useful answer. This is a question-and-answer site, so you need to articulate a specific question. We're not going to do your exercise for you, or explain the entire Hopcraft algorithm to you (there are plenty of resources that already have such an explanation), but if you have a specific question about the algorithm, we might be able to answer it. $\endgroup$ – D.W. Jun 19 '18 at 20:34
  • $\begingroup$ I now what you mean, but I asking myself and you guys, if its even possible to use the algorithm with Graphes above? Thats why I am unsure. I wont deep into the algo if its not even possible. I hope you understand what i mean :D Edit: I never said that you should explain me the algorithm or do my exercise. The only question is if I can transform a graph like this into a bipartite graph, or even are graphs which the spezification from above in generell in a way bipartite $\endgroup$ – Nado Ba Jun 19 '18 at 20:34
  • $\begingroup$ This is your exercise, so it is for you to figure out. As Wikipedia explains, the Hopcroft-Karp algorithm can be used with any bipartite graph. Do you have a bipartite graph? If yes, what can you conclude? It sounds like you should spend more time studying how the algorithm works. $\endgroup$ – D.W. Jun 19 '18 at 20:36
  • $\begingroup$ I am not sure if you understand me right, as I said I have Graphs like above and I am not sure if they are Bipartite or not with spezification like( just neighbors are edges etc.) $\endgroup$ – Nado Ba Jun 19 '18 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.