Показник короткості

Показник короткості — це числовий параметр сімейства графів, який показує, наскільки далекими від гамільтоновості можуть бути графи сімейства. Інтуїтивно, якщо $e$ — показник короткості графа сімейства $ℱ$, то будь-який граф із $n$ вершинами має цикл довжини, близької до $n^e$ але деякі графи не мають довших циклів. Точніше, для будь-якого впорядкування графів у $ℱ$ у послідовність $G_0,G_1,\dots$, та функції $h(G)$, визначеної як довжина найбільшого циклу в графі $G$, показник короткості визначають якШаблон:Sfn

$\underset{i\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{\log h(G_i)}{\log |V(G_i)|}.$

Це число завжди міститься в інтервалі від 0 до 1. Показник дорівнює 1, якщо графи сімейства завжди містять гамільтонів або близький до гамільтонового цикл, і 0, якщо найбільша довжина циклів у графах сімейства може бути меншою від будь-якого сталого степеня числа вершин.

Показник короткості поліедральних графів дорівнює ${\log }_{3}2\approx 0,631$. Побудова, заснована на многогранниках Клі, показує, що деякі поліедральні графи мають найбільший цикл завдовжки $O(n^{{\log }_{3}2})$Шаблон:Sfn, і було також доведено, що будь-який поліедральний граф містить цикл, довжиною $\mathrm{\Omega }(n^{{\log }_{3}2})$Шаблон:Sfn. Поліедральні графи — це графи, які одночасно є планарними і вершинно 3-зв'язними. Факт вершинної 3-зв'язності тут важливий, оскільки існує множина вершинно 2-зв'язних планарних графів (таких як повні двочасткові графи $K_{2,n}$) із показником короткості 0. Є багато додаткових результатів щодо показника короткості обмежених підкласів планарних та поліедральних графівШаблон:Sfn.

Вершинно 3-зв'язні кубічні графи (без вимог планарності) також мають показник короткості, який (як було показано) лежить строго між 0 і 1Шаблон:SfnШаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття