Konig's theorem: maximum matching equals minimum vertex cover

Both sides are computed and compared, and the cover is separately VERIFIED to cover every edge – a construction returning the right size while missing an edge would otherwise pass.

Usage

morie_konig_theorem(left_n, right_n, edges)

Arguments

left_n, right_n: Side sizes.
edges: List of (left, right) pairs, numbered from 1.

Value

A list with matching_size, cover_size, cover_is_valid, konig_holds, warnings.

References

Konig D (1931). Grafok es matrixok. Matematikai es Fizikai Lapok, 38, 116-119.

Examples

E <- list(c(1, 1), c(1, 2), c(2, 2), c(3, 1), c(3, 3))
morie_konig_theorem(3, 3, E)
#> $matching_size
#> [1] 3
#> 
#> $matching
#>        pairs
#> [1,] 1     1
#> [2,] 2     2
#> [3,] 3     3
#> 
#> $cover_size
#> [1] 3
#> 
#> $cover_left
#> [1] 1 2 3
#> 
#> $cover_right
#> integer(0)
#> 
#> $cover_is_valid
#> [1] TRUE
#> 
#> $n_uncovered
#> [1] 0
#> 
#> $konig_holds
#> [1] TRUE
#> 
#> $n
#> [1] 6
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Konig's theorem (Konig 1931)"
#>