Показатель краткости

В теории графов показатель краткости — это числовой параметр семейства графов, который измеряет, насколько далеки от гамильтоновых могут быть графы в семействе. Интуитивно, если — показатель краткости семейства графов , то каждый граф с вершинами в семействе имеет цикл длины около , но некоторые графы не имеют более длинных циклов. Точнее, для любого упорядочения графов в в последовательность , где определено как длина самого длинного цикла в графе , показатель краткости определяется как ^[1]${\displaystyle е}$${\displaystyle {\mathcal {F}}}$${\displaystyle n}$${\displaystyle н^{е}}$${\displaystyle {\mathcal {F}}}$${\displaystyle G_{0},G_{1},\точки }$${\displaystyle h(G)}$${\displaystyle G}$

${\displaystyle \liminf _{i\to \infty }{\frac {\log h(G_{i})}{\log |V(G_{i})|}}.}$

Это число всегда находится в интервале от 0 до 1; оно равно 1 для семейств графов, которые всегда содержат гамильтонов или близкий к гамильтонову цикл, и 0 для семейств графов, в которых длина наибольшего цикла может быть меньше любой постоянной степени числа вершин.

Показатель краткости многогранных графов равен . Конструкция, основанная на клеетопах, показывает, что некоторые многогранные графы имеют самую большую длину цикла , ^[2] в то время как также было доказано, что каждый многогранный граф содержит цикл длины . ^[3] Многогранные графы — это графы, которые одновременно являются планарными и 3-вершинно-связными ; предположение о 3-вершинной связности необходимо для этих результатов, поскольку существуют наборы 2-вершинно-связных планарных графов (таких как полные двудольные графы ) с показателем краткости 0. Существует много дополнительных известных результатов о показателях краткости ограниченных подклассов планарных и многогранных графов. ^[1]${\displaystyle \log _{3}2\приблизительно 0,631}$${\displaystyle O(n^{\log _{3}2})}$${\displaystyle \Омега (n^{\log _{3}2})}$ ${\displaystyle K_{2,n}}$

Связанные кубические графы с тремя вершинами (без ограничения, что они должны быть планарными) также имеют показатель краткости, который, как было доказано, лежит строго между 0 и 1. ^{[4] [5]}