Konig Theorem

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

MutableBipartiteGraph<String> g = MutableBipartiteGraph.create();

g.insertLeftVertex("A");
g.insertLeftVertex("B");
g.insertLeftVertex("C");

g.insertRightVertex("X");
g.insertRightVertex("Y");
g.insertRightVertex("Z");

g.addEdge("A", "X");
g.addEdge("A", "Y");
g.addEdge("A", "Z");
g.addEdge("B", "Z");
g.addEdge("C", "Z");

// By Konig's Theorem, In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
// So matching algorithm is used in its implementation. In this example, Hopcroft-Karp algorithm is used.
MinimumVertexCoverAlgorithmInBipartiteGraph algorithm = KonigTheorem.getInstance(HopcroftKarpAlgorithm.getInstance());

int number = algorithm.calcMinimumVertexCover(g); // result is 2, ("A", "C")

See Also

• Maximum Bipartite Matching
• Minimum Vertex Cover In Bipartite Graph

Implementation

• KonigTheorem.java in GitHub

---

Copyright 2014 psjava team. View on GitHub