Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент принимает значения от 0 для деревьев до 1 для максимальных планарных графов.
Определение
Коэффициент используется для сравнения общей структуры циклов связного планарного графа по отношению к двум крайним значениям. С одной стороны имеются деревья, планарные графы без циклов. Другая крайность представлена максимальными планарными графами, имеющими наибольшее возможное число рёбер и граней для заданного числа вершин. Нормализованный коэффициент сетчатости — это отношение числа циклов к максимально возможному числу циклов в графе (с тем же числом вершин). Отношение принимает значение от 0 для деревьев до 1 для любого максимального планарного графа.
Вообще говоря, можно показать с помощью эйлеровой характеристики, что все планарные графы с n {displaystyle n} вершинами имеют максимум 2 n − 5 {displaystyle 2n-5} ограниченных граней (одна неограниченная грань не считается) и, если имеется m {displaystyle m} рёбер, то число ограниченных граней равно m − n + 1 {displaystyle m-n+1} (что равно контурному рангу графа). Таким образом, нормализованный коэффициент сетчатости можно определить как отношение двух чисел:
α = m − n + 1 2 n − 5 . {displaystyle alpha ={frac {m-n+1}{2n-5}}.}И этот коэффициент меняется от 0 для деревьев до 1 для максимальных планарных графов.
Приложения
Коэффициент сетчатости может быть использован для оценки избыточности сети. Этот параметр, наряду с алгебраической связностью, которая измеряет надёжность сети, может быть использован для измерения топологических аспектов стойкости сети водопровода; также используется для описания структуры улиц в городах.
Ограничения
В пределе для больших графов (число рёбер n ≫ 1 {displaystyle ngg 1} ) сетчатость стремится к следующей величине:
α ≈ ⟨ k ⟩ 4 − 1 2 {displaystyle alpha approx {frac {langle k angle }{4}}-{frac {1}{2}}} ,где ⟨ k ⟩ = 2 m / n {displaystyle langle k angle =2m/n} — средняя степень вершин в графе. Таким образом, для больших графов сетчатость не несёт больше информации, чем средняя степень.