Girth
The length of the shortest cycle.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St000264via LabeledGraph✓Girth(graph)The length of the shortest cycle.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 St000264, of a graph that is not a tree; a graph without a cycle has an infinite girth. 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(
(totals: list<integer>) => Apply(
(adjacency: list<list<integer>>) => Apply(
(paths: list<integer>) => Apply(
(shortest: integer) => PositiveInfinity if shortest > n else shortest,
Min(Map(Function(totals[s + 1] if (1 if totals[s + 1] >=
3 else 0) *
Apply(
(low: integer) => Max(Sum(Map(Function(adjacency[low][e] *
paths[(s - 1) *
n +
e +
1], e), Range(1, n))), 0),
Min(Map(Function(v if s %
2 ^ v >=
2 ^
(v - 1) else n + 1, v), Range(1, n))),
) >
0 else n + 1, s), Range(1, 2 ^ n -
1))),
),
Apply((a_init: list<integer>) => Fold((a: list<integer>, b) => Apply(
(a_next: list<integer>) => a_next,
Join(a, Map(Function((1 if b ==
2 ^
(e - 1) else 0 if e ==
Min(Map(Function(v if b %
2 ^ v >=
2 ^
(v - 1) else n + 1, v), Range(1, n))) else Max(Sum(Map(Function((1 if (b -
2 ^
(e - 1)) %
2 ^ w >=
2 ^
(w - 1) else 0) *
adjacency[w][e] *
a[(b -
2 ^
(e - 1) -
1) *
n +
w +
1], w), Range(1, n))), 0)) if b %
2 ^ e >=
2 ^
(e - 1) else 0, e), Range(1, n))),
), a_init, Range(1, 2 ^ n -
1)), [0]),
),
Map(
Function(Map(Function(Max(Sum(Map(Function((1 if e[1] == i else 0) *
(1 if e[2] == j else 0) +
(1 if e[1] == j else 0) *
(1 if e[2] == i else 0), e), edges)), 0), j), Range(1, n)), i),
Range(1, n),
),
),
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),
),
), _x[2]), _x[1])Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |