MinimumVertexCoverCount
The vertex covers with the fewest vertices: the independent sets with the most.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St000363via LabeledGraph✓MinimumVertexCoverCount(graph)The vertex covers with the fewest vertices: the independent sets with the most.Typed signatures
| Type | Package | Applies |
|---|---|---|
(labeled_graph) -> number | combinatorics | always |
Details
- Defined over
LabeledGraphas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
LabeledGraphand nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer. - FindStat's St000363: the covers of the least possible size, which are the complements of the largest independent sets. The graph with no vertices has the empty cover, so 1.
Definition
Epsil, as the implementation runs it.
on LabeledGraph, over _x
1 if _x[1] == 0 else Apply((n: integer) => Apply((edges: list<list<integer>>) => Apply(
(inside: list<integer>) => Apply(
(totals: list<integer>) => Apply(
(top: integer) => Max(Sum(Map(Function((1 if inside[m + 1] ==
0 else 0) *
(1 if totals[m + 1] ==
top else 0), m), Range(0, 2 ^ n -
1))), 0),
Max(Map(Function((1 if inside[m + 1] ==
0 else 0) *
totals[m + 1], m), Range(0, 2 ^ n -
1))),
),
Map(
Function(Max(Sum(Map(Function(1 if m %
2 ^ v >=
2 ^
(v - 1) else 0, v), Range(1, n))), 0), m),
Range(0, 2 ^ n -
1),
),
),
Map(
Function(Max(Sum(Map(Function((1 if m %
2 ^ e[1] >=
2 ^
(e[1] - 1) else 0) *
(1 if m %
2 ^ e[2] >=
2 ^
(e[2] - 1) else 0), e), edges)), 0), m),
Range(0, 2 ^ n -
1),
),
), _x[2]), _x[1])Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |