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

Перейти к навигацииПерейти к поиску

Показатель короткости — это числовой параметр семейства графов, который показывает, насколько далеки от гамильтоновости могут быть графы семейства. Интуитивно, если является показателем короткости графа семейства , тогда любой граф с вершинами имеет цикл длины, близкой к , но некоторые графы не имеют более длинные циклы. Более точно, для любого упорядочения графов в в последовательность , и функции , определённой как длина наибольшего цикла в графе , показатель короткости определяется как[1]

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

Показатель короткости полиэдральных графов равен . Построение, основанное на многогранниках Кли, показывает, что некоторые полиэдральные графы имеют наибольший цикл длиной [2], и было также доказано, что любой полиэдральный граф содержит цикл, длиной [3]. Полиэдральные графы — это графы, которые одновременно являются планарными и вершинно 3-связными. Факт вершинной 3-связности здесь важен, поскольку существует множество вершинно 2-связных планарных графов (таких как полные двудольные графы ) с показателем короткости 0. Есть много дополнительных результатов относительно показателя короткости ограниченных подклассов планарных и полиэдральных графов[1].

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

Примечания

  1. 1 2 Grünbaum, Walther, 1973, с. 364–385.
  2. Moon, Moser, 1963, с. 629–631.
  3. Chen, Yu, 2002, с. 80–99.
  4. Bondy, Simonovits, 1980, с. 987–992.
  5. Jackson, 1986, с. 17–26.

Литература