InducedMatchingNumber
The most edges whose ends induce a subgraph that is just those edges.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St001393via LabeledGraph✓InducedMatchingNumber(graph)The most edges whose ends induce a subgraph that is just those edges.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 St001393: half the vertices of the largest set in which every vertex has exactly one neighbor. The graph with no vertices gives 0.
Definition
Epsil, as the implementation runs it.
on LabeledGraph, over _x
0 if _x[1] == 0 else Apply((n: integer) => Apply((edges: list<list<integer>>) => Apply(
(inside: list<integer>) => Apply(
(totals: list<integer>) => Apply(
(toSet: list<list<integer>>) => Max(Map(Function((1 if Max(Sum(Map(Function((1 if m %
2 ^ v >=
2 ^
(v - 1) else 0) *
(1 if toSet[m + 1][v] !=
1 else 0), v), Range(1, n))), 0) ==
0 else 0) *
totals[m + 1], m), Range(0, 2 ^ n -
1))) /
2,
Map(
Function(Map(Function(Max(Sum(Map(Function((1 if e[1] == v else 0) *
(1 if m %
2 ^ e[2] >=
2 ^
(e[2] - 1) else 0) +
(1 if e[2] == v else 0) *
(1 if m %
2 ^ e[1] >=
2 ^
(e[1] - 1) else 0), e), edges)), 0), v), Range(1, n)), 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 |